基于改進(jìn)蟻群算法的車(chē)輛路徑仿真研究

1、基于改進(jìn)蟻群算法的車(chē)輛路徑仿真研究唐連生，程文明，張則強(qiáng)，鐘斌，梁劍（西南交通大學(xué)機(jī)械工程研究所，成都 610031）摘要：針對(duì)基本蟻群算法收斂速度慢、易陷于局部最優(yōu)等缺陷，提出了一種改進(jìn)蟻群算法。通過(guò)車(chē)輛的滿載率調(diào)整搜索路徑上的啟發(fā)信息強(qiáng)度變化，對(duì)有效路徑采取信息素的局部更新和全局更新策略，并對(duì)子可行解進(jìn)行3-opt優(yōu)化，在實(shí)現(xiàn)局部最優(yōu)的基礎(chǔ)上保證可行解的全局最優(yōu)。通過(guò)對(duì)22城市車(chē)輛路徑實(shí)例的仿真，仿真結(jié)果表明，改進(jìn)型算法性能更優(yōu)，同基本蟻群相比該算法的收斂速度提高近50%，效果顯著，該算法能在更短時(shí)間內(nèi)求得大規(guī)模車(chē)輛路徑問(wèn)題滿意最優(yōu)解。關(guān)鍵字：物流，VRP，蟻群算法，車(chē)輛路徑中國(guó)分類(lèi)號(hào)：T

2、P18 文獻(xiàn)標(biāo)識(shí)碼：AVEHICLE ROUTING SIMULATION RESEARCH BASED ON AN IMPROVED ANT COLONY ALGORITHMTang Liansheng, Cheng Wenming, Zhang Zeqiang, Zhong Bin, Liang jian(Research Institute of Mechanical Engineering, Southwest Jiaotong University, Chengdu, 610031)ABSTRACT：An improved ant colony algorithm is propos

3、ed aiming at the basic ant colony algorithms convergence slow and be prone to plunge a partial basis. The inspired route information strength changes according to the search vehicles loaded rate. Both local information and global information are updated on the effective route. Achieving optimal loca

4、l basis ensures the best possible solution by means of 2-opt optimized algorithm. The example of 22 city vehicle routing is simulated by this algorithm, and it shows that the speed of convergence nearly 50% increased compared with the basic ant algorithm. The algorithm has achieved significant resul

5、ts, and less time by the algorithm to solve large-scale vehicle routing problems.KEYWORDS：Logistics; VRP; Ant colony algorithm; Vehicle routing 1 引言車(chē)輛路徑問(wèn)題（Vehicle Routing Problem，簡(jiǎn)稱(chēng)VRP）來(lái)源于交通運(yùn)輸，由Dantzig1于1959年提出，它是組合優(yōu)化問(wèn)題中一個(gè)典型的NP-hard問(wèn)題，用于研究亞特蘭大煉油廠向各加油站投送汽油的運(yùn)輸路徑優(yōu)化問(wèn)題，并迅速成為運(yùn)籌學(xué)和組合優(yōu)化領(lǐng)域的前沿和研究熱點(diǎn)，吸引眾多學(xué)者對(duì)其進(jìn)行研

6、究。通常用圖G=(V,E)用來(lái)描述該問(wèn)題2，在圖G=(V，E)中，V=0,1,2,n，E=(i，j)，ij，i，jV，節(jié)點(diǎn)1表示倉(cāng)庫(kù)（depot），其它節(jié)點(diǎn)為客戶(hù)。每個(gè)客戶(hù)的需求為qi，邊(i，j)對(duì)應(yīng)的距離或運(yùn)輸時(shí)間或成本為Cij，所有車(chē)輛運(yùn)輸能力為Q，車(chē)輛從倉(cāng)庫(kù)出發(fā)，完成運(yùn)輸任務(wù)后回到倉(cāng)庫(kù)，每個(gè)顧客只能接受一次服務(wù)，問(wèn)題的目標(biāo)函數(shù)通常是車(chē)輛數(shù)和運(yùn)輸成本最小化。由于該問(wèn)題的復(fù)雜性，尋找到一種高效、精確的算法的可能性微乎其微，人們開(kāi)始嘗試?yán)梅律悄芩惴ㄇ蠼狻?蟻群算法是一種新的群體智能啟發(fā)式優(yōu)化方法，適合求解車(chē)輛路徑等組合優(yōu)化問(wèn)題。最初由意大利學(xué)者Dorigo34等人提出用于解決旅行商問(wèn)題，

