鄧 波，蒲保興

(邵陽學院 信息工程學院，湖南 邵陽，422000)

基于改進蟻群算法的物流配送路徑優(yōu)化研究

鄧 波，蒲保興

(邵陽學院 信息工程學院，湖南 邵陽，422000)

物流配送行業(yè)不但要求所有貨物能及時進行配送，而且也要求盡可能降低整個物流運輸成本。所以物流配送車輛路徑優(yōu)化問題是重點亟待解決的關鍵問題，由于傳統(tǒng)的優(yōu)化方法搜索時間較長，且難以找到全局最優(yōu)路徑，從而造成配送成本高，效率低。為了降低成本，提高車輛路徑優(yōu)化率，本文以蟻群算法為基礎，并加以改進，首先建立優(yōu)化物流配送路徑的全局數學模型,然后采用改進信息素更新規(guī)則、改進啟發(fā)信息更新策略獲取最優(yōu)物流路徑，通過優(yōu)選算法參數，改進蟻群算法對全局數學模型進行求解。從而有效避免只有局部優(yōu)化解的出現。仿真實驗結果表明，改進后的算法效率提高較大，算法在實驗環(huán)境下收斂性好，是解決物流配送路徑優(yōu)化問題的有效算法。

物流配送；蟻群算法；路徑優(yōu)化；仿真；VRP

隨著社會實體經濟的高速發(fā)展，整個物流行業(yè)也得以快速發(fā)展，物流行業(yè)中的物資配送越發(fā)成為當今企業(yè)生產過程中一個非常重要環(huán)節(jié)，物流配送指的是依照用戶的訂單要求,并在配送中心進行準確地分貨、配貨，然后將配好的貨物及時送交給用戶的活動[1]。由于油價、人力資源等成本的不斷上漲，物流運輸費用已逐漸成為商家成本主要部分，又由于現代擁擠的城市交通與及時物資配送服務之間存在著難以調和的矛盾，因而優(yōu)化物流車輛路徑相對于整個物流效益、速度以及運輸成本都顯得至關重要，因此怎樣選擇最優(yōu)配送路徑，及時將貨物配送到用戶手中，也已成為物流行業(yè)相關領域里的關鍵問題[2]。

配送車輛路徑問題(vehicle routing problem，VRP)的關鍵是整個物流系統(tǒng)優(yōu)化環(huán)節(jié)。通過系統(tǒng)選擇配送車輛的最佳輸送路徑，并對運輸車輛調度進行優(yōu)化，合理安排配送車輛配送順序，可以減少車輛的行駛距離和空駛率。在物流配送中，存在很多決策優(yōu)化問題(例如距離、時間、費用等)[3]，大部分僅探討物流配送路徑的優(yōu)化問題，即在滿足客戶需求的前提下，制定出合理的貨物配送路徑，通過派遣數量最少的車輛并為配送車輛指派運輸時間和運輸最省的路線費用，迅速地將貨物輸送客戶手中。優(yōu)化配送路徑其實是一個NP問題，只有當客戶節(jié)點和線路較少時，才能求得精確解，然而當問題的規(guī)模增大時，精確求解會存在耗時較長，并且效果低現象；而采用人機互動法，又需要管理者具備足夠的物流配送專業(yè)知識，且會增加對車輛配送路徑選擇的隨意性[4]。對于這類問題的求解一般應采用啟發(fā)式算法，該算法是指通過對已經解決具體問題的經驗不斷進行歸納、分析、推理，并產生解決此類問題的方法[5]。其目標是在適當的代價下得到即將要解決的全局問題的滿意解或最優(yōu)解，這樣不但節(jié)省了時間，也會滿足用戶的實際要求。又由于啟發(fā)式算法具有效率高、實現簡單等多種優(yōu)點，所以引起了當今優(yōu)化研究領域的廣泛關注，近年來發(fā)展非?？臁?/p>

蟻群算法是一種群智能優(yōu)化算法，該算法是通過正反饋并行機制和螞蟻間協(xié)作定能找到巢穴與食物之間的最短路徑[6]。蟻群算法一被提出就受到研究領域的廣泛關注，因為該算法不但具有并行性好、求解速度快等優(yōu)點，而且在解決路徑優(yōu)化、任務分配等方面表現出優(yōu)良的性能，但是蟻群算法同時也存在一定的缺陷，例如當問題變成大規(guī)模時，就會出現運算時間長、收斂速度較慢、容易陷入局部最優(yōu)解等現象[7，8]。

1 構建VRP數學模型

