基于混合蟻群算法的車輛路徑問題研究

梁承姬，崔佳誠，丁 一

(上海海事大學 物流研究中心，上海 201306)

基于混合蟻群算法的車輛路徑問題研究

梁承姬，崔佳誠，丁 一

(上海海事大學 物流研究中心，上海 201306)

為了求解車輛路徑問題，設計了一種結合節約算法和鄰域搜索算法的混合蟻群算法，該算法改善了標準蟻群算法搜索時間長、容易陷入局部最優解的問題。首次引入節約算法以提高初始解的質量，使得蟻群算法在較優的路徑中進行搜索，從而更有效地收斂到最優解；運用最大最小螞蟻系統控制路徑的信息素，避免算法陷入局部最優解；采用鄰域搜索算法優化某階段最優解的子路徑。應用該混合蟻群算法對VRPLIB數據庫實例進行了運算，取得了較為滿意的結果。

交通運輸工程；車輛路徑問題；混合蟻群算法；最大最小螞蟻系統；節約算法；鄰域搜索算法

0 引 言

車輛路徑問題(vehicle routing problem, VRP)是物流配送優化的基礎問題，同時也是提高物流經濟效益、事先物流科學化所必不可少的[1]。該問題自問世以來，很快就引起了運籌學、計算機等各學科專家學者的極大關注，成為運籌學以及組合優化領域的前沿和熱點問題。車輛路徑問題是組合優化領域著名的NP難題(nondeterministic polynomial problem)，求解非常復雜。半個世紀以來，許多學者從車輛路徑問題的實際出發，根據不同的目標函數和約束條件，建立了不同的數學模型，也提出了許多不同的算法。盛麗俊等[2]運用遺傳算法對VRPTW問題進行求解；吳思等[3]運用PSO算法解決了貨物帶權重的VRP問題；王志剛等[4]運用人工蜂群算法求解了車輛路徑問題；葉開文[5]運用增加反轉算子的蟻群算法求解了車輛路徑問題；蔡婉君等[6]運用多維信息素和基于掃描法的局部優化方法來提高蟻群算法的性能，求解了車輛路徑問題；王仁民等[7]利用變鄰域搜索算法對車輛路徑問題進行了求解。總的來看，求解車輛路徑問題的算法主要有兩大類：精確算法和啟發式算法[8]。精確算法是根據具體的模型和約束，用運籌學的方法得到精確的結論，精確算法得到的往往是最佳解。啟發式算法是憑借著經驗和直覺，通過不斷的優化，朝著最優解不斷靠近或搜索最優解的一種算法。圖1是求解車輛路徑問題的算法的關系示意。

圖1 VRP求解算法Fig.1 Solving algorithm of VRP

蟻群算法(ant colony optimization，ACO) 最先是由意大利學者M.DORIGO提出的一種啟發式算法[9]。蟻群算法在提出之初便是用來解決旅行商問題的，螞蟻沿最優路徑覓食和旅行商沿著最優路徑推銷商品之間有著極強的相似性。而車輛路徑問題作為旅行商問題的拓展，自然是最適合用蟻群算法來求解的。故筆者將以蟻群算法為基礎對VRP問題進行研究。蟻群算法是一種具有正反饋性的算法。初始時刻各邊的信息素是相同的，但只要有一只螞蟻給予微小的信息素增量，那么各邊的信息素濃度就會產生差別，不同的解之間也有了優劣之分，從而較好的路徑上會有越來越多的信息素留下，吸引更多的螞蟻。這個正反饋的過程使得初始解不斷朝著最優的方向進化。

然而，標準的蟻群算法在求解中存在搜索容易陷入局部最優解、收斂到全局最優解要花費較長的時間且解的結果容易在局部最優解和全局最優解之間波動的缺點，故筆者將對標準蟻群算法進行改進。首先，通過節約算法，給出問題的初始解，使得信息素僅留在較好的路徑上，從而蟻群算法可以更快更有效地收斂到最優解；其次，采用了提高算法性能的最大最小螞蟻系統；最后，通過鄰域搜索算法，對最優解的子路徑進行調整。提出的算法能兼顧局部最優和全局最優，具有較強的魯棒性。

1 VRP數學模型

VRP問題可以描述為有L個客戶點，每個客戶點的送貨量和坐標是已知的，配送中心有K輛車完成這L個客戶點的配送任務，完成任務后車輛需要返回配送中心，每輛車有一定的載重上限[10]。要求車輛在完成配送任務的前提下盡可能地節約運輸成本，且有以下的約束條件：

