混合蟻群算法求解帶時間窗的車輛路徑問題

王 建，李紅云，楊燕飛

Wang Jian，Li Hongyun，Yang Yanfei

（北京航空航天大學 交通科學與工程學院，北京 100191）

車輛路徑問題（Vehicle Routing Problem，VRP）是營運車輛研究領域中一個具有重要理論和現實意義的問題[1]。由于該問題屬于 NP-hard（Non-deterministic Polynomial Hard，非確定性多項式難題），所以尋找到一種高效而精確的算法的可能性微乎其微，而自然界中生物群體的合作與競爭等復雜行為產生的群體智能往往對解決某些特定的隨機尋優問題提供了高效的解決方法，因此人們開始嘗試利用仿生智能算法求解。

蟻群算法模型來源于對自然界真實螞蟻行為的觀測，蟻群在解決優化以及分布控制問題上具有很高的智能性，因此蟻群算法對解決復雜尋優問題的新型算法的開發與應用具有重要的啟發價值。蟻群算法隨機尋優機制的核心內容是分布性和協作性，而營運車輛具有同蟻群相似的分布性與協作性。目前采用蟻群算法求解車輛路徑問題已經取得了很多的研究成果[2-4]。但是蟻群算法也存在著前期收斂速度慢，容易陷入局部最優等缺點。國內外學者針對蟻群算法存在的缺點進行一系列的改進，包括Max-Min螞蟻系統，精英螞蟻系統，基于排序的螞蟻系統，基于混沌理論的螞蟻系統等[5-6]，這些改進有一個共同的目的，就是在合理時間復雜度的限制條件下，盡可能提高蟻群算法在一定空間復雜度下的尋優能力，從而改善蟻群算法的全局收斂性，并拓寬蟻群算法的應用領域。

文中對蟻群算法的分布和協作機制進行了深入研究，在分析已有蟻群系統的優缺點的基礎上提出了基于實時路況的 3層信息素更新策略，提出了考慮時間窗約束的基于多種蟻群系統的混合蟻群算法（Mixed Ant Colony Algorithm，MACO），在算法中充分考慮實時路況更新對道路通行能力的影響，以增強蟻群算法在求解動態車輛路徑問題的算法性能。

1 車輛路徑問題描述

營運車輛的調度問題屬于車輛路徑問題，但在普通的車輛路徑問題上增加了一些約束，主要體現在以下3個方面：

1）營運車輛的調度不只是單純地考慮最短路徑，同時考慮車輛運行過程中所經路徑等級、運行時間等問題，最終達到降低整體成本的目的；

2）營運車輛作為一種商業化的信息溝通形式，要充分考慮以人為本，要注重企業形象、提高顧客滿意度；

3）營運車輛數目有限，載貨量一定并且客戶的訂單具有時間要求。

營運車輛領域的車輛路徑問題可以簡單描述為：每個廠商都有一個倉庫和一批客戶集合，倉庫即是配送中心，擁有K輛可用于調度的運輸車輛，車輛的最大載重量、最大行駛距離和車況已知，每個客戶的位置信息、需求信息已知，車輛都由倉庫出發，經過若干客戶點之后返回倉庫，形成一個子回路，假如若干車輛構成的子回路集合可以完成對客戶點的不重復遍歷，那么就構成車輛路徑問題的一個可行解。通過一定的算法以及約束條件尋找可行解，并從可行解的集合中發掘滿足總行程最短或者總體成本最低的可行解就是營運車輛領域的車輛路徑問題。

鑒于營運車輛調度問題與普通的車輛路徑問題存在以上不同，同時我國“十二五”提出到2015年構建完善的營運車輛車聯網系統，以完成對路況信息的實時更新，因此有必要對蟻群算法做出一定形式的改進，以適應企業對車輛的調度。

2 基本蟻群算法模型

蟻群在覓食過程中可以通過感知和釋放一種帶有氣味的化學物質—信息素來實現相互之間的通訊交流[7]。生物學家已經指出，只要存在一種通過媒介質進行的間接傳遞信息途徑，就可以解釋蟻群如何實現有序的組織行為。蟻群算法的提出正是以此為基礎，以一種人工媒介質的形式來實現群體之間的協作溝通。