假定某個物流公司具有N個客戶以及M個集散中心，物流車輛配送路徑的目標是要在使配送成本最小的情況將貨物從M個集散中心送到N個客戶點上。在車載量q和客戶需求量gi(i=1,2…n)均已知的前提下，可以確定至少應派多少臺車才能滿足應用需求且車輛所經的總路徑最短，從而找到配送方案中最小成本的方案，在進行數學模型構建時首先作如下假設：

1)車輛對每個客戶點服務，途中只卸貨無裝貨的情況。

2)每一臺配送車輛均以同一集散中心為起點和終點。

3)車載量要大于每條配送路徑上客戶量之和(q>gi)。

4)每輛車只服務一條路線，每一個客戶只被一輛車配送。

5)每輛配送車所經過的路線均不能重復。

可以由下列公式求得所需車輛數目m:

(1)

其中：m表示所選擇車輛數，a是參數，且0

建立物流配送路徑選擇問題的求解數學模型。首先定義以下變量：

Xik=1 (客戶i的配送由車輛k完成，i、K分別表示客戶、車輛的編號)

(2)

或Xik=0 (客戶i的配送車輛k未完成配送)

Yijk=1 (車輛k從i客戶點行駛到j客戶點完成)

(3)

或Yijk=0(車輛k從客戶點i行駛到客戶點j未完成)

(4)

minZ=∑i∑j∑kCijYijk

(5)

設置如下限制條件：

∑iYki=1i=1,2,…,m

(6)

∑iGiXki≤qi=1,2…,m?k

(7)

∑jXkijk=Ykii=0,1,…,?k

(8)

∑iYkijk=Ykjj=0,1,…,?k

(9)

X=Xijk∈S

(10)

Xijk=0或1i,j=0,1,…,?k

(11)

Yki=0或1i,j=0,1,…,?k

(12)

上述條件約束了車輛的配送總容量，其中，Cij表示從點i到點j的所有運輸成本，Gi表示任務i的運輸量，q表示貨物配送總容量，所有貨物運輸任務均由m臺配送車輛去完成，保證每個客戶的所有貨物僅由唯一臺輛車來配送完成，即保證了服務的唯一性[9]。

2 蟻群算法的改進

通過專家們多年來的研究，蟻群算法的應用研究已經取得了較大進展，在各種工程領域中得以廣泛應用，但由于該算法收斂速度慢，且容易陷入局部最優(yōu)解等多種缺點。作者力求通過對局部信息素更新規(guī)則的改進，優(yōu)化組合動態(tài)調整相關參數和全局更新策略，實現算法優(yōu)化，從而提高了蟻群算法的收斂速度，達到了增強全局搜索的隨機性，極大地抑制了算法出現早熟現象。

2.1 信息素更新規(guī)則改進

在所研究基本蟻群算法中，發(fā)現存在兩種信息素更新策略，即實時更新、全局更新。前者是指螞蟻在從一個節(jié)點完成到達另一節(jié)點后，就馬上更新路徑的信息素;而后者是指螞蟻在遍歷完所有節(jié)點后才更新整條路徑上的信息素。這兩種方式相比較，全局更新策略可以迅速加快收斂速度。目前很多研究已表明全局更新效果好，但同時也有一些缺陷，例如該方法下全局更新通常收斂過早，在同一條路徑上會使大量螞蟻很快集中，從而無法發(fā)現和得到更優(yōu)解，也即陷入局部最優(yōu)解情況[10]。

在信息素更新過程中，系統(tǒng)通常只會更新找到最優(yōu)路徑的螞蟻的信息素。對于這只螞蟻信息素的更新，通?？刹捎靡韵聝煞N方式進行，一種是在循環(huán)過程中找到表現最佳的螞蟻，該方式的收斂速度通常比較慢，不會過早導致迅速收斂到某條路徑上，蟻群還會繼續(xù)去找新的路徑，也就更易于去發(fā)現更好的路徑；另一種則是找到在整個運算中表現最佳的螞蟻，該更新方式可以迅速提高收斂速度，從而得到較優(yōu)解，但這也阻礙了蟻群再去尋找更優(yōu)解，容易使整個蟻群困在相對較差的某路徑上。因此，本文提出了一種新的混合更新信息素策略，也即在搜索前幾次循環(huán)過程中，采用迭代最優(yōu)法不斷進行及時信息素更新，進行信息素更新是為發(fā)現本輪循環(huán)中表現最佳的螞蟻，該方法通?？煞奖阏业胶芏噍^優(yōu)解，可有效避免蟻群過早陷入到較差解中；經多次循環(huán)(在此以十次循環(huán)為例)完成更新以后，然后再采用全局最優(yōu)解進行更新，也即信息素更新是利用整個運算以來最佳表現的螞蟻來進行的。在混合信息素更新規(guī)則被采用后，本算法會收斂到較優(yōu)解集中，從而也就可以找到更多可行解，并且還能繼續(xù)去搜尋其他更優(yōu)解，并且保持著快的收斂速度，可有效地去克服采用單一全局更新時易過早出現陷入局部最優(yōu)解的不足。

