基于聚類分析和種子進化算法的車輛路徑優化算法

冀德剛，魏俊萍，賈 鸝

（1.河北農業大學 理學院，河北 保定 071001；2.保定市科學技術信息研究所，河北 保定 071000）

1 引言

物流優化方案[1-6]是一個涉及多方面、多系統的組合優化方案，包含客戶系統、倉儲系統、運輸系統等諸多方面的優化。而運輸系統優化是物流運輸配送過程中的重要環節，也是控制物流營運成本的核心內容[7-12]。如果配送車輛路徑合理，不但能夠減少送貨時間，降低物流成本，同時還能夠使客戶達到較高的滿意度，實現物流管理科學化的目標，因此本文只討論車輛路徑優化問題。

2 VRP模型

為了描述問題方便，定義如下變量：M代表車輛總數，N代表客戶數量；Burk代表配送車輛k的最大限載量；Vonk代表配送車輛k的最大裝載容積；Carijk代表車輛k從i客戶到j客戶的配送基礎費用（i=1,2,...,N；j=1,2,...,N；k=1,2,...,M）；λTL代表運輸延時調整系數（λTL∈[1,+∞]）；CuWi代表客戶i的貨重；CuVi代表客戶i的貨物體積。

目標函數表示車輛的總費用等于每輛配送車的總費用乘以懲罰因子，懲罰因子隨著運輸時間的增長而不斷增大，具體大小需要預先設定。懲罰因子較大時，該目標函數轉化為帶時間窗路徑優化函數（本文沒有考慮帶時間窗路徑優化的問題，故在數值計算時λTL=1）。

約束條件：

其中式（4）、（5）保證每個客戶的貨物都得到配送；式（6）保證每個客戶只由一輛車送達貨物；式（7）保證一條線路上的所有客戶貨物總重不超過配送車輛最大載重量；式（8）保證一條線路上的所有客戶貨物總體積不超過配送車輛最大載容量；式（9）、（10）為約束條件。

3 車輛路徑優化算法設計思路

基于物流運輸的實際情況，考慮到物流系統優化的諸多要求，把整個優化過程分成兩個階段：

（1）分割區域：考慮到在物流配送中一個特定區域只能由一臺車來完成，因此對于一個具體的城市，有必要對整個區域進行劃分。首先把每一個指定的客戶看成一個二維的點，把區域內的公路看成線，這樣通過點與線就可以把整個區域組成一個連通網，把每兩點間公路距離定義為兩點間距離。其次通過k-means聚類，把近距點劃為同一區域，這樣就完成了整個區域的劃分。

（2）優化方法：使用智能算法對每個區域中的配貨路線進行優化，最終形成最優配送方案。具體優化時，先讓優化個體在局部區域深度搜索后，再進行聚類分組之間的二次優化，搜尋全局最優值。

兩階段法的設計從實際的物流配送出發，同時在不同區域分別確定局部最優解，然后不同區域間再次優化，很大程度上降低了算法的輸入量，使算法的求解速度有效提高。

4 基于聚類和種子進化算法的復合算法

4.1 K-means聚類

K-means算法原理：首先從樣本數據中隨機選取K個點作為初始聚類中心；其次計算每一個樣本到聚類中心的距離（本文使用歐氏距離），把距離每個中心最近的樣本點歸為該中心所在的類。接下來計算新形成的每一個類中所有樣本數據的平均值作為新的聚類中心，直到相鄰兩次的聚類中心不再發生變化，此時K-means聚類結束[13]。

4.2 種子進化算法(SOA：Seed Optim ization Algorithm)

種子進化算法思想源于豆科植物種子的傳播規律。它的整體思路如下：首先把待優化的車輛運輸區域看成土地，那么最優值就應該在土地最肥沃的區域取得。在這種思想下，可以用目標函數值來確定每個區域土地的肥沃程度。土地貧瘠，則目標函數值低，土地肥沃，則目標函數值高。顯然如果經過傳播后的種子所落區域是肥沃土地，那么它生長和傳播的機會就會很大；否則，傳播的可能性就很小。經過反復搜索，植株會在最肥沃的土地上被找到，此時優化問題的目標函數就取得最優值。這樣反復執行的過程經過抽象最終形成一種進化算法-種子進化算法。種子進化算法中散射現象是最核心的部分，整個算法中的搜索機制由散射來完成[14]。

