[發(fā)明專利]基于數(shù)據(jù)驅(qū)動的群體智能計算的城市車輛路徑優(yōu)化方法

有效

• 申請?zhí)枺?/td>: 202011275358.7
• 申請日: 2020-11-16
• 公開（公告）號: CN112270047B
• 公開（公告）日: 2023-09-29
• 發(fā)明（設(shè)計）人: 王甲海;張勇鑫;張子臻
• 申請（專利權(quán)）人: 中山大學(xué)
• 主分類號: G06F30/15
• 分類號: G06F30/15;G06F30/27;G06F111/06
• 代理公司: 廣州市華學(xué)知識產(chǎn)權(quán)代理有限公司 44245
• 代理人: 林梅繁

1.基于數(shù)據(jù)驅(qū)動的群體智能計算的城市車輛路徑優(yōu)化方法，其特征在于，包括以下步驟：

S1、將城市多目標車輛路徑優(yōu)化問題建模成一個無向圖，倉庫和客戶為圖中的結(jié)點，結(jié)點的屬性包括坐標、需求量和服務(wù)時間窗；任意兩個結(jié)點之間通過邊相連接，邊的屬性包括旅行距離、旅行時間；并建立多目標函數(shù)，設(shè)定兩個優(yōu)化目標：所有車輛的旅行距離總和、最大的單個車輛旅行距離；

S2、設(shè)定M個均勻分布在[0,1]間的權(quán)重向量，使用權(quán)重和的方式將多目標函數(shù)的向量目標分解為M個單目標子問題；

S3、針對每個單目標子問題，訓(xùn)練一個帶有全面環(huán)境信息的圖注意力模型，直至模型收斂，得到M個神經(jīng)網(wǎng)絡(luò)模型；

S4、將訓(xùn)練得到的M個神經(jīng)網(wǎng)絡(luò)模型作為初始種群，對初始種群進一步訓(xùn)練，得到最終的M個模型；

S5、用訓(xùn)練好的M個模型對多目標車輛路徑優(yōu)化問題進行求解，獲得一組在兩個優(yōu)化目標間權(quán)衡的解集；

S6、計算解集中每個解對應(yīng)的車輛旅行距離總和以及最大的單個車輛旅行距離；

步驟S3的訓(xùn)練步驟包括：

S31、圖注意力模型包括編碼器與解碼器，將訓(xùn)練算例中的結(jié)點輸入到編碼器中，編碼器提取訓(xùn)練算例中各個結(jié)點的特征以及圖的結(jié)構(gòu)特征，得到結(jié)點的特征向量序列H＝(h₀,h₂,…,h_N)；

S32、更新當(dāng)前的車輛狀態(tài)，計算得到當(dāng)前的全面環(huán)境信息，將全面環(huán)境信息與結(jié)點特征向量序列輸入到解碼器，由解碼器決策選擇下一個服務(wù)的結(jié)點；直到所有客戶都被服務(wù)，得到關(guān)于訓(xùn)練算例的解；

S33、第i個單目標子問題的目標為權(quán)重向量與向量目標函數(shù)F(s|G)的內(nèi)積，即通過權(quán)重和的方式將向量目標函數(shù)F(s|G)轉(zhuǎn)化為在兩個目標上根據(jù)權(quán)重向量λ_i進行權(quán)衡的標量目標，其中分別是權(quán)重向量λ_i的兩個分量，f₁(s)、f₂(s)分別表示車輛的旅行距離總和與最大的單個車輛旅行距離；

步驟S33中，針對單目標子問題使用基于策略梯度的REINFORCE算法對神經(jīng)網(wǎng)絡(luò)模型的參數(shù)θ進行訓(xùn)練，即：

其中b(G)是用于減小梯度方差的值函數(shù)，表示權(quán)重向量的轉(zhuǎn)置，F(xiàn)(s|G)表示多目標車輛路徑優(yōu)化問題中的向量目標函數(shù)；

步驟S4的訓(xùn)練包括過程：

S41、將強化學(xué)習(xí)訓(xùn)練得到的M個模型{π₁,π₂,…,π_M}作為初始種群；

S42、對種群中的每個模型π_i進行變異操作，即對模型的參數(shù)θ_i加入擾動，生成一個子代模型π_i^′，相應(yīng)地模型π_i為子代模型π_i^′的父代模型；

S43、在多目標車輛路徑優(yōu)化問題環(huán)境中對父代模型和子代模型進行評估，得到各個模型的適應(yīng)度值；然后將適應(yīng)度值根據(jù)非支配等級和擁擠距離進行排序，選擇前M個模型作為下一代種群；

S44、不斷迭代S42與S43，直到達到設(shè)定的迭代次數(shù)。

2.根據(jù)權(quán)利要求1所述的城市車輛路徑優(yōu)化方法，其特征在于，步驟S1中服務(wù)時間窗t_i由一個二元組[a_i,b_i]構(gòu)成，a_i和b_i分別表示最早和最晚車輛到達時間。

3.根據(jù)權(quán)利要求1所述的城市車輛路徑優(yōu)化方法，其特征在于，步驟S1中車輛k服務(wù)的客戶結(jié)點與倉庫結(jié)點構(gòu)成一條路徑r_k；步驟S5中多目標車輛路徑優(yōu)化問題的一個解s由K個路徑構(gòu)成，解s需要滿足以下約束：(1)所有結(jié)點都被服務(wù)且僅服務(wù)一次，(2)所有的路徑都滿足容量約束；(3)所有的客戶結(jié)點都在各自的服務(wù)時間窗內(nèi)被服務(wù)。