改進后信息素更新規(guī)則如下:

τij(t+1)=(1-ρ)×τij(t)+Δτbest

(13)

其中：Δτbest= 1 /f(sbest)；全局最優(yōu)解sob用f(sbest)、本次迭代所得最優(yōu)解用sib表示。再則為了防止搜尋停滯，應將路徑上的信息素限定在某個可以預定的范圍之內，而對于全部信息素τij(t)都必須滿足

τij(t)∈[τmin，τmax]，如果τij(t)≥τmax，那么將設置為τij(t)=τmax，如果

τij(t)≤τmin，那么將設置為τij(t)=τmin，如果在某個迭代過程中產生了可行解，且其信息素的量是τmax，而其他路徑上信息素的量卻是τmin，那么收斂就會出現?？梢詣討B(tài)地按照以下策略進行信息素的改進：

1)在初始狀態(tài)下，信息素未加以更新，采用式(7)、(8)來確定初始更新范圍，其中L(sbest)表示全局最優(yōu)解或本次迭代所得最優(yōu)解，而每次迭代運算過程中出現新增的信息素最高值則用1 /L(sbest)表示。

(14)

(15)

2)若信息素更新完成后，則開始采用式(16)來確定τmax(t)，而τmin(t)仍采用式(15)來確定。

(16)

2.2 啟發(fā)信息更新策略的改進

在進行路徑規(guī)劃時，可以根據式(5)來進行相應路徑選擇，但式(5)中只反映了當前結點與其相鄰接結點之間的關系，并沒有反映出其鄰接結點與終點之間的關系，它搜索的空間是以起點為中心近似圓形的區(qū)域，由于這種沒有方向性的搜索很容易造成搜索失敗或收斂速度過慢等原因。為此，可將與當前結點i相鄰的下一可選結點j到終點z的直線距離djz引入啟發(fā)函數，這樣得到

(17)

定義在t時刻第k只螞蟻從位于節(jié)點i上選擇下一個j節(jié)點為目標的概率為:

ifj∈allowedk

(18)

這里,ηij是由i轉移到j的啟發(fā)信息，由要解決的問題函數給出。參數α和參數β分別用來表示控制信息素濃度以及啟發(fā)信息相對重要程度。而allowedk表示第k只螞蟻下一步可選擇所有節(jié)點的集合[11]。

通過將djz引入到啟發(fā)函數，改變了無向搜索，使搜索的方向性加強，搜索的空間也轉化為由起點到終點的橢圓形區(qū)域，縮小了搜索區(qū)域，搜索的成功率大大提高，然而，對于實際道路交通狀況，由于交通環(huán)境(如快速路、高速路)等因素的影響，該方向啟發(fā)的方法并不一定得到最優(yōu)路徑，這是因為方向啟發(fā)的過早所致，使得初始搜索空間有限，為此，特引入當前結點i與起點o之間的直線距離dio作為初始搜索空間的大小，等搜索到一定的程度以后再引入方向啟發(fā)進行搜索空間縮減，從而在利用蟻群算法進行路徑規(guī)劃時，首先應按基本蟻群算法去進行路徑搜索，當距離dio大于給定的閾值ε時，應采用式(15)來進行具有方向啟發(fā)的路徑搜索，確定了方向，不僅提高了搜索到最優(yōu)路徑的可能性，而且也盡可能地縮減了搜索空間，因此提高了該算法的執(zhí)行效率[12]，對于起點o與當前結點i的直線距離閾值ε應根據地方區(qū)域規(guī)模來加以確定，常見的方法是參照起點o與終點z直線距離dOz進行確定。

3 改進后的蟻群算法實現步驟

算法改進后的詳細流程實現步驟如下:

步驟1 首先對參數進行初始化。設Nc= 0(Nc表示迭代次數)，并設置最大迭代次數為Ncmax，初始化信息素強度Q，設置最大信息素強度為τmax、最小信息素強度為τmin和α、β的值，每條路徑上的信息素濃度值τij(0)=c(c為常數)，并設置Δτij= 0，然后隨機將m個螞蟻放置到初始點上。

