改進蟻群算法求解有時間窗的物流配送路徑問題

康燕妮　嵇啟春　李武剛　李玲燕

摘 要： 物流配送車輛路徑優(yōu)化問題已被證明是一個NP難題，很難得到最優(yōu)解。應用蟻群算法對帶時間窗的物流車輛路徑優(yōu)化問題進行了算法設計，建立了車輛路徑優(yōu)化問題的蟻群算法數(shù)學模型及解決方案。通過對蟻群算法的分析，提出了改進的蟻群算法，并結合實例對該算法進行測試和分析，檢驗其有效性，結果表明了改進蟻群算法的可行性，符合實際的需要。

關鍵詞： 物流配送； 車輛路徑； 蟻群算法； 時間窗

中圖分類號：TP399 文獻標志碼：A 文章編號：1006-8228（2015）03-21-04

Abstract： Logistics distribution vehicle routing optimization problem has been proven to be a NP problem， which is difficult to get an optimal solution. The algorithm of logistics vehicle routing with time windows is designed by using ant colony algorithm. Mathematical model and solution of vehicle routing optimization are established. Through analyzing the ant colony algorithm， the improved ant colony algorithm is proposed. The algorithm is tested and analyzed by examples. The validity of the improved ant colony algorithm is ensured， proving the feasibility of the improved ant colony algorithm， which can accord with the actual needs.

Key words： logistics distribution； vehicle routing； ant colony algorithm； time windows

0 引言

隨著全球經(jīng)濟的快速發(fā)展，物流行業(yè)也得到了飛速的發(fā)展，物流配送作為物流行業(yè)最重要的環(huán)節(jié)，被越來越多的人關注和研究。首先，物流管理的內(nèi)容對整個物流運輸?shù)某杀?、效益等起著極其重要的作用；其次，物流向滿足顧客類型、數(shù)量和時間等方面的發(fā)展趨勢越來越突出。配送車輛路徑安排這一優(yōu)化問題最初由Dcmtzing & Ramser于1959年提出，一直以來，都是交通貨運和物流配送領域的一個核心問題。

在實際應用問題中，帶時間窗的車輛路徑問題（VRP With Time Windows，VRPTW）作為VRP問題的擴展，已被 Savelsbergh證明是一個NP難題，由于該問題屬于求解非常困難的組合優(yōu)化問題，具有很強的實際應用價值，長期以來吸引著大量的研究人員對其不斷地進行研究。研究人員從精確算法開始，逐漸將目光投向啟發(fā)式算法，如禁忌搜索算法、遺傳算法、蟻群算法等。鐘石泉等人[1]對軟、硬時間窗約束的VRP進行了研究，并用禁忌搜索算法分別進行求解；Chao[2]利用禁忌搜索算法求解了多車型的VRP；Chen等人[3]利用遺傳算法來處理鋼鐵領域采用半掛車運輸車輛進行物流配送中的車輛時間表制定及路徑選擇問題；唐爐亮等人[4]通過對蟻群算法的改進解決了GPS數(shù)據(jù)的公眾出行路徑優(yōu)化問題。這些算法在VRP的求解上取得了顯著的成果，但是這些算法也存在著很明顯的缺陷，如：禁止搜索算法由于涉及一些復雜領域轉換及求解策略，在現(xiàn)實中很難實現(xiàn)；模擬退火法需要結合其他一些局部搜索算法構造混合算法應用；蟻群算法、神經(jīng)網(wǎng)絡和粒子群算法易陷入局部收斂和收斂速度比較慢等。本文將基本蟻群算法進行改進，克服蟻群算中的一些缺點，使蟻群算法性能更好，得到運輸效率更高、運算結果更精確。

1 物流車輛路徑問題的模型

1.1 有時間窗車輛路徑問題的定義

對VRPTW作如下定義：從物流配送中心用多臺配送車輛向多個客戶送貨，車輛總容量一定。每個客戶的位置、需求量及需求時間給定，每個客戶只能由一臺車輛配送并且只能服務一次，要求合理安排車輛線路，使得目標函數(shù)最優(yōu)，即在符合約束條件下行駛路線長度最短。

