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

梁承姬，崔佳誠，丁 一

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

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

梁承姬，崔佳誠，丁 一

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

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

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

0 引 言

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

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

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

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

1 VRP數(shù)學模型

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

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

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

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

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

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

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

符號的定義：L為客戶點總數(shù)；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為總車輛的數(shù)目；Qk為車輛k的最大載重，其中k=1，2,…，K；nk為車輛k完成配送的客戶總數(shù)，當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

優(yōu)化目標函數(shù)：

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

(4)

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

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

2.1 算法說明

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

2.1.1 節(jié)約算法

節(jié)約算法運用在車輛路徑問題中的基本思路是首先把各個客戶點單獨與配送中心相連，構(gòu)成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)，計算出這兩點連接后費用的“節(jié)約值”：

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

(6)

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

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

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

2.1.2 最大最小螞蟻系統(tǒng)

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

最大最小螞蟻系統(tǒng)在螞蟻系統(tǒng)的基礎(chǔ)上有4項主要的改進[12]。

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

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

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

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

2.1.3 鄰域搜索算法

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

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

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

2.2 算法步驟

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

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

(7)

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

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

(8)

式中：Lb為最優(yōu)螞蟻行駛過的路徑的長度，所以增加的信息素為距離的倒數(shù)；ρ為信息素的揮發(fā)。

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

(9)

τmin=τmax×τrate

(10)

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

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

5)根據(jù)概率公式：

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

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

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

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

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

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

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

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

3 計算實例與結(jié)果分析

3.1 計算實例1

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

表1 客戶及配送中心數(shù)據(jù)

表2 各算法比較

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

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

3.2 計算實例2

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

表3 VRPLIB中問題的計算結(jié)果

Table 3 Calculation results of the problems in VRPLIB

4 結(jié) 語

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

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

[2] 盛麗俊,周溪召.帶有時間窗的車輛路徑問題優(yōu)化[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] 吳思,丁以中.計重收費政策下的貨物權(quán)重車輛路徑[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] 蔡婉君,王晨宇,于濱,等.改進蟻群算法優(yōu)化周期性車輛路徑問題[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] 王仁民,閉應洲,劉阿寧,等.改進變鄰域搜索算法求解動態(tài)車輛路徑問題[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] 蔣波.基于遺傳算法的帶時間窗車輛路徑優(yōu)化問題研究[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] 于芹.基于蟻群算法的物流車輛路徑優(yōu)化問題的研究[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].工業(yè)工程與管理,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—)，男，上海人，碩士研究生，主要從事車輛路徑及港口集卡調(diào)度方面的研究。E-mail:tracymcgrady 06675@126.com。

U116.2

A

1674-0696(2016)03-094-06