1)每段路徑上所有客戶點的送貨量總和不允許超過車輛的最大載重；

2)每段配送路徑的總路程長度不允許超過車輛配送的最大行駛距離；

3)每個客戶點必須有車輛經過，且只能由一輛車完成其需求。

其目標是使得某個實現設定的目標函數(如距離、成本、時間等)為最小。

圖2是一個基本的物流配送示意。假設有1個配送中心、7個客戶點、4條行駛路徑；其中行駛路徑1負責右上方3個客戶點的配送，行駛路徑2和3分別負責左上方和左下方的客戶點，行駛路徑4負責右下方2個客戶點的配送；這4條行駛路徑可以由一輛車分4次進行，也可以由4輛車同時進行；必須滿足車輛由配送中心出發、訪問完所有的客戶點，且最后返回配送中心。

圖2 物流配送示意Fig.2 Logistics distribution diagram

符號的定義：L為客戶點總數；q(i)為客戶點i的貨物需求量，單位為t，其中i=1,2,…，n；d(i,j)為客戶點i到客戶點j的距離，特別地當i，j=0 時，表示配送中心，如d(0,3)表示從配送中心到3號客戶點的距離，i,j=0，1，2,…，n；K為總車輛的數目；Qk為車輛k的最大載重，其中k=1，2,…，K；nk為車輛k完成配送的客戶總數，當nk=0 時，表示該車沒有參與配送；Rk為車輛k配送的客戶點的集合，當nk=0 時，Rk為空集；當nk≠0 時，Rk={rk1,rk2,rk3,…}?{1,2,…,L}，其中rki表示該客戶點在車輛k的行駛路徑中的順序為i，k=1，2 ,…，K。

約束條件：

1)每條線路上的客戶點貨物重量之和不超過汽車載重量：

(1)

2)每個客戶點的貨物都要得到送達，只能由一輛汽車來完成：

Rk1∩Rk2=,k1≠k2

(2)

3)行駛路徑要求訪問所有客戶點：

(3)

0≤nk≤L

優化目標函數：

將采用所有車輛的總行駛路徑最短為優化目標，最短的路徑意味著汽油的節省，車輛的損耗降低，司機疲勞程度的降低，對物流配送來說有著直接的經濟意義：

(4)

至此，車輛路徑問題的數學模型已經建立完畢，之后的編程以及算法設計都將圍繞這一數學模型展開。當式(4)的值S越小時，表明行駛路徑越優。

2 基于節約算法和鄰域搜索算法的混合蟻群算法

2.1 算法說明

通過節約算法得到問題的較優解，作為蟻群算法初始解的比較對象，當蟻群算法得到的解優于節約算法得到的解時，螞蟻才會在路徑上留下信息素，保證了信息素僅會留在較優的路徑上，從而能讓蟻群算法更有效地收斂到最優解。而每當有更優解出現時，對該條路徑進行鄰域搜索，使得所有的客戶點以“最優的方式”排列。

2.1.1 節約算法

節約算法運用在車輛路徑問題中的基本思路是首先把各個客戶點單獨與配送中心相連，構成n條“0→i→0”(i=1，2，…，n)初始路線(用雙線表示)，第i條線路的物流成本為[11]

Zi=C0i+Ci0

(5)

之后把客戶點i和客戶點j連接在一起，形成路線“0→i→j→0”(i，j=1，2，…，n)，計算出這兩點連接后費用的“節約值”：

s(i,j)=Ci0+C0j-Cij

(6)

s(i，j)越大，說明將客戶點i和客戶點j連接在一起時節約的總費用越多，因此應優先連接s(i，j)值大的點i和j。根據這一原則，CLARKE和WRIGHT在1964年提出C-K節約算法。圖3為典型的節約方案。約定把只有一個客戶的線路(如“0→i→0”)稱為初始化線路，把包含兩個或兩個以上客戶的線路(如“0→…→i→…→0”)稱為已構成線路。

圖3 典型的節約方案Fig.3 Typical C-W plan

通過節約算法，得到VRP問題的較優解，并將其作為蟻群算法的初始解，這樣可以提高蟻群算法的收斂速度，并保證信息素僅留在較優的路徑上，避免算法的停滯。

2.1.2 最大最小螞蟻系統

最大最小螞蟻系統(max-min ant system)是德國學者Stützle等提出的一種改進蟻群優化系統。

