求解車輛路徑問題的改進蟻群算法

王占鋒，杜海蓮，安素芳，張翠軍

（1.石家莊經(jīng)濟學(xué)院 信息工程學(xué)院，河北 石家莊050031；2.河北師范大學(xué) 電子系，河北 石家莊050023）

1959年，Dantzig和Ramser提出車輛路徑優(yōu)化問題 .這是一個經(jīng)典的NP-hard組合優(yōu)化問題，采用傳統(tǒng)的數(shù)學(xué)方法求解往往找不到正確的解，而只有解決了車輛路徑優(yōu)化這個難題，現(xiàn)代物流業(yè)配送的效率及性能才能得到提高［1］.由于車輛路徑問題屬于NP-hard問題，利用傳統(tǒng)的精確算法無法找到正確的配送路徑，實際應(yīng)用中往往采用啟發(fā)式算法［2-3］.蟻群算法是一種新型的啟發(fā)式螞蟻群體仿生優(yōu)化算法，它利用正反饋原理達到算法的最終收斂來搜索最優(yōu)解，性能較高，其缺點是求解時程序容易較早收斂，停滯［4］.遺傳算法是一種仿生型優(yōu)化算法，其優(yōu)點是全局搜索能力較強，缺點是沒有使用系統(tǒng)中的反饋信息.本文將遺傳算法和蟻群算法融合，提出一種改進的蟻群算法，求解車輛路徑優(yōu)化問題.

1 數(shù)學(xué)模型的建立

令配送中心的編碼為0，n個需要配送商品的客戶的編碼依次為1，2，…，n.設(shè)編碼為i的客戶的需要配送的貨物量為gi（i＝1，2，…，n），設(shè)m輛汽車可以完成所有配送任務(wù)，qmax為每輛配送汽車的最大載重量；編碼分別為i和j的客戶之間的運輸距離di，j（i＝0，1，2，…，n；j＝0，1，2，…，n）.數(shù)學(xué)模型的建立需要定義如下3個主要變量［5-7］.

1）變量xi，j，k.如果車輛k駛過客戶i和j之間的道路，xi，j，k取值為1，否則xi，j，k取值為0；

2）變量yk，i.如果車輛k為編號為i的客戶配送任務(wù)，yk，i取值為1，否則yk，i取值為0；

3）變量di，j.客戶i和客戶j之間運輸成本定義為行駛時間、運輸距離或運輸費用等，文中將di，j定義為客戶i和j之間的運輸距離.

建立的數(shù)學(xué)模型中，目標(biāo)函數(shù)的作用是使所有汽車的運距（行駛距離）之和z最短，即

同時，建立的約束條件是約束配送汽車的最大載重量，即

為保證只允許一輛車k完成編號為i的客戶的運輸任務(wù)，即

為限制只允許一輛汽車經(jīng)過某一客戶，則有

2 應(yīng)用蟻群算法求解車輛路徑

使用蟻群算法求解車輛路徑優(yōu)化問題，需定義如下變量［8-10］：

1）ηi，j為定義為邊（i，j）的能見度；2）τi，j（t）為時刻螞蟻殘留在邊（i，j）上的信息素；3）Δτi，j（t）為蟻群經(jīng)過一次迭代后，邊（i，j）上的信息素增值；4）Lk為經(jīng)過一次迭代后，編號k的螞蟻經(jīng)過所有的客戶點后爬行的路徑長度；5）α為啟發(fā)因子，表示信息素影響螞蟻選擇路徑的相對重要性（α≥0）；6）β為期望啟發(fā)因子，表示能見度影響螞蟻選擇路徑的相對重要性（β≥0）；7）ρ為信息素揮發(fā)系數(shù)（0≤ρ≤1），1-ρ定義為信息素的殘留系數(shù)；8）Q為經(jīng)過一次迭代后，螞蟻在經(jīng)過所有客戶后，在路徑上所釋放的信息素總量；9）tabuk為客戶禁忌表，表示已完成配送任務(wù)的客戶所構(gòu)成的集合；10）allowedk為允許編號k的螞蟻移動時可以移向的客戶所構(gòu)成的信息表；12）tourk為經(jīng)過一次迭代后，編號k的螞蟻所經(jīng)過的所有客戶編號所構(gòu)成的集合.

文中車輛路徑采用自然數(shù)編碼，即首先計算客戶之間、客戶與配送中心之間的距離di，j，并初始化每個客戶的貨物需求量，同時通過計算確定配送貨物需要的最少車輛數(shù).螞蟻從配送中心出發(fā)，其選擇概率的計算式為