2 車輛問題改進的蟻群算法

2.1 信息素的改進

2.1.1 信息素的動態(tài)改進

在蟻群算法中，螞蟻能夠感覺到信息素并且指導它的行為，這樣使得信息素濃度較大的路徑被螞蟻選擇的可能性相對比較大，導致該條路徑上的信息素進一步被增強，由于螞蟻的這種正反饋的作用，使得蟻群算法容易產(chǎn)生早熟、停滯現(xiàn)象。因此，本文從選擇策略方面進行改進，采用確定性和隨機性相結合的選擇策略，當搜索陷入局部最優(yōu)，則通過動態(tài)調整信息素和增強隨機選擇概率，從而有效地克服蟻群算法的早熟現(xiàn)象。

2.1.2 最大最小信息素的限定

為了避免算法過早收斂于非全局最優(yōu)解，本文提出將各條路徑可能的信息素濃度限制于[τmin，τmax]，超出這個范圍的值被強制設為τmin或者τmax，初始時刻，各條路徑上的信息素的起始濃度設為τmax，它的基本思想是基于最大最小螞蟻系統(tǒng)[5]，可以有效地避免其中某條路徑上的信息素濃度遠大于其余路徑，使得所有的螞蟻都集中到同一條路徑上，從而使算法不再擴散。

2.2 臨近候選名單列表

在蟻群算法中，當螞蟻在節(jié)點i選擇下一個節(jié)點j時，通過分析多個節(jié)點的圖，選擇離節(jié)點i最近的節(jié)點j，因此本文采用選擇最近節(jié)點的策略以改進蟻群算法的收斂速度。這種策略的基本思想是分配候選名單，每個節(jié)點i對應的候選列表存放的就是距離節(jié)點i最近的若干節(jié)點j的編號，也就是最近鄰列表。

，一只位于節(jié)點i的螞蟻將在節(jié)點i的候選列表中選擇一個它未訪問過的節(jié)點作為它下一步要訪問的節(jié)點，僅當候選列表中的所有節(jié)點都被該螞蟻訪問過后，它才會訪問不在候選列表中的其他節(jié)點，由于候選列表明顯降低了螞蟻的選擇范圍，所以可以顯著加快求解的速度[6]。同時，由于候選列表相對地加大了螞蟻選擇信息素濃度較低路徑的幾率，使得算法不容易因為信息素在局部路徑上的快速累積而過快陷入局部最優(yōu)。根據(jù)Bullnheimer[7]等人研究，候選名單的數(shù)量一般為總的客戶數(shù)量的四分之一。

3.3 其他參數(shù)

參數(shù)螞蟻的數(shù)量m的值一般取城市數(shù)量的2/3，候選名單一般為總的顧客數(shù)的1/4。

4 算法的實現(xiàn)

⑴ 初始化

設置蟻群算法參數(shù)，設置迭代次數(shù)Nc=0，將m只螞蟻置于配送中心，分別為各螞蟻做一個禁忌表，做一個候選名單，設定每條路段的初始信息素強度值為τij（0）。然后采用“蟻周模型更新規(guī)則[10]，對各路段的信息素進行更新。

⑵ 通過螞蟻的移動，形成配送路徑，并對局部信息素進行更新

每個螞蟻從配送中心出發(fā)，螞蟻根據(jù)轉移概率選擇下一個節(jié)點，若滿足容量和時間窗約束，則選擇該節(jié)點，并且將該節(jié)點記錄到禁忌表中；否則，返回到配送中心，重新開始新的路徑，直至所有客戶節(jié)點都被訪問，該螞蟻就完成了一次周游。局部更新，是指螞蟻從當前節(jié)點移動到下一個節(jié)點，就對經(jīng)過的路段進行一次信息素更新。

⑶ 局部搜索操作

在每只螞蟻構造完配送路徑以后，對配送路徑進行局部搜索操作。局部搜索操作采用2-opt方法，對可行解進行鄰域搜索，以便獲得更優(yōu)的解。

⑷ 全局更新信息素

全局更新，當所有螞蟻都完成周游以后，對最優(yōu)路徑的組成路段進行信息素更新。