最大最小螞蟻系統在螞蟻系統的基礎上有4項主要的改進[12]。

1)每次迭代中，只有最優的螞蟻才釋放出信息素。

2)把信息素的大小限制在一個區間[τmax,τmin]內，這樣可以防止某些路徑上的信息素增長速度過快從而導致算法可能出現停止的現象，即所有的螞蟻都在對同一條路徑進行搜索，盡管這些路徑是較好的路徑，卻不一定是全局最優的路徑。

3)信息素的初始值將設定為其取值范圍的上限，并且和一個相對小的信息素蒸發速率相結合，這樣可以讓算法在最初的搜索步驟中探索更多可能的路徑。

4)當系統達到停滯狀態或者長時間沒有找到更優解的時候，所有信息素的值將被初始化。

2.1.3 鄰域搜索算法

蟻群算法在構造最優解時，僅僅得到了最優路徑中包含哪些客戶點，即“最優解的成分”，然而卻不一定是“最優解的排列方式”[13]。最優解的排列方式往往是唯一的，所以蟻群算法直接得到最優解的可能性很低。例如在圖4中，各個頂點即是最優路徑的成分(客戶點)，連線就是不同的排列方式(車輛行駛的路徑)。其中圖4(a)是算法得到的近似最優解，它包含了最優解需要遍歷的客戶點，卻沒有得到最優的行駛路徑，圖4(b)則是最優解。圖4訪問了相同的4個客戶點，然而，圖4(a)的行駛距離卻明顯大于圖4(b)的行駛距離。

圖4 鄰域搜索算法優化過程Fig.4 Optimization process of local search algorithm

使用的鄰域搜索就是將圖4(a)的解調整為圖4(b)的解的一種方法，確保解的最優性。通過在局部遍歷該路徑上所有點的排列方式，得到其中最短的一條路徑，作為算法的最終結果。

2.2 算法步驟

1)定義參數并設置參數的變量值。首先導入客戶點和配送中心的坐標，得到客戶的數量，客戶點之間的距離和貨物需求量。其次設置參數α,β,ρ，在蟻群算法中，參數α,β,ρ對算法的性能有著一定的影響。α表明了每條路徑的相對重要性，α的值越大表明螞蟻選擇之前選擇過的點的可能性就越高，但α過大會導致搜索陷入局部最優解，從而停滯；β表明能見度的相對重要性，β越大表明選擇該路徑就越依靠啟發信息；ρ表明路徑的持久性，可將1-ρ理解為跡衰減度。通常0≤α≤5，1≤β≤5，0.1≤ρ≤0.99，筆者將取α=1，β=2，ρ=0.95。螞蟻數量一般取為派送點數量的2/3，如總共有15個點的話，那么設置螞蟻數量為10。

2)設置信息素參數。在最大最小螞蟻系統中，信息素有最大值τmax和最小值τmin的限制，它們有著τmin=τmax×τrate的關系，其中最大最小信息素的比值為

(7)

式中：p為螞蟻一次搜索找到最優解的概率，假設p=0.05；Cn為配送中心和客戶點的總數量。

信息素最大最小值在初始的時候設置成多大無所謂，因為第一次搜索完會生成一個最優解，然后用這個解重新產生最大最小值。不妨設τmax=1，則τmin=τmax×τrate。信息素更新規則為只有全局最優的螞蟻才釋放信息素：

(8)

式中：Lb為最優螞蟻行駛過的路徑的長度，所以增加的信息素為距離的倒數；ρ為信息素的揮發。

同時更新信息素最大值和信息素最小值：

(9)

τmin=τmax×τrate

(10)

3)通過節約算法得到問題較優解，作為蟻群算法初始值Lb，并得到初始的最優路徑長Lb。

4)fori=1 tok，第n只螞蟻開始進行搜索。

5)根據概率公式：

式中：ηij(t)=1/dij。

求得第k只螞蟻的轉移概率p(i,j)，找到螞蟻k下一個要走的點j。

6)計算i和j連接后線路上的總貨運量Q，若Q≤VW(車輛最大容量)，則轉到步驟5)，螞蟻繼續選擇下一個要去的客戶點；否則螞蟻回到配送中心，表示這輛車已經完成配送任務，不能再承擔更多重量的貨物運輸，之后再從配送中心重新出發，轉到步驟5)，尋找下一個要去的客戶點。

7)當螞蟻訪問完所有的客戶點后，記錄其走過的路徑到path表中，并計算走過的路徑長度L，與當前最優路徑Lb比較，若L