4.3 車輛路徑選擇的復合優化算法

基于聚類和種子進化的車輛路徑選擇的復合優化算法（KMSOA:K-Means Seed Optimization Algorithm）設計分為兩個階段：（1）聚類；（2）優化算法求解。其流程圖如圖1、2所示。

圖1 種子進化算法流程圖

圖2 父種選擇流程

KMSOA算法首先把物流運輸的區域利用K-means算法進行區域劃分，然后計算每個父種對應的適應度函數值，依賴父種的適應度函數值來完成父種的選擇和傳播，如果滿足終止條件則結束，否則生成下一代新的父種，然后再次進行區域劃分，反復迭代執行。

5 數值實驗

5.1 實驗數據

為了驗證本文算法的可行性及有效性，實驗中采用與文獻[15]相同的數據(見表1)，以便進行比較。

表1 實驗數據

5.2 實驗說明

距離：所有點之間只考慮直線距離，其他情況不予考慮，距離函數采用歐式距離：

KMSOA算法說明：

（1）聚類中K的取值：2到可調度的最多可用車量數。

（2）把優化目標函數定義為適應度函數，即式（3），懲罰因子λTL=1，不考慮時間窗，其中任意兩點間的車輛配送費用即為兩點間的歐氏距離。

（3）父種類別個數取20。

（4）距離限定標準：避免父類選擇為種子的集中分布，距離的限定標準采用每兩個種子之間距離的30%。

（5）算法執行最大次數取50次。

5.3 實驗結果和分析

為了驗證文中給定復合算法的有效性，把文中結果和文獻[15]提出的混合遺傳算法做比較，獨立運行9次，結果見表2與表3。

表2 混合遺傳算法求解結果

表3 KMSOA求解結果

表2、表3展示了在相同條件下混合遺傳算法與本算法的對比，本文提出的KMSOA算法無論從平均值還是迭代次數來看，均優于混合遺傳算法。實驗數據再次說明文中給出算法能夠降低算法的輸入量，提高收斂速度，對物流運輸中運輸路徑優化問題具有一定的可行性和有效性。

[1]F Alffedo,T Montan,R Galv.A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service[J].Computers&Operations Research,2006,33:595-619.

[2]朱志勇,刁洪祥.基于改進遺傳算法的車輛路徑問題研究[J].湘潭大學自然科學學報,2011,33(3):115-118.

[3]何未雨.物流配送最佳路徑的最差-最優蟻群算法實現[J]甘肅科技縱橫,2011,40(5):104-106.

[4]BOmbuki,B JRoss,E Hanshar.Multi-Objective Genetic Algorithms for Vehicle Routing Problem with TimeWindows[J].Applied Intelligence,2006,(24):17-30.

[5]姜貴山,姬長虹.周期性車輛路徑問題在物流中的應用：案例研究[J].科學技術與工程,2010,10(11):2 694-2 697.

[6]E Taniguchi,N Ando.An Experimental Analysis on Probabilistic Vehicle Routing and Scheduling with ITS[J].Journal of the Eastern Asia Society for Transportation Studies,2005,(6):3 052-3 06l.

[7]G Alvarenga.A Hybrid Approach for the Dynamic Vehicle Routing Problem with Time Windows[A].Proceedings ofthe Fifth International Conference on Hybrid Intelligent Systems[C].2005.

[8]J Y Potvin,Y Xu,I Benyahia.Vehicle routing and scheduling with dynamic travel times[J].Computers&Operations Research,2006,33:1 129-1 137.

[9]宋遠卓.物流配送中心搬運設備配置研究[D].成都:西南交通大學,2008.

[10]呂勇.蟻群優化算法及在網絡路由中的應用研究[D].杭州:浙江大學,2006.

[11]李晨.基于免疫遺傳算法的物流配送VRP問題研究[D].天津:天津理工大學,2009.

[12]胡田田.車輛路徑問題的知識表示支持系統研究[D].大連:大連理工大學,2006.

[13]張建輝.K-means聚類算法研究及應用[D].武漢:武漢理工大學,2007.

[14]張曉明,王儒敬,宋良圖.一種新的進化算法—種子優化算法[J].模式識別與人工智能,2008,21(5):677-681.

[15]郎茂祥,胡思繼.用混合遺傳算法求解物流配送路徑優化問題的研究[J].中國管理科學,2002,10(5):51-56.