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

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

關(guān)鍵詞： 物流配送； 車輛路徑； 蟻群算法； 時(shí)間窗

中圖分類號(hào)：TP399 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：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)濟(jì)的快速發(fā)展，物流行業(yè)也得到了飛速的發(fā)展，物流配送作為物流行業(yè)最重要的環(huán)節(jié)，被越來(lái)越多的人關(guān)注和研究。首先，物流管理的內(nèi)容對(duì)整個(gè)物流運(yùn)輸?shù)某杀?、效益等起著極其重要的作用；其次，物流向滿足顧客類型、數(shù)量和時(shí)間等方面的發(fā)展趨勢(shì)越來(lái)越突出。配送車輛路徑安排這一優(yōu)化問(wèn)題最初由Dcmtzing & Ramser于1959年提出，一直以來(lái)，都是交通貨運(yùn)和物流配送領(lǐng)域的一個(gè)核心問(wèn)題。

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

1 物流車輛路徑問(wèn)題的模型

1.1 有時(shí)間窗車輛路徑問(wèn)題的定義

對(duì)VRPTW作如下定義：從物流配送中心用多臺(tái)配送車輛向多個(gè)客戶送貨，車輛總?cè)萘恳欢āＣ總€(gè)客戶的位置、需求量及需求時(shí)間給定，每個(gè)客戶只能由一臺(tái)車輛配送并且只能服務(wù)一次，要求合理安排車輛線路，使得目標(biāo)函數(shù)最優(yōu)，即在符合約束條件下行駛路線長(zhǎng)度最短。

2 車輛問(wèn)題改進(jìn)的蟻群算法

2.1 信息素的改進(jìn)

2.1.1 信息素的動(dòng)態(tài)改進(jìn)

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

2.1.2 最大最小信息素的限定

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

2.2 臨近候選名單列表

在蟻群算法中，當(dāng)螞蟻在節(jié)點(diǎn)i選擇下一個(gè)節(jié)點(diǎn)j時(shí)，通過(guò)分析多個(gè)節(jié)點(diǎn)的圖，選擇離節(jié)點(diǎn)i最近的節(jié)點(diǎn)j，因此本文采用選擇最近節(jié)點(diǎn)的策略以改進(jìn)蟻群算法的收斂速度。這種策略的基本思想是分配候選名單，每個(gè)節(jié)點(diǎn)i對(duì)應(yīng)的候選列表存放的就是距離節(jié)點(diǎn)i最近的若干節(jié)點(diǎn)j的編號(hào)，也就是最近鄰列表。

，一只位于節(jié)點(diǎn)i的螞蟻將在節(jié)點(diǎn)i的候選列表中選擇一個(gè)它未訪問(wèn)過(guò)的節(jié)點(diǎn)作為它下一步要訪問(wèn)的節(jié)點(diǎn)，僅當(dāng)候選列表中的所有節(jié)點(diǎn)都被該螞蟻訪問(wèn)過(guò)后，它才會(huì)訪問(wèn)不在候選列表中的其他節(jié)點(diǎn)，由于候選列表明顯降低了螞蟻的選擇范圍，所以可以顯著加快求解的速度[6]。同時(shí)，由于候選列表相對(duì)地加大了螞蟻選擇信息素濃度較低路徑的幾率，使得算法不容易因?yàn)樾畔⑺卦诰植柯窂缴系目焖倮鄯e而過(guò)快陷入局部最優(yōu)。根據(jù)Bullnheimer[7]等人研究，候選名單的數(shù)量一般為總的客戶數(shù)量的四分之一。

3.3 其他參數(shù)

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

4 算法的實(shí)現(xiàn)

⑴ 初始化

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

⑵ 通過(guò)螞蟻的移動(dòng)，形成配送路徑，并對(duì)局部信息素進(jìn)行更新

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

⑶ 局部搜索操作

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

⑷ 全局更新信息素

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

⑸ 判斷終止條件

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

⑹ 輸出最優(yōu)解

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

5 案例分析

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

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

6 結(jié)束語(yǔ)

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

參考文獻(xiàn)：

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

統(tǒng)工程理論方法應(yī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].中南大學(xué)學(xué)報(bào)：英文版，2010.17（4）：873-879

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

公眾出行路徑優(yōu)化[J].中國(guó)公路學(xué)報(bào)，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] 李士勇，陳永強(qiáng)，李研.蟻群算法及其應(yīng)用[M].哈爾濱工業(yè)大學(xué)出版

社，2004.

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

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