結(jié)合聚類的改進HGS求解復(fù)雜車輛路徑問題

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

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

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

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

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

1 MDVRP_TW 建模與分析

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

1.1 問題假設(shè)和符號定義

MDVRP_TW滿足如下假設(shè)：

（1） 供應(yīng)方和需求地的位置坐標已知；

（2） 車輛送完貨后需返回原供應(yīng)方；

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

（4） 配送需盡量在各需求地設(shè)定的時間段內(nèi)完成。

MDVRP_TW的相關(guān)符號定義如表1所示：

1.2 問題優(yōu)化目標計算模型

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

1.3 問題模型

問題優(yōu)化目標：

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

2 問題求解算法IHGS_CD

本文提出的IHGS_CD由問題分解階段和子問題求解階段組成。其結(jié)構(gòu)如圖1所示。

2.1 IHGS_CD 的問題分解階段

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

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

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

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

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

Step4 當簇不發(fā)生變化或達到最大迭代次數(shù)時，則輸出各供應(yīng)方服務(wù)的需求地群。

2.2 IHGS_CD 的子問題求解階段

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

2.2.1 編碼與解碼規(guī)則

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

IHGS采用貪心策略對每個個體的配送路徑進行解碼，在不違背載重約束的情況下，根據(jù)個體從左往右的順序?qū)⑿枨蟮夭迦氘斍败囕v。如果添加下一需求地，當前車輛將違反載重量約束，則應(yīng)分配下一輛車來服務(wù)剩余需求地。

2.2.2 適應(yīng)度函數(shù)

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

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

2.2.3 接近食物

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

2.2.4 饑餓角色

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

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

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

2.2.5 算法步驟

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

Step1 初始化參數(shù)。

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

Step2 初始化個體Xi的位置。

Step3 判斷迭代次數(shù)是否大于T，如果是，則輸出全局最優(yōu)解，否則，繼續(xù)執(zhí)行Step4。

Step4 依照式（14）計算所有個體的適應(yīng)度值，更新Fitbest，F(xiàn)itworst，Xbest，分別依照式（20）式（21）計算饑餓權(quán)重G1和G2，依照式（18）計算M，依照式（16）更新P，依照式（15）更新個體。

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

Step6 t=t+1，返回執(zhí)行Step3。

3 實驗比較與分析

為驗證所提算法的有效性。本文通過Python程序?qū)λ憷M行仿真實驗。

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

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

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

4 結(jié)論

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