求解車輛路徑問(wèn)題的改進(jìn)蟻群算法

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

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

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

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

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

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

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

3）變量di，j.客戶i和客戶j之間運(yùn)輸成本定義為行駛時(shí)間、運(yùn)輸距離或運(yùn)輸費(fèi)用等，文中將di，j定義為客戶i和j之間的運(yùn)輸距離.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

改進(jìn)后的遺傳變異算子有如下2個(gè)步驟.

1）隨機(jī)選擇父?jìng)€(gè)體p1上一位基因r1，假設(shè)r1＝1.

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

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

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

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

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

改進(jìn)后蟻群算法求解客戶車輛路徑測(cè)試結(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.算法共運(yùn)行10次，運(yùn)行后最優(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，路徑長(zhǎng)為377.3km.

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

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

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

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

5 結(jié)論

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

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

［1］ 潘正君，康立山，陳毓屏.演化計(jì)算［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］ 姜大立，楊西龍，杜文，等.車輛路徑問(wèn)題的遺傳算法研究［J］.系統(tǒng)工程理論與實(shí)踐，1999，19（6）：40-44.

［5］ 王占鋒，張翠軍，許冀偉，等.求解非滿載車輛調(diào)度問(wèn)題的改進(jìn)遺傳算法［J］.計(jì)算機(jī)工程與設(shè)計(jì)，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)化問(wèn)題［J］.計(jì)算機(jī)工程與應(yīng)用，2006，42（4）：210-212，217.

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

［9］ 戴樹貴，陳文蘭，潘蔭榮，等.多配送中心車輛路徑安排問(wèn)題混合蟻群算法［J］.四川大學(xué)學(xué)報(bào)：工程科學(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)化問(wèn)題研究［J］.計(jì)算機(jī)工程與應(yīng)用，2006，42（13）：203-205.

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

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

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

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

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

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

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

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