基于改進蟻群算法的車輛路徑仿真研究

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

2、P18 文獻標識碼：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 引言車輛路徑問題（Vehicle Routing Problem，簡稱VRP）來源于交通運輸，由Dantzig1于1959年提出，它是組合優(yōu)化問題中一個典型的NP-hard問題，用于研究亞特蘭大煉油廠向各加油站投送汽油的運輸路徑優(yōu)化問題，并迅速成為運籌學和組合優(yōu)化領域的前沿和研究熱點，吸引眾多學者對其進行研

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

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

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

9、度軌跡信息素量，pijk是螞蟻k從城市i轉移到城市j的狀態(tài)轉移概率， j是尚未訪問的城市，則狀態(tài)轉移概率pijk （1）式中，allowedk=0,1,n-1表示螞蟻k下一步允許選擇的城市。和為兩個參數(shù)，分別反映了螞蟻在運動過程中積累的信息和啟發(fā)信息在螞蟻選擇路徑中的相對重要性8。為每只螞蟻設計一個禁忌表tabuk(k=1,2,m)，記錄在t時刻螞蟻k已走過城市，不允許該螞蟻在本次循環(huán)中重復經過。本次循環(huán)結束后禁忌表被清空。螞蟻完成一次循環(huán)，對各路徑上的信息素進行更新： （2） （3）式中ijk(t，t+1)表示第k只螞蟻在(t，t+1)時刻留在(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)的表達試不同。蟻周系統(tǒng)與其他兩種模型的差別在于ij的表達式不同，使用了全局信息而其他兩者使用的局部信息。3 算法的改進3 1 狀態(tài)轉移概率公式的改進蟻群算法的主要依據是信息正反饋原理和啟發(fā)式算法的有機結合，ij的設計是蟻群算法的關鍵。當群體規(guī) 模較大時，短時間內難以求得最優(yōu)解，如果隨機產生的某一路徑信息量變化過

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

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

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

14、于信息素更新過快易陷入局部最優(yōu)的缺點。該算法與3-opt算法相結合，在求解的精度方面也有了很大提高，同時為求解大規(guī)模VRP問題提供了一種可行的方法。對該算法進一步擴展后，可用于求解有時間窗的VRP問題，如何利用該算法求解突發(fā)事件下到達時間不確定的模糊VRP問題將有待進一步研究。 參考文獻 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 劉志勛, 申金升, 柴躍廷. 基于自適應蟻群算法的車輛路徑問題研究J. 控制與決策, 2005, 20(5): 562-566. 8 Dennis Huisman, Albert P. M. Wage