從allowedk中選擇下一個配送客戶，直到汽車已配送客戶的貨物量之和超過其最大載重時，汽車駛回配送中心，形成一條子路徑，將若干條子路徑構(gòu)成車輛配送問題一個正確解［11-12］.

allowedk，τi，j（t），ηi，j（t），α，β等參數(shù)前文已經(jīng)提到，這里i為螞蟻所在的客戶點編號，j表示下一個移動概率最大的客戶編號.這種路徑選擇規(guī)則與基本蟻群算法類似，但平衡了信息素和能見度的作用，更接近于實際的蟻群系統(tǒng).

車輛路徑的適應(yīng)度函數(shù)［13-15］定義為

式（6）中：δ為正常數(shù)；k為編號k的螞蟻；z為螞蟻經(jīng)過所有客戶后爬行的路徑長度.

3 應(yīng)用改進后的遺傳變異算子優(yōu)化路徑

改進后的遺傳算法是根據(jù)概率mp1（0＜mp1＜1）的大小來執(zhí)行不同的逆轉(zhuǎn)變異.這樣擴大了父個體基因信息的選擇來源，從而增大了子個體的多樣性，防止算法過早收斂［16-20］.

改進后的遺傳變異算子有如下2個步驟.

1）隨機選擇父個體p1上一位基因r1，假設(shè)r1＝1.

2）隨機生成一個實數(shù) ，范圍在 （0，1）區(qū)間，令r和mp1比較，然后執(zhí)行以下不同的步驟：如果r≤mp1，從父個體p1中隨機選取不同于r1的一個基因作為r2；如果r＞mp1，重新選擇另外一個父個體p2，從父個體p2中選取r2，令父個體p1中r1和r2之間的編碼逆轉(zhuǎn)，產(chǎn)生下一代子個體o1.

將第一階段得到的局部最優(yōu)解編碼作為父代基因信息，然后使用改進的逆轉(zhuǎn)變異算子，得到下一子代的基因信息，符合條件的車輛配送路徑 .從生成的子代中選出目標(biāo)函數(shù)最優(yōu)者，即得到車輛路徑的全局最優(yōu)解.

4 仿真測試及結(jié)果分析

以車輛路徑Eil22問題為例，測試算法性能.物流中心使用一些載重為6t的汽車，對21個客戶配送貨物，物流中心編號為0，客戶編號分別為1，2，…，20，21，要求使用車輛最少，行車路線最短.客戶坐標(biāo)及客戶的需求量，如表1所示.

表1 客戶坐標(biāo)及配送量表Tab.1 Coordinates and distribution of customers

改進后蟻群算法求解客戶車輛路徑測試結(jié)果，如表2所示.參數(shù)設(shè)置：Nc，max＝10，α＝1，β＝3，ρ＝0.5，Q＝1，Nc，max1＝100，P＝0.6，m＝21（螞蟻數(shù)與客戶數(shù)相同），逆轉(zhuǎn)變異概率mp1＝0.3.算法共運行10次，運行后最優(yōu)解為0-9-7-5-2-1-6-8-0-14-16-21-19-0-12-15-18-20-17-0-10-3-4-11-13-0，路徑長為377.3km.

表2 改進后蟻群算法求解客戶車輛路徑問題測試結(jié)果Tab.2 Test results of customers vehicle routing problem based on improved ant colony algorithm

從表2可知：算法運行一次的平均時間為0.295s，找到最短路徑的概率為60%，其他幾次找到的配送路徑距離與最優(yōu)解差值很小，與文獻［5-6］中的算法相比，算法性能有很大的提高.

另外，分別使用遺傳算法和改進后的蟻群算法對文獻［4-5］中8個客戶的數(shù)據(jù)進行實驗 .其中：配送中心編號為0，8個客戶分別編號為1，2，…，8.使用遺傳算法求解車輛路徑問題的路徑中達到最優(yōu)解（最優(yōu)解總長度為67.5）的次數(shù)占總數(shù)的50%，平均路徑長度為68.55.

使用改進后的蟻群算法對文獻［4-5］中的8客戶的配送問題進行仿真實驗.參數(shù)設(shè)置：Nc，max＝10，α＝1，β＝3，ρ＝0.5，Q＝1，Ncmax1＝200，P＝0.6，m＝8逆轉(zhuǎn)變異概率mp1＝0.3.程序運行10次，其中7次找到了最短路徑，平均路徑長度為68.05.通過實驗結(jié)果對比，可以看出改進后的蟻群算法要比使用遺傳算法求得的最短車輛路徑的概率要高，算法性能有明顯的提高.

5 結(jié)論