螞蟻在蟻巢與食物源之間往返，在前進和返回時都會釋放信息素，并且自然界中蟻群的實際行為也證明這是尋找較短分支所必需的行為方式。

蟻群在蟻巢與食物源之間的隨機尋優簡化模型如圖1所示。

參考圖1，假設在t時刻分別有m只螞蟻同時從蟻巢和食物源之間出發，路徑AB的長度等于路徑BC的長度，并且均為路徑AD以及DC的2倍。此時路徑ABC與路徑ADC上的信息素濃度均為τ(t)，螞蟻選擇路徑的概率嚴格與信息素濃度成線性比例關系，因此分別有p/2只螞蟻選擇ABC與ADC。當到達t+n時刻時，ADC路徑上的螞蟻已經從出發地到達目的地，然而由于路徑較長，AB路徑和BC路徑上的螞蟻在B點相遇，此時路徑ADC的信息素濃度為

而此時路徑ABC上的信息素濃度為

式中，τ(ρ)表示揮發掉的信息素數量，τ(*)表示每只螞蟻在路上經過時對路徑信息素濃度的貢獻量。

由于螞蟻選擇路徑的概率與信息素濃度成線性比例關系，因此

因此當以后的m-p只螞蟻繼續往返于蟻巢與食物源之間時，由于兩條路徑信息素濃度的不同而有越來越多的螞蟻選擇較短的路徑而達到群體尋優的效果。

3 蟻群算法改進策略

將蟻群算法的思想用于求解營運車輛路徑問題，要充分考慮客戶訂單的時間要求、位置要求等方面，因此對普通蟻群算法主要改進轉移概率，信息素濃度更新以及最終可行解的選擇3個方面。

3.1 相鄰城市轉移概率

在基本的蟻群算法中，螞蟻轉移概率只考慮道路長度和信息素濃度的影響，而在帶有時間窗的車輛路徑問題中，應綜合考慮，做到緊急訂單優先處理。因此其轉移概率為

式中，τij(t)為在t時刻路徑ij上的信息素濃度；ηij(t)為由節點i選擇j點的期望值，一般情況下取ηij(t)=1/dij，dij為客戶 ij之間的花費；ωij(t)是在 t時刻由城市i轉到城市j的滿意度影響因子；α，β，λ分別為信息素啟發因子、路徑選擇期望值影響啟發因子和滿意度影響啟發因子。顧客滿意程度與送貨時間有關，假定[aj，bj]為顧客點j的時間要求，在此范圍內送到顧客的滿意度為1，顧客能容忍的提前送到時間為，能容忍的最晚送到時間為。在提前和推遲送貨時間內將貨物送到的顧客滿意度變化符合一定的三角函數規律，如圖 2所示。

因此ωij(t)隨送貨時間的變化取值如式（6）所示。

式中，tj表示到達城市j的時間，其值等于到達顧客點i的時間加上在顧客點i的服務時間和由顧客點i到達顧客點j的路程時間。

在該轉移概率算法中，充分考慮了時間窗對顧客滿意度的影響，同時在不需要考慮時間窗的VRP問題中，通過將λ設置為0可以很方便地將顧客滿意度的影響忽略。

3.2 信息素更新策略

3.2.1 信息素揮發自適應策略

線路非直線系數是路網布局規劃中的一項重要指標。網絡兩節點（小區）間的非直線系數定義為該兩節點（小區）間的路上實際距離與兩點間空間直線距離之比。

首先統計車輛行經路徑信息，并按照所經路徑的質量，路徑質量定義為實際距離與非直線系數的函數，即

式中，Rij為m×2維矩陣，1到m分別代表顧客點i到顧客點j的路段在路網中的功能等級，ψij代表顧客點i到顧客點j的路段的非直線系數。

定義信息素揮發因子

式中，ρ(t)為自適應信息素調整因子，R(i1)表示某段路徑的功能等級數，s為道路集合。

采用自適應信息素調整后的全局信息素更新策略為