步驟2 設置循環(huán)搜索次數Nc，其值變化趨勢Nc=Nc+ 1。

步驟3 設置螞蟻禁忌表，將禁忌表的索引號設成n，并且n= 1。

步驟4 設置螞蟻數目m，其數目的變化趨勢為m=m+ 1。

步驟5 確定搜索熱區(qū)，判斷某路徑是否在熱區(qū)以內，然后計算出每一只螞蟻移動到下一條路徑的概率值。

步驟6 當螞蟻從某節(jié)點i出發(fā)到達下一節(jié)點j時，應當對其所經全部路徑上的信息素及時進行更新并及時修改禁忌表，然后按照當前狀況將修改禁忌表值，并將新節(jié)點j也置于禁忌表中。

步驟7 循環(huán)執(zhí)行步驟 2到步驟 6 ，一直到每只螞蟻都能找到一條包含區(qū)域內所有節(jié)點的可行路徑。

步驟8 并在新搜索到的所有可行解集內產生一條最短路徑，即這條路徑就是本次迭代產生的最優(yōu)路徑。

步驟9 不斷判斷循環(huán)次數Nc，只要循環(huán)次數沒有超過十次，則一直對螞蟻所找到的最優(yōu)路徑依照本迭代最優(yōu)值法去進行信息素更新；如果循環(huán)次數已經超過十次，則立即按照全局更新進行信息素更新。

步驟10 對全部螞蟻經過的任何一條路徑，都必須按式(11)到(14)進行一次全局更新信息素。

步驟11 重復執(zhí)行步驟2到步驟7 ，直到在連續(xù)的多次迭代中沒有出現更優(yōu)解或者次數Nc的值已經達到最大的迭代次數Ncmax，才停止運算，然后將當前值作為算法最優(yōu)解。

4 仿真實驗研究

通過以上對算法加以改進和詳細流程的介紹，本實驗將用測試數據對改進后的蟻群算法進行仿真，通過對測試結果進行分析，評價改進算法的好壞。

4.1 數據集

已知某物流公司的有 8臺配送車，每臺車的最大載重量為10噸，每臺車的最大行駛距離100公里，需同時向 30個客戶提供服務，物流配送中心與客戶的基本資料及位置情況如表1與圖1所示。

表1 客戶基本資料表

4.2 仿真平臺及參數優(yōu)化設置

仿真系統(tǒng)的運行平臺為：CPU為2.6GMHz，內存為4GB，OS為windows 7，采用VB6.0 語言編程實現。蟻群算法的參數設置如下：螞蟻最大數目為100，α= 1，β= 1.5，實驗進行了10次，最大迭代次數為 200，ρ= 0.85。

圖1 客戶地理位置信息圖Fig.1 Customer location information map

4.3 仿真實驗所得結果與分析

4.3.1 算法改進前后的最優(yōu)車輛路徑搜索結果

采用改進后的蟻群算法對最優(yōu)配送路徑進行求解，可用3臺車3個路徑即可完成，改進前，在迭代60次時，就產生局部最優(yōu)解，最短路徑為220公里，而改進后，按此算法在迭代100次時，就找到了問題全局最優(yōu)解，最優(yōu)路徑長度為200公里，從仿真實例中可以看出，改進后，它能夠以更快的速度收斂到全局最優(yōu)解，也就是說本算法是一種有效的配送車輛路徑優(yōu)化方法。最短路徑的收斂情況如圖2所示。

圖2 基本蟻群算法改進前后的收斂曲線Fig.2 The basic ant colony algorithm improves the curve of convergence before and after

4.3.2 算法改進前后對比分析

從圖2可以看出，改進后的蟻群算法最優(yōu)路徑長度比改進前減少了20 km，而且收斂速度快了很多，所以無論是從收斂速度還是對最終結果進行比較，本文算法都要優(yōu)于基本蟻群算法，基本蟻群算法容易停滯于局部最優(yōu)解上的問題在改進后的算法中得到了有效的解決?？梢?，本文改進后的蟻群算法具有較大的優(yōu)越性，也證明了改進后的蟻群算法的正確性和有效性。本例是在單一物流配送中心的情況下求解的，若是存在多個物流配送中心，則只需將多個配送中心通過分解法來進行區(qū)域劃分，然后進行各自獨立求解即可，所得解可能不是全局最優(yōu)解，但仍然還是非常有效的、可行的。

5 結束語

