結合聚類的改進HGS求解復雜車輛路徑問題

黃靜 王亞彬 白梅娟 閆聚兵 侯帥 王楊洋

關鍵詞：車輛路徑問題；多供應方；時間窗；聚類分解；改進饑餓游戲搜索算法

車輛路徑問題（VRP）是在1959 年由Dantzig 和Ramser首先提出[1]，自提出后便受到眾多學者來深入研究。典型的車輛路徑問題往往只存在一個供應方，多供應方車輛路徑問題（MDVRP）即存在多個供應方，通過合理的路徑優化，將需求地分配給確定供應方，并由供應方分配車輛來完成配送。

近年來部分研究提出了一些分解策略[2-5]，將MDVRP分解為一系列子問題（單供應方VRP） ，再求解該子問題。例如，陳誠等人[6]通過基于邊界客戶分配法的轉化策略把MDVRP轉化成單供應方VRP，再用禁忌搜索算法對單供應方VRP 進行路線規劃[7]。Ma等人使用全局搜索集群將問題轉化為多個單供應方的多目標優化問題，然后設計了一個多目標遺傳算法來解決轉化的VRP[8]。鄭建輝等人[9]通過最近距離分配原則來轉化多供應方問題，再根據禁忌搜索算法進行優化求解。史春燕等人[10]根據k-means聚類算法將多供應方VRP轉化為單供應方VRP，然后利用模擬退火算法進行求解。胡蓉等人[11]先用兩種基于Kmeans的聚類將原問題分解成若干子問題，再設計一種增強蟻群算法來求解。上述文獻對MDVRP的分解主要是根據需求地的密度或距離信息。而在其分解結果平衡性方面的研究目前還較少。然而對于MDVRP_TW問題，由于其求解難度較高，截至目前，在MDVRP_TW問題上獲得的成果仍是比較有限的，故開展相關研究意義重大。

本文提出了一種結合聚類分解策略的改進饑餓游戲搜索算法（Improved Hunger Games Search Algo?rithm Based on Cluster Decomposition， IHGS_CD），首先本文結合MDVRP_TW的特征，設計了求解該問題的改進饑餓游戲搜索算法（IHGS）。饑餓游戲搜索算法（Hunger games search，HGS）[12]是一種按照動物饑餓驅動活動和行為而設計的新型智能優化，具備尋優能力強、收斂快等特點。截至目前，還尚未有文獻將HGS應用于MDVRP_TW的求解。其次基于K-means的平衡約束聚類算法（BCGS）的思想使得各供應方的資源劃分更具平衡性。最后提出的改進饑餓游戲搜索算法，采用個體精度約束參數來控制個體繼續迭代，能有效提高個體精度。

1 MDVRP_TW 建模與分析

MDVRP_TW屬于帶軟時間窗約束的多供應方車輛配送問題，優化目標為最小化配送總成本。

1.1 問題假設和符號定義

MDVRP_TW滿足如下假設：

（1） 供應方和需求地的位置坐標已知；

（2） 車輛送完貨后需返回原供應方；

（3） 車輛為同種車型，且容量已知，在配送過程中不得超過其額定載重量；

（4） 配送需盡量在各需求地設定的時間段內完成。

MDVRP_TW的相關符號定義如表1所示：

1.2 問題優化目標計算模型

MDVRP_TW的優化目標為配送總成本H，該優化目標由兩部分組成：車輛經濟成本H1和軟時間窗懲罰成本H2。H1和H2的計算公式如式（1） 和（2） 所示：

1.3 問題模型

問題優化目標：

式（6）表示最小化配送總成本；式（7）表示容量限制約束，即分配給車輛的貨物量不能超過車輛的額定載重；式（8）代表所有車輛從某供應方出發且都回到該供應方；式（9）表示車輛駛入需求地，也會從其駛出；式（10）表示需求地間沒有子回路；式（11）表示從某供應方出發的車輛數和回到該供應方的車輛數相等。

2 問題求解算法IHGS_CD

本文提出的IHGS_CD由問題分解階段和子問題求解階段組成。其結構如圖1所示。

2.1 IHGS_CD 的問題分解階段

IHGS_CD的問題分解階段執行BCGS[13]，用于將原問題MDVRP_TW 分解為Gt 個單供應方子問題VRP_TWs。

隨著需求地數量逐漸增大，聚類后會出現各供應方服務的需求地數量相差較大。為確保各供應方的需求地資源能平衡劃分，采用BCGS進行聚類，根據對簇可以包含的數據點個數進行限制，可更合理地分配各供應方所服務的需求地群。BCGS步驟如下：

Step1 對每個需求地進行K-means聚類。初始化簇數目為供應方數目K，初始化簇可以包含的數據點個數上限為u，初始化簇中心為每個供應方的坐標位置，評價指標為歐式距離和u，終止條件為簇不發生變化或達到最大迭代次數。

Step2 將需求地ni分配至合適的供應方。計算ni與各簇中心點的距離，按照由近到遠排序后存入Q={mj|j=1，2，3，...，K}中。然后，按照由近到遠順序嘗試加入Q 中的某一個簇中。