8)k=k+1，若還有螞蟻沒進行搜索，則轉到步驟4)；當全部螞蟻遍訪完所有客戶點后轉到步驟9)。

9)按照式(7)～式(10)更新各邊的信息素。

10)判斷是否超過設定迭代次數而沒有產生更優解，否的話直接轉到步驟11)，是的話初始化信息素并轉到步驟11)。

11)I(迭代次數)=I+1，當完成預定迭代次數的搜索后，跳出并打印最優路徑；否則轉到步驟4)開始下一次迭代。

3 計算實例與結果分析

3.1 計算實例1

為了便于分析和比較，選用文獻[14]的第一個VRP實例進行試算。其中，車容量為8 t，問題規模為21(20個客戶點加上一個配送中心)，其基礎數據如表1，配送中心位于坐標點(52,4)，設置蟻群算法參數α=1，β=2，ρ=0.95。表2為本文算法和其他各算法的比較。

表1 客戶及配送中心數據

表2 各算法比較

由表2可見，本文算法得到的最優解為828.897，優于文獻[14]中列出的最優解846.785，多次運算的平均值也明顯優于文獻中的平均解，最優路徑經過驗證是可行的。且由圖5可見，算法收斂速度很快。

圖5 算法收斂圖Fig.5 Algorithm convergence diagram

3.2 計算實例2

為了進一步驗證算法的有效性，采用了國際公認的VRP算例庫VRPLIB中的經典算例，經大量運行測試，得到了較好的結果。限于篇幅，僅給出E-n22-k4，E-n30-k3，E-n51-k5，3個算例的結果，見表3。設置蟻群算法參數α=1，β=2，ρ=0.95。對VRPLIB中算例進行計算時，大部分算例達到了最優解，少部分甚至改進了最優解，也有一部分解比已知最優解稍差一些。表3給出了有代表性的3個算例。其中E-n22-k4達到了已知最優解，且得到了和已知最優路徑相同的路徑；E-n30-k3得到了更優于已知最優解的結果，但略有不足的是車輛數從3輛增加到了4輛，但行駛距離比已知最優解更短；E-n51-k5得到的解比已知最優解稍差一些，但偏差僅為1.5%，在可接受范圍之內。由此可見，筆者提出的算法是一種有效的混合算法。

表3 VRPLIB中問題的計算結果

Table 3 Calculation results of the problems in VRPLIB

4 結 語

筆者提出一種混合蟻群算法，該算法將蟻群算法和節約算法相結合，控制初始階段信息素僅留在較優路徑上，增強了蟻群算法的尋優能力，引入最大最小螞蟻系統的局部改進機制，防止了算法陷入局部最優解。仿真實驗及其對比結果表明，本算法能有效得到問題的最優解，具有較強的尋優能力。不過筆者僅考慮了基礎的VRP問題，對于一些復雜的VRP問題(如帶時間窗的VRPTW問題)，本文算法能否得到滿意的結果，有待進一步研究。

[1] 馬良,朱剛,寧愛兵.蟻群優化算法[M].北京:科學出版社,2008:9-18,85. MA Liang,ZHU gang,NING Aibing.AntColonyOptimization[M]. Beijing: Science Press,2008:9-18,85.

[2] 盛麗俊,周溪召.帶有時間窗的車輛路徑問題優化[J].上海海事大學學報,2007,28(4):64-67. SHENG Lijun,ZHOU Xizhao. Vehicle routing problem optimization with time windows[J].JournalofShanghaiMaritimeUniversity,2007,28(4):64-67.

[3] 吳思,丁以中.計重收費政策下的貨物權重車輛路徑[J].上海海事大學學報,2010,31(3):22-26. WU Si,DING Yizhong. Weighted vehicle routing problem under toll-by-weight policy[J].JournalofShanghaiMaritimeUniversity,2010,31(3):22-26.

[4] 王志剛,夏慧明.求解車輛路徑問題的人工蜂群算法[J].計算機工程與科學,2014,36(6):1088-1094. WANG Zhigang,XIA Huiming. An artificial bee colony algorithm for the vehicle routing problem[J].ComputerEngineering&Science,2014,36(6):1088-1094.

[5] 葉開文.基于群體智能的車輛路徑問題研究[D].西安:西安電子科技大學,2014. YE Kaiwen.ResearchontheVehicleRoutingProblemBasedonSwarmIntelligenceOptimization[D]. Xi’an: Xi’an Electronic and Science University,2014.