⑸ 判斷終止條件

判斷Nc是否為最大迭代次數(shù)，若符合，則進入下一步；否則，返回到Step 2。

⑹ 輸出最優(yōu)解

輸出最優(yōu)解，計算結束。為了避免蟻群算法出現(xiàn)“過早收斂”的問題，本文采用“最大-最小螞蟻系統(tǒng)”[10-11]的信息素更新策略，將路段信息素量限制在[τmin，τmax]以內(nèi)。

5 案例分析

為了驗證算法的可行性，對一個隨機生成的VRPTW問題進行求解，車場和用戶均分布在100 km×100 km的范圍內(nèi)，客戶點的數(shù)據(jù)見表1，車輛的允許容量為20t，車速60km/h。采用蟻群算法參數(shù)設置如下：Q=0.9，U=100，NC=200。

三種算法測試結果如表2。200次測試中，比較三種算法的總距離與車輛數(shù)，結果表明，本文改進的蟻群算法總距離最小，并且用的車輛數(shù)也相對較少，最大最小算法次之，基本蟻群最低。平均運算時間比較，本文算法時間最短，效率最高，最大最小蟻群算法次之。綜合來看，本文提出的改進類蟻群算法車輛數(shù)最少，總距離最小，同時計算時間最短，計算效率最高。

6 結束語

本文構造了具有最小總行駛距離目標函數(shù)的VRPTW數(shù)學模型，提出了改進蟻群算法，此模型和算法有效的避免了其他方法的盲目搜索，且能達到求解質量和效率兩者的很好統(tǒng)一。通過實例驗證，該改進蟻群算法對提高求解質量和效率是很有效的。算法具有較高的正確率和較快的收斂速度，能有效地避免基本蟻群算法中存在的早熟和在局部停滯的現(xiàn)象，提高了物流配送車輛路徑系統(tǒng)的實用性。進一步的研究將考慮各客戶點的重要性權重不同、道路交通障礙不同等條件下的VRPTW問題，使之更貼近于實際應用。

參考文獻：

[1] 鐘石泉，賀國光.有時間窗約束車輛調度優(yōu)化的一種禁忌算法[J].系

統(tǒng)工程理論方法應用，2005.14（6）：523-527

[2] Chao Yiming. A tabu search method for the truck and trailer

routing problem[J]. Computer and Operations Research，2002.29（1）：33-51

[3] Chen Yaorong， Liang Bo， Zhou Meihua.Optimization for vehicle

scheduling in iron and steel works based on semi-trailer swap transport[J].中南大學學報：英文版，2010.17（4）：873-879

[4] 唐爐亮，常曉猛，李清泉等.基于蟻群優(yōu)化算法與出租車 GPS數(shù)據(jù)的

公眾出行路徑優(yōu)化[J].中國公路學報，2011.24（2）：89-95

[5] T.Stutzle， H.H.Hoos， The MAX-MIN ant system and local search

for the traveling salesman problem， in：Proceedings of the IEEE International Conference on Evolutionary Computation，1997：309-314

[6] Dorigo M，Cambardella L M.Ant colony system： a cooperative

learning approach to the traveling salesman problem[J]. IEEE Transactions on Evolutionary Computation，1997.1（1）：317-365

[7] B.Bullnheimer， R.F.Hartl， C. Strauss， An improved ant system algorithm for the vehicle routing problem， Ann. Oper. Res. 89，1999：

319-328

[8] Hasegawa M， IkeguchiT， Aihara K .Combination of chaotic

neurodynamics with the 2-opt algorithm to solve traveling salesman problems[J]. Physical Review Letters，1997.79（12）：2344-2347

[9] Rocki K， Suda R. Accelerating 2-opt and 3-opt local search using

GPU in the Travelling Salesman Problem[C]. High Performance Computing and Simulation （HPCS）， 2012 International Conference on. IEEE，2012：489-495

[10] 李士勇，陳永強，李研.蟻群算法及其應用[M].哈爾濱工業(yè)大學出版

社，2004.

[11] STUTZLET， HOOS H H. Max-min ant system[J]. Future

Generation Computer Systems，2000.16（8）：889-914