Step3 平衡需求地群。如果供應方mj簇中當前需求地個數未達到u，則將需求地ni加入簇mj中。但若簇mj中當前需求地個數已達上限，則需比較簇mj當前邊界需求地nb離中心點的位置與ni離簇mj中心點的位置。若ni離中心點更近，則將簇mj中的當前邊界需求地nb移出該簇mj，然后將需求地ni加入簇mj中。且對nb （邊界需求地即簇中與中心點距離最遠的需求地）進行重新分配。否則用相同的策略嘗試將ni加入簇mj+1中，直到ni成功添加至某個簇。

Step4 當簇不發生變化或達到最大迭代次數時，則輸出各供應方服務的需求地群。

2.2 IHGS_CD 的子問題求解階段

本階段采用設計的IHGS依次對每個VRP_TW進行求解，進而可獲得原問題的解和優化目標值。

2.2.1 編碼與解碼規則

本文采用的自然數編碼[8]。每個個體代表多輛車。

IHGS采用貪心策略對每個個體的配送路徑進行解碼，在不違背載重約束的情況下，根據個體從左往右的順序將需求地插入當前車輛。如果添加下一需求地，當前車輛將違反載重量約束，則應分配下一輛車來服務剩余需求地。

2.2.2 適應度函數

適應度對于評價個體位置的優劣和對個體進行位置更新操作有著重要作用。最優的個體Xbest即是適應度最高的種群個體。因本文所設的目標函數為配送總成本，故可將種群個體的適應度設成與配送總成本成反比關系的值，即當配送總成本越小，該種群個體的適應度越高，反之則相反。則適應度函數設置如式（14） 所示：

H 代表當前個體所求得的配送成本，min（H）代表最小配送成本值，max（H）代表最大配送成本值。

2.2.3 接近食物

X（t）為第t 代個體位置，t 是迭代次數，rn（1）是一個滿足正態分布的隨機數，c1和c2均是范圍在[0，1]的隨機數，h 是一個可以改善算法性能的控制參數，G1和G2指的是饑餓的權重，Xbest代表全局最優位置。P 為在[-a，a]范圍內，用于控制活動范圍的參數公式如式（16） 所示：

2.2.4 饑餓角色

模擬搜索中個體的饑餓特征為：

Z 代表個體數量，hg（i）表示個體的饑餓程度，Shg是全部個體饑餓程度的總和。c3，c4和c5均是范圍在[0，1]的隨機數。

在每次迭代中，當個體適應度與最佳適應度相同時，將個體的饑餓值設置為0。否則，在原始饑餓值的基礎上增加一個新的饑餓值hgn，每個個體對應不同的hgn。hgn的公式如式（23） 所示：

2.2.5 算法步驟

根據前面對接近食物和饑餓角色的描述，可將整個算法流程描述如下：

Step1 初始化參數。

個體總數量N，最大迭代次數T，參數h，全部個體饑餓程度的總和Shg，個體精度約束參數f。

Step2 初始化個體Xi的位置。

Step3 判斷迭代次數是否大于T，如果是，則輸出全局最優解，否則，繼續執行Step4。

Step4 依照式（14）計算所有個體的適應度值，更新Fitbest，Fitworst，Xbest，分別依照式（20）式（21）計算饑餓權重G1和G2，依照式（18）計算M，依照式（16）更新P，依照式（15）更新個體。

Step5 依照式（14）計算更新的個體適應度值，若Fit

Step6 t=t+1，返回執行Step3。

3 實驗比較與分析

為驗證所提算法的有效性。本文通過Python程序對算例進行仿真實驗。

算例：設在一個邊長為35km的正方形區域里有3個供應方和30個需求地，每個供應方均配備4臺車輛，且每輛車的空車重量為5 000kg，平均速度為30km/h，車輛的最大負載均為11t。要求車輛配送路線合理，使之取得最短配送總長度。

設置最大迭代次數T=100，改善算法性能的參數h=0.03，個體精度約束參數f=0.3，搜索空間的上限BU=100，下限BL=100，懲罰成本Me=10元/小時，Ml=15元/小時，Mc=1.2元/km，Mh=6.8元/L。

表2給出了應用本文設計的IHGS_CD求解到的最優配送路線與應用結合最近距離分配的禁忌搜索算法的求解結果比較，驗證了本文算法的有效性。其中，禁忌搜索算法的參數設置為：不可行路徑懲罰權重為300km，迭代次數為400，每次迭代搜索當前鄰居個數為40，禁忌長度為20。通過對比可得，應用本文設計的IHGS_CD 對算例求解，得到的最優結果為140.14km，與應用最近距離分配結合禁忌搜索算法得到的145.76km相比也有很大提升。此外，本文算法在求解過程中確保每個供應方的需求地資源能平衡劃分。據此可以看出，IHGS_CD在求解帶時間窗多供應方車輛路徑問題上具有良好效果。

4 結論

針對MDVRP_TW，本文提出一種結合聚類分解策略的改進饑餓游戲搜索算法進行求解。其中，該問題分解階段采用的BCGS能使得需求地資源平衡劃分給供應方，并有效控制問題規模且快速引導算法在較優區域內搜索，求解階段采用IHGS對每個分解后的子問題VRP_TW進行求解，IHGS引入個體精度約束參數來控制個體繼續迭代，從而有效控制個體精度以提高算法的全局最優解。本文所提方法與結合最近距離的分配禁忌搜索算法相比，取得了較好的預測效果。同時，驗證了改進饑餓游戲搜索算法求解MDVRP_TW的有效算法，拓寬了其實際應用領域。