該調整因子的功能在于對道路進行排序處理，路程短且非直線系數小的道路屬于精英道路，信息素揮發較慢，有助于加快算法收斂速度，當R(i1)過大的時候，則代表此段路徑長度長且非直線系數大，此時ρ(t)有可能為負值，主要是為了避免算法陷入局部最優，使所有道路都有可能被選中。

3.2.2 考慮空間擴散特性的局部信息素更新

信息素在空氣中的濃度與距離成反比，在以往的蟻群系統中，往往對信息素的擴散更新只是局限于一條道路，文中認為信息素在空間的擴散過程是三維立體擴散，信息素的擴散對周圍道路亦產生影響，該信息素擴散策略更加忠實于自然界真實的螞蟻系統，擴散過程如圖3所示。

在簡化的信息素擴散模型中，圓心的信息素濃度為τmax時，信息素在空氣中的最大傳播距離為2rmax，根據信息素濃度與傳播距離成正比的原則可知，信源信息素濃度為τ時，信息素的最大傳播距離為。

由此可得，距離信源為ri處的信息素為

從式（10）可以看出：距離信源越遠，螞蟻所接收到的信息素就越少。

該擴散策略充分考慮了與信源的距離和中央信息素濃度的影響，同時在算法中，考慮信息素的空間擴散，更加真實地模擬自然界中信息素的擴散機制，能夠更加全面地反映路況，提高算法的收斂速度。

3.2.3 采用閾值判斷的全局信息素更新策略

蟻群算法中容易出現的停滯和擴散問題不容忽視，將各條路徑上可能的殘留信息素量限制在[τmin，τmax]之間，以避免算法陷入停滯狀態。這個信息素限制規則的作用是把位于城市 i的螞蟻選擇城市 j作為下一個訪問城市的概率 pij限制在[pmin，pmax]內，其中0

基于閾值判斷的信息素更新策略如下

假定在任何一次迭代結束之后，任意一條邊（i，j）上的信息素的最大增量為qf(s*)，因此可得在第 1次迭代中的信息素的最大值為(1-ρ)τ0+qf(s*)，在第 2次迭代之后最大值為(1-ρ)2τ0+(1-ρ)qf(s*)+qf(s*)，以此類推，考慮信息素揮發之后，第NC次迭代結束之后的信息素的值應該小于等于下式

因為0<ρ≤1，因此式（12）漸進和收斂于

每當發現一條新的最優路徑，就按照式（13）更新τmax的值，相應地，信息素的下界被設定為τmin=τmax/a，其中a是一個參數。

3.3 可行解的構造方法

由于在VRP中，每輛營運車輛所經過的只是客戶集合中的一個子回路，所有螞蟻子回路的集合構成的解有可能為可行解也有可能得不到可行解。若在有限的迭代次數內經常得不到可行解，則會造成算法的時間復雜度大幅度增加，影響車輛調度系統對車輛的有效調度，無法完成企業降低成本等方面的要求，因此文中提出當算法到達一定的迭代次數并未找到可行解時，放棄尋找可行解并轉向將所得近似解進行可行化的算法以降低計算量，防止算法陷入搜索停滯狀態。

按照文獻[8]中給出的定義，近似解有2種，分別為最大未滿非可行解和最小溢出非可行解[8]。對于未滿非可行解按照節約算法將未出現在路徑中的點插入到現有路徑中，同理對于最小溢出非可行解可以將多次出現的客戶點通過插入可行解任意一個子回路的方式抹去。

若到達一定迭代次數時沒有找到可行解，并且還存在沒有被調用過的車輛，則需要比較單獨使用未調用車輛去服務未出現的客戶點與直接將該客戶點插入至未達到最大載貨量與最大行駛距離的子回路的成本，成本較低的方案即為尋找的可行解。

若近似解已經完成對全部車輛的調用，則算法需要遍歷將未出現客戶點插入至子回路產生的成本總和，最低成本者同樣為尋找的可行解。

4 MACO算法步驟

根據上述蟻群算法改進策略，提出的 MACO算法求解步驟如下。

1）算法開始進行時，初始化MACO的參數：τmin, τmax, h, allowedk，[aj，bj]，s，R，α，β，設置迭代次數NC，初始化各條路徑上的信息素，將m只螞蟻均勻地放在 N個節點上，更新 allowedk，tabuk；