7、隨著研究的不斷深入，已經(jīng)陸續(xù)滲透到電子、通訊、車(chē)間調(diào)度等工程領(lǐng)域。John E. Bell5將螞蟻系統(tǒng)優(yōu)化的亞啟發(fā)式方法應(yīng)用到VRP問(wèn)題的求解。Silvia6探討了在車(chē)輛容量限制條件下的VRP問(wèn)題，在亞啟發(fā)式算法基礎(chǔ)上提出了CVRP 的蟻群算法，并取得較好的效果。劉志勛7等在分析VRP和TSP區(qū)別基礎(chǔ)上，構(gòu)造了求解VRP的自適應(yīng)蟻群算法，提出了近似解可行化的解決策略。蟻群算法由于基本蟻群算法收斂速度慢且易陷于局部最優(yōu)，很難在較短時(shí)間內(nèi)對(duì)大規(guī)模VRP求得滿意最優(yōu)解，且該算法極易出現(xiàn)停滯現(xiàn)象，因此有必要對(duì)四川省應(yīng)用基礎(chǔ)研究項(xiàng)目（批準(zhǔn)號(hào):04JY029-058-1）唐連生 (1974.2-)，男（滿

8、族），遼寧人，博士生，研究方向?yàn)閿?shù)字物流與智能技術(shù)，車(chē)輛路徑。算法進(jìn)行改進(jìn)。1 基本蟻群算法簡(jiǎn)介910基本蟻群算法受真實(shí)蟻群覓食行為策略的啟發(fā)，螞蟻在覓食過(guò)程中對(duì)所經(jīng)過(guò)路段釋放一種被稱(chēng)為信息素的物質(zhì)，其他經(jīng)過(guò)該路段的螞蟻通過(guò)對(duì)殘留信息素的數(shù)量判斷是否重復(fù)該路段，從而找到一條巢穴到食物源之間的最短路徑。該路段殘留信息素越多，所有螞蟻選擇該路段的可能性也就越大。為模擬螞蟻實(shí)際行為設(shè)：m是蟻群中螞蟻的數(shù)量，dij是城市i到城市j之間的距離，ij是邊(i，j)的能見(jiàn)度，ij=1/dij，反映由城市i轉(zhuǎn)移到城市j的啟發(fā)程度，ij是邊(i，j)上的信息素軌跡強(qiáng)度，ijk是螞蟻k在邊(i，j)上留下的單位長(zhǎng)

9、度軌跡信息素量，pijk是螞蟻k從城市i轉(zhuǎn)移到城市j的狀態(tài)轉(zhuǎn)移概率， j是尚未訪問(wèn)的城市，則狀態(tài)轉(zhuǎn)移概率pijk （1）式中，allowedk=0,1,n-1表示螞蟻k下一步允許選擇的城市。和為兩個(gè)參數(shù)，分別反映了螞蟻在運(yùn)動(dòng)過(guò)程中積累的信息和啟發(fā)信息在螞蟻選擇路徑中的相對(duì)重要性8。為每只螞蟻設(shè)計(jì)一個(gè)禁忌表tabuk(k=1,2,m)，記錄在t時(shí)刻螞蟻k已走過(guò)城市，不允許該螞蟻在本次循環(huán)中重復(fù)經(jīng)過(guò)。本次循環(huán)結(jié)束后禁忌表被清空。螞蟻完成一次循環(huán)，對(duì)各路徑上的信息素進(jìn)行更新： （2） （3）式中ijk(t，t+1)表示第k只螞蟻在(t，t+1)時(shí)刻留在(i，j)路段上的信息量，ij(t，t+1)表示

10、本次循環(huán)中路段(i，j)的信息素增量，(1-)為信息素軌跡的衰減系數(shù)。Dorigo給出了三種不同的模型，分別為蟻周系統(tǒng)（ant-cycle system）、蟻量系統(tǒng)（ant-quantity system）、蟻密系統(tǒng)（ant-density system）。區(qū)別僅在于ijk(t，t+1)的表達(dá)試不同。蟻周系統(tǒng)與其他兩種模型的差別在于ij的表達(dá)式不同，使用了全局信息而其他兩者使用的局部信息。3 算法的改進(jìn)3 1 狀態(tài)轉(zhuǎn)移概率公式的改進(jìn)蟻群算法的主要依據(jù)是信息正反饋原理和啟發(fā)式算法的有機(jī)結(jié)合，ij的設(shè)計(jì)是蟻群算法的關(guān)鍵。當(dāng)群體規(guī) 模較大時(shí)，短時(shí)間內(nèi)難以求得最優(yōu)解，如果隨機(jī)產(chǎn)生的某一路徑信息量變化過(guò)