物流中規(guī)劃好車輛配送路徑是提高物流企業(yè)經濟效益的關鍵，本文通過對基本蟻群算法進行改進，包括啟發(fā)信息更新的改進、信息素更新的改進等，設計出新的改進蟻群算法，針對物流系統(tǒng)當前存在的問題，對車輛路徑優(yōu)化問題進行了深入研究，并利用蟻群算并行性度、高法速度快、魯棒性強的特點，創(chuàng)造性提出了基于蟻群算法的車輛配送路徑優(yōu)化問題的求解方法。在通過仿真實驗對其進行驗證后，其試驗結果表明改進后的方法可以很好地提高效率，并能夠非?？焖俚卣业剿惴ㄗ顑?yōu)解，因而在以后車輛路徑優(yōu)化中肯定會展現出廣闊的市場前景。

[1]唐爐亮，常曉猛，李清泉，等.基于蟻群優(yōu)化算法與出租車GPS 數據的公眾出行路徑優(yōu)化[J].中國公路學報，2011，24(2):89-95.

[2]余玥,胡宏智.基于改進遺傳算法的物流配送路徑求解[J].計算機技術與發(fā)展,2009,19(3):52- 55.

[3]CHEN Yaorong，LIANG Bo，ZHOU Meihua.Optimization for vehiclescheduling in iron and steel works based on semi-trailer swap transport[J].中南大學學報:英文版，2010，17(4):873-879.

[4]鐘石泉，賀國光.有時間窗約束車輛調度優(yōu)化的一種禁忌算法[J].系統(tǒng)工程理論方法應用，2005，14(6):523-527.

[5]CHAO Yiming.A tabu search method for the truck and trailer rou-ting problem[J].Computer and Operations Research，2002，29(1):33-51.

[6]姜宏岸，王剛.優(yōu)先級隊列的緩存管理機制的性能分析[J].計算機工程與應用，2009，45(25)：86-88.

[7]宋留勇，王銳，周永旺，等.動態(tài)城市交通網絡優(yōu)化模型研究及算法設計[J].測繪科學，2011，36(1):134-136.

[8]程明輝,齊名軍.基于粒子群算法的物流配送路徑優(yōu)化問題研究[J].中國外資,2008,(8):254- 256.

[9]陳以,萬梅芳.RBF神經網絡在物流系統(tǒng)中的應用[J].計算機仿真,2010,27(4):159- 163.

[10]SEO JB，LEUNG V.Approximate queuing performance of amultipacket reception slotted ALOHA system with an ex-ponentialbackoff algorithm[C]∥4th International Conference on Communications and Networking in China，2009:1-5.

[11]楊中秋，張延華.改進蟻群算法在交通系統(tǒng)最短路徑問題的研究[J].科學計算與信息處理，2009，32(8):76-78.

[12]KARSTEN M.FIFO service with differentiated queueing[C]∥7th ACM/IEEE Symposium on Architectures for Networking and Communications Systems，2011:122-133.

Logistics distribution path optimization research based on improved ant colony algorithm

DENG Bo,PU Baoxing

(School of Information Engineering,Shaoyang University,Shaoyang 422000,China)

Logistics industry can not only requires that all the goods in a timely manner and distribution,but also the requirement as far as possible to reduce the logistics cost.So the logistics distribution vehicle routing optimization problem is focused on the key problems to be solved,due to the traditional optimization method to search for a long time,and hard to find the global optimal path,resulting in the distribution cost is high,the efficiency is low.In order to reduce costs,increase the rate of vehicle routing optimization,in this paper,based on the ant colony algorithm,and improved it,the first to establish the mathematical model of the logistics distribution path of global optimization and then with the improved pheromone update rule,improvement of heuristic information update strategy,obtain the optimal logistics path,through the parameter optimization algorithm,ant colony algorithm for solving global mathematical model.Thus effectively avoid the occurrence of only local optimization solution.The simulation experimental results show that the improved algorithm efficiency is larger,convergence algorithm in experiment environment is good,and it is effective to solve the problem of logistics distribution route optimization algorithm.

logistics distribution;ant colony algorithm;path optimization;simulation;VRP

1672-7010(2017)04-0069-07

2017-04-21

湖南省科技計劃項目(2012FJ3108)；湖南省教育廳科學研究項目(13C845)

鄧波(1973-)，男，湖南邵陽人，講師，碩士，從事嵌入式系統(tǒng)、數據挖掘研究蒲保興(1965-)，男，湖南城步人，教授，博士，碩導，從事網絡安全、數據挖掘研究

TP311

A