[6] 蔡婉君,王晨宇,于濱,等.改進蟻群算法優化周期性車輛路徑問題[J].運籌與管理,2014,23(5):70-77. CAI Wanjun,WANG Chenyu,YU Bin,et al.Improved ant colony algorithm for period vehicle routing problem[J].OperationsResearchandManagementScience,2014,23(5):70-77.

[7] 王仁民,閉應洲,劉阿寧,等.改進變鄰域搜索算法求解動態車輛路徑問題[J].計算機工程與應用,2014,50(2):237-241. WANG Renmin,BI Yingzhou,LIU A′ning,et al. Improved variable neighbourhood search algorithm for DVRP[J].ComputerEngineeringandApplications,2014,50(2):237-241.

[8] 蔣波.基于遺傳算法的帶時間窗車輛路徑優化問題研究[D].北京:北京交通大學,2010. JIANG Bo.StudyofVehicleRoutingProblemwithTimeWindowsBasedonGeneticAlgorithm[D].Beijing: Beijing Jiaotong University,2010.

[9] DORIGO M,MANIEZZO V,COLORNI A. The ant system: optimization by a colony of cooperating Agents[J].IEEETransonSystems,Man,andCybernetics-PartB,1996,26(1):29-42.

[10] 于芹.基于蟻群算法的物流車輛路徑優化問題的研究[D].上海:上海交通大學,2007. YU Qin.VehicleRoutingOptimizationProblemsinLogisticsBasedonAntColonyAlgorithm[D].Shanghai: Shanghai Jiaotong University,2007.

[11] 繆興鋒,秦明森.物流運籌學方法[M].廣州:華南理工大學出版社,2007:101-102. MIU Xingfeng,QIN Mingsen.LogisticsOperationalResearchMethods[M].Guangzhou: South China University of Technology Press,2007:101-102.

[12] 段海濱.蟻群算法原理及其應用[M].北京:科學出版社,2005:33-38. DUAN Haibin.ThePrincipleofAntColonyAlgorithmandItsApplication[M].Beijing: Science Press,2005:33-38.

[13] 李婭,王東.基于混沌擾動和鄰域交換的蟻群算法求解車輛路徑問題[J].計算機應用,2013,32(2):444-447. LI Ya,WANG Dong. Ant colony optimization algorithm based on chaotic disturbance and neighborhood exchange for vehicle routing problem[J].JournalofComputerApplications,2012,32(2):444-447.

[14] 程勇.物流車輛路徑問題的混合快速螞蟻算法[J].工業工程與管理,2007(4):15-19. CHENG Yong. Hybrid fast ant algorithm for vehicle routing problem [J].IndustrialEngineeringandManagement,2007(4):15-19.

Vehicle Routing Problem Based on Hybrid Ant Colony Algorithm

LIANG Chengji, CUI Jiacheng, DING Yi

(Logistics Research Center, Shanghai Maritime University, Shanghai 201306, P.R.China)

In order to solve the vehicle routing problem (VRP), a new ant colony algorithm based on C-W saving algorithm and local search algorithm was proposed. The hybrid algorithm solved the problem of the standard ant colony algorithm to search for a long time and easy to fall into the local optimal solution. Firstly, C-W saving algorithm was introduced to improve the quality of the initial solution, which made the ant algorithm search in a better way, so it could converge to the optimal solution more effectively. And then, the pheromone of path was controlled by using max-min ant system (MMAS), which avoided the local optimal solution of the algorithm. Finally, the sub-path of optimal solution for a certain stage was optimized by using local search algorithm. The proposed hybrid ant colony algorithm was used to calculate the examples in VRPLIB database, and achieved the satisfactory results.

traffic and transportation engineering; vehicle routing problem; hybrid ant colony algorithm; max-min ant system; C-W saving algorithm; local search algorithm

10.3969/j.issn.1674-0696.2016.03.20

2014-10-28；

2015-05-04

國家自然科學基金項目(71471110,71301101)

梁承姬(1970—)，女(朝鮮族)，吉林龍井人，教授，博士，主要從事集裝箱港口物流方面的研究。E-mail:liangcj@shmtu.edu.cn。

崔佳誠(1991—)，男，上海人，碩士研究生，主要從事車輛路徑及港口集卡調度方面的研究。E-mail:tracymcgrady 06675@126.com。

U116.2

A

1674-0696(2016)03-094-06