11、快，很容易出現(xiàn)搜索停滯現(xiàn)象，為控 圖1 改進(jìn)蟻群算法流程圖制信息量的變化速度，采用如下方法選擇下一個(gè)被訪問(wèn)的城市： 4）式中，0為車(chē)輛的滿載率，,其中為第k只螞蟻所在禁忌表的城市需求量之和，QV是車(chē)輛的允許載荷?？梢?jiàn)，隨車(chē)輛遍歷城市數(shù)量的增加而增加，它可以提高路徑選擇的多樣性，從而避免陷入局部最優(yōu)。q0(0,1)為常數(shù)，q為0到1之間的隨機(jī)數(shù)。當(dāng)qq0時(shí)，J仍按式（1）進(jìn)行計(jì)算。3 2 信息素更新策略的改進(jìn)信息素更新策略是蟻群算法的關(guān)鍵步驟之一，信息更新過(guò)快將導(dǎo)致算法陷入局部最優(yōu)甚至停滯，信息更新過(guò)慢則收斂速度緩慢，無(wú)法搜索到最優(yōu)路線。3 2 1全局信息更新 （5） （6）式中當(dāng)前全局最優(yōu)解的

12、路線長(zhǎng)度，Q常量，信息素的揮發(fā)系數(shù)。3 2 2局部信息更新螞蟻找到一個(gè)子可行解后，將子可行解路段(i，j)上的信息素進(jìn)行更新。 （7）式中常數(shù)，為本次循環(huán)最短路線長(zhǎng)度。 算法流程如圖1所示。 4 實(shí)例分析本文以eil22問(wèn)題為研究對(duì)象，已知有客戶(hù)，各客戶(hù)坐標(biāo)位置點(diǎn)及需求量已知，各車(chē)輛 圖2 eil22車(chē)輛行走路線圖 圖3 改進(jìn)蟻群算法的收斂進(jìn)程載重Q6000。初始參數(shù)設(shè)置為m20，迭代次數(shù)n_gen50，0.9，4，q00.6。采用Matlib7.0編程運(yùn)算，表1 本文算法同基本蟻群算法在相同參數(shù)下的實(shí)驗(yàn)結(jié)果比較算法類(lèi)型 最短線路長(zhǎng) 進(jìn)化次數(shù)基本蟻群算法 1 4 387.6 372 1 3 3

13、87.6 396 1 2 387.6 408改進(jìn)蟻群算法 1 4 387.6 184 1 3 387.6 189 1 2 387.6 210得到最終的線路為： 第一條線路：1151720221第二條線路：118211916131第三條線路：1112368101第四條線路：1794512141運(yùn)輸總距離387.6。結(jié)果如圖2所示。由表1可以看出，在基本參數(shù)相同的條件下，使用基本蟻群算法求解結(jié)果與改進(jìn)蟻群算法相同，但改進(jìn)后的蟻群算法的進(jìn)化次數(shù)大大降低，收斂速度有顯著提高。5 結(jié)論由仿真結(jié)果可以看出，改進(jìn)后的蟻群算法解的收斂速度提高近50%，通過(guò)調(diào)整信息素更新策略和啟發(fā)信息強(qiáng)度，彌補(bǔ)了基本蟻群算法由

14、于信息素更新過(guò)快易陷入局部最優(yōu)的缺點(diǎn)。該算法與3-opt算法相結(jié)合，在求解的精度方面也有了很大提高，同時(shí)為求解大規(guī)模VRP問(wèn)題提供了一種可行的方法。對(duì)該算法進(jìn)一步擴(kuò)展后，可用于求解有時(shí)間窗的VRP問(wèn)題，如何利用該算法求解突發(fā)事件下到達(dá)時(shí)間不確定的模糊VRP問(wèn)題將有待進(jìn)一步研究。 參考文獻(xiàn) 1Bernd Bullnheimer, Richard F. Hartl and Christine Strauss. An improved ant system algorithm for the vehicle routing problemJ/OL. .2 Alberto Colorni, Marco

15、 Dorigo, Vittorio Maniezzo. Distributed Optimization by Ant ColoniesJ. European conference on artificial life, Paris, France, Elsevier Publishing, 134-142. 3Marco Dorigo and Gianni Di Caro. Ant Algorithms for Discrete OptimizationJ. Artificial Life, 1999, 5 (3): 137- 172.4Marco Dorigo. Ant colonies

16、for the traveling salesman problemJ. Biosystems,1997,43:73-81.5John E. Bell, Patrick R. McMullen. Ant colony optimization techniques for the vehicle routing problemJ. Advanced Engineering Informatics Volume: 18, Issue: 1, January, 2004, pp. 41-486Silvia Mazzeo, Irene Loiseau. An ant colony algorithm for the capacitated vehicle routingJ. Electronic Notes in Discrete Mathematics Volume: 18, Complete, December 1, 2004, pp. 181-1867 劉志勛, 申金升, 柴躍廷. 基于自適應(yīng)蟻群算法的車(chē)輛路徑問(wèn)題研究J. 控制與決策, 2005, 20(5): 562-566. 8 Dennis Huisman, Albert P. M. Wage