文中車輛配送路徑采用了客戶和配送中心使用自然數(shù)編碼的方法，并將遺傳算法中的逆轉(zhuǎn)變異算子融合到現(xiàn)有的蟻群算法中，對使用蟻群算法求得的最優(yōu)解進行二次優(yōu)化，得到配送路徑最優(yōu)解的基因表達式.

仿真實驗證明，求解車輛路徑優(yōu)化問題時，使用文中改進后的蟻群算法有如下優(yōu)點：1）避免了單純使用遺傳算法求解車輛路徑優(yōu)化問題時，選擇、交叉、變異等遺傳操作的復(fù)雜性，程序運行速度較慢，性能較低的現(xiàn)象；2）與現(xiàn)有的求解車輛路徑優(yōu)化問題的蟻群算法相比，具有更快的運行速度，找到最優(yōu)解的概率更高；3）應(yīng)用文中所改進的蟻群算法時，操作上切實可行，避免了蟻群算法過早收斂，求解效率和性能都較高.

［1］ 潘正君，康立山，陳毓屏.演化計算［M］.北京：清華大學(xué)出版社，1998.

［2］ 段海濱 .蟻群算法原理及其應(yīng)用［M］.北京：科學(xué)出版社，2005.

［3］ DORIGO M，MANIEZZO V，COLOMI A.The ant system：Optimization by a colony of cooperating agents［J］.IEEE Transactions on Systems，Man，and Cybernetics：Part B，1996，26（1）：29-41.

［4］ 姜大立，楊西龍，杜文，等.車輛路徑問題的遺傳算法研究［J］.系統(tǒng)工程理論與實踐，1999，19（6）：40-44.

［5］ 王占鋒，張翠軍，許冀偉，等.求解非滿載車輛調(diào)度問題的改進遺傳算法［J］.計算機工程與設(shè)計，2008，29（15）：3991-3993.

［6］ WANG Zhan-feng，DU Hai-lian，HU Ji-chao，et al.An improved genetic algorithm for vehicle routing problem of non-full load［C］∥3rd International Symposium on Intelligent Information Technology Application.Washington D C：IEEE Computer Society，2009：173-175.

［7］ 樊建華，王秀峰.基于免疫算法的車輛路徑優(yōu)化問題［J］.計算機工程與應(yīng)用，2006，42（4）：210-212，217.

［8］ 張翠軍，劉坤起.求解一般車輛優(yōu)化調(diào)度問題的一種改進遺傳算法［J］.計算機工程與應(yīng)用，2004，40（33）：207-208，211.

［9］ 戴樹貴，陳文蘭，潘蔭榮，等.多配送中心車輛路徑安排問題混合蟻群算法［J］.四川大學(xué)學(xué)報：工程科學(xué)版，2008，40（6）：154-158.

［10］ BULLNHEIMER B，HARTL R，STRAUSS C.An improved ant system algorithm for the vehicle routing problem［J］.Annals of Operation Research，1999，89（13）：319-328.

［11］ BRYSY O，DULLAERT W.A fast evolutionary metaheuristic for the vehicle routing problem with time windows［J］.International Journal of Artifical Intelligence Tools，2002，12（2）：143-157.

［12］ 柳林，朱建榮.基于混合螞蟻算法的物流配送路徑優(yōu)化問題研究［J］.計算機工程與應(yīng)用，2006，42（13）：203-205.

［13］ GLOVER F.Tabu search：a tutorial［J］.Interfaces，1990，20（4）：74-94.

［14］ 丁建立，陳增強，袁著祉.遺傳算法與螞蟻算法的融合［J］.計算機研究與發(fā)展，2003，40（9）：1351-1356.

［15］ 陳陵，沈潔，秦玲，等.基于分布均勻度的自適應(yīng)蟻群算法［J］.軟件學(xué)報，2003，14（8）：1379-1387.

［16］ 張翠軍，張敬敏，王占鋒.基于車輛路徑問題的蟻群遺傳融合優(yōu)化算法［J］.計算機工程與應(yīng)用，2008，44（4）：233-235.

［17］ 劉志碩，申金升，柴躍廷.基于自適應(yīng)蟻群算法的車輛路徑問題研究［J］.控制與決策，2005，20（5）：562-566.

［18］ 唐連生，程文明，張則強，等.基于改進蟻群算法的車輛路徑仿真研究［J］.計算機仿真，2007，24（4）：262-264.

［19］ 徐強，宋海洲，田朝薇.解TSP問題的蟻群算法及其收斂性分析［J］.華僑大學(xué)學(xué)報：自然科學(xué)版，2011，32（5）：587-591.

［20］ 楊四海.TSP的等價解及其對免疫遺傳算法的干擾［J］.華僑大學(xué)學(xué)報：自然科學(xué)版，2007，28（1）：27-29.