2）將 m只螞蟻放在初始節點，迭代次數NC=NC++；

3）螞蟻從allowedk中選擇下一步允許到達的城市，根據轉移概率公式進行移動；

4）判斷載重量是否已經達到極限，若是，則轉到第5步，若否，則轉到第3步；

5）螞蟻k返回原點，構成一個子回路；轉到第2步，若tabu[k]未滿，則從初始節點繼續出發；

6）根據動態揮發原則，更新局部路徑信息素；記錄本次最優路徑，更新全局信息素；

7）若Nc

8）判斷可行解是否找到，若找到，轉到第9步，若沒有找到，找到近似解，通過節約算法將近似解可行化，轉到第9步；

9）輸出結果。

5 仿真驗證

為了便于檢驗算法的性能，用改進的MACO算法在C#中進行了仿真計算。文中采用Marius M等在文獻[9]中所述的基準VRPTW實例，這些實例共有56個，這56個實例中都含有100個客戶和1個中心倉庫，并規定了車輛負載、客戶的時間窗和車輛運行時間[9]。

實驗開始，在每個城市都放置一只螞蟻，螞蟻的個數與客戶的數目相同，設置α=1.0，β=5.0，信息素揮發因子ρ=0.12，ω1=0.68，ω2=0.32，NC=40，τmax=1，τmin=0.024。

文中選取56個實例中的10個進行仿真計算，實驗結果見表1。

表1 實驗結果

仿真結果表明，算法具有快速尋優的能力，能夠在很短的時間內找到可行解或者找到近似解進行快速可行化，并且通過對實驗結果求平均值可以知道算法的尋優結果穩定，有效地改進了蟻群算法求解時間長，容易陷入局部最優的缺點。

6 結 論

文中提出的混合蟻群算法（MACO）在處理帶有時間窗的車輛路徑問題中具有計算結果穩定，跳出局部最優，計算時間短的優點。除此之外，算法還有以下優點。

1）提出的信息素揮發自適應策略能夠根據實時道路狀況調整信息素的揮發快慢，可以擴展算法完成動態調度問題；

2）將螞蟻轉移概率中的ωij設置為1可以很方便地求解不帶時間窗的車輛路徑問題或者經典旅行商問題；

3）修改迭代次數可以在保證計算量的前提下保持較好的尋優穩定性。

[1]Jose Brandao.A Tabu Search Algorithm for the Heterogeneous Fixed Fleet Vehicle Routing Problem.[J]Computers&Operations Research.2011，38（1）：140-151.

[2]Ren yingtao，Maged Dessouky，Fernando Ordonez.The Multi-shift Vehicle Routing Problem with Overtime[J].Computer&Operations Research.2010，37（11）：1987-1998.

[3]R.Tavakkoli Moghaddam，M.Gazanfari，M.Alinaghian.A New Mathematical Model for A Competitive Vehicle Routing Problem with Time Windows Solved by Simulated Annealing[J].Journal of Manufacturing Systems.2011，30（2）：83-92.

[4]Habibeh Nazif，Lai Soon lee.Optimised Crossover Genetic Algorithm for Capacitated Vehicle Routing Problem[J].Applied Methematical Modeling.2012，36（5）：2110-2117.

[5]W.Y.Szeto，Yongzhong Wu，Sin c.Ho.Anartificial Bee Colony Algorithm for the Capacitated Vehicle Routing Problem[J].European Journal of Operational Research.2011，215（1）：126-135.

[6]Zhang xiaoxia，Tang lixin.A New Hybrid Ant Colony Optimization Algorithm for the Vehicle Routing Problem[J].Pattern Recognition Letters.2009，30（9）：848-855.

[7]桑國珍，王峰，楊瑞臣.改進的蟻群算法求解VRP問題[J].現代電子技術， 2010（12）：75-77.

[8]段海濱.蟻群算法原理及其應用[M].北京：科學出版社， 2005，238-249.

[9]Marius M，Solomon M.Algorithms for Vehicle Routing and Scheduling Problems with Time Window Constrains[J].Operation Research.1987，35（2）：763-781.