基于蟻群算法的緊急物流配送路徑優化設計

[摘 要] 本文將結合應急物流的配送車輛優化調度問題，根據應急物流配送的突出特點，對應急物流配送車輛調度路線優化進行探討，建立了應急物流配送車輛調度模型，用蟻群算法對車輛的配送路徑進行優化。

一、引言

近些年無論是自然災害還是各種事故災害，公共災害等各類突發事件爆發頻繁，而且規模都很大。突發性重大自然災害和公共衛生事件造成巨大的人員傷亡和財產損失，必然需要大量的應急物資，以解決傷者救助、衛生防疫、恢復生產等，否則受災面積、人員、損失將會擴大。因此選擇距離最短、費用最少和時間最快的配送路徑顯得格外重要。目前國內關于物流調度方面作了一些研究，但是關于應急物流配送車輛調度問題研究還很少。鑒于物流調度的研究方法，其中有傳統的方法，比如，數學規劃，分支定界法等。不過這些方法只能基于某些簡化的假設因而不能適應實際的需要.智能調度方法，如專家系統、神經網絡和遺傳算法在使用中盡管有優點，但也有明顯的缺點。根據以上問題，本文將結合應急物流的配送車輛優化調度問題，根據應急物流配送的突出特點，對應急物流配送車輛調度路線優化進行探討，建立了應急物流配送車輛調度模型，用蟻群算法對車輛的配送路徑進行優化。

二、問題描述

物流配送路徑優化是指對一系列裝貨點(或卸貨點)，組織適當的行車線路，使車輛有序地通過它們，在滿足一定的約束條件(如貨物需求量、發送量、交發貨時間、車輛容量限制、行駛里程限制、時間限制等)下，達到一定的目標，使總代價最小(如路程最短、費用最少、時間盡量少、使用車輛盡量少等)，并且同時滿足以下條件及假設:各個需求點的位置和需求量為已知，尋找一個優秀的配送方案，使得總代價最小。

1.約束條件

(1)所有節點之間都有路線相通。(2)各救災點與各受災地點、各受災地點之間的運輸距離作為已知量。(3)每個受災地點對救災物資的需求是必須在規定時間送到。(4)所有的受災地點的需求，在物資數量方面和運輸時間方面都能夠得到滿足。(5)單個需求節點的需求量小于單車車容量。(6)為簡化問題描述，假設車輛所在車場到物資儲備中心的距離忽略不計。

2.數學模型

在上述條件下指派運輸車輛以期達到總的運輸距離最短，從而降低應急物流的運輸成本。應急物流配送車輛調度模型如下。

目標函數:

(1)

Min k(2)

約束條件:

i=0，1，2，…，n(3)

RTi≤LTii=0，1，2，…，n (4)

i=0，1，2，…，n (5)

i，j=0，1，2，…，n (6)

i，j=0，1，2，…，n (7)

X=(xik)∈D (8)

k≤n(9)

公式中符號說明:

(1)dij表示為從節點i到節點j的運輸距離，當i，j=0時表示該節點為救災點，否則為受災點。

(2)。

(3)k表示車輛數量;q表示單車車容量lgi(i≠0)表示第i個受災節點對于救災物資的需求量;。

(4)RTi表示車輛到達i點的時刻;LTi表示最遲允許車輛到達時刻。

三、蟻群算法原理

蟻群算法是意大利學者M·Dorigo等提出的一種仿生尋優算法，它通過模擬自然界蟻群從巢穴到食物源的最短路徑的覓食過程來求解一些NP難題。蟻群算法是一種通用型隨機優化算法，對問題的求解沒有苛刻的限制使用條件，可以在非常困難的條件下搜索到組合問題的最優解或較優解，在很多經典的組合優化領域上都有較好的應用，如旅行商問題(TSP)和非對稱旅行商問題(ATSP)、作業車間調度問題(JSP)。蟻群算法是通過信息素的積累和更新來尋求最優解。螞蟻有能力在沒有任何提示下找到從巢穴到食物源的最短路徑，并且能隨環境的變化而變化，適應性地搜索新的路徑，產生新的選擇。其根本原因是螞蟻在尋找食物源時，在其走過的路上釋放一種特殊的分泌物——信息素，后來的螞蟻選擇該路徑的概率與當時這條路徑上該物質的強度成正比。當它們碰到一個沒有走過的路口時，就隨機地挑選一條路徑前行，與此同時釋放出與路徑長度有關的信息素。路徑越長，釋放的信息素濃度越低。當后來的螞蟻再次碰到這個路口時，選擇信息素較高路徑的概率就會相對較大。而當一定路徑上通過螞蟻越來越多時，其留下的信息素軌跡也越來越多，后來的螞蟻選擇該路徑的概率也越高，從而更增加了該路徑的信息素強度。而強度大的信息素會吸引更多的螞蟻，從而形成一種正反饋機制。螞蟻的路徑搜索原理如圖所示，有兩條支路ACB和ADB，支路ACB中節點A和B各有兩只螞蟻，其中螞蟻1、2由A向B行進，而3、4則由B向A行進。假設螞蟻速度相同，當螞蟻2和螞蟻4經過支路ADB分別到達節點B和A，而螞蟻1和3還在支路ACB的途中。顯然，支路ADB留下的信息素的痕跡濃度要高于支路ACB上的信息素濃度，所以當再有螞蟻到達點A和B時，它們選擇支路ADB的概率就會更大，從而增加支路ADB上的信息素痕跡的濃度，形成正反饋，這樣螞蟻可以容易找到一條到食物源的最短路徑。

四、蟻群算法優化求解

在研究調度問題中，爬山法、遺傳算法等取得了一定的成果，但是由文獻比較結果顯示蟻群算法的計算結果明顯優于其他方法。因此本文采用了蟻群算法解決應急物流配送車輛調度問題。

在優化求解過程中，我們做如下定義:

(1)m:蟻群中螞蟻的數量。

(2)ηij路徑ij的能見度。

(3)Γij t時刻在路徑ij上的信息量。

(4)ΔΓijk螞蟻k在本次循環中留在路徑ij上的信息量。

(5)Pjik螞蟻k在t時刻由位置i轉移到位置j的概率。

(6)α:轉跡的相對重要性，α≥0。

(7)β:能見度的相對重要性，β≥0。

(8)ρ:信息數的持久性，0≤ρ≤1，1-ρ表示信息素的衰減度。

(9)假設Γij(0)=C，C為一常量。

(10)螞蟻k在運動過程中，只允許移向未到達的受災點或者是救災物資儲備中心，并且根據當前所處位置的不同選擇不同路徑。

(11)當螞蟻位于救災點時:由于救災點假設均滿足車載重量約束，則在這些救災點中螞蟻k按照式(10)給出的轉移規則移向受災點s;否則隨機產生一個(0，1)間的隨機數r，若r

其中S表示為:，

S=arg max{[Γ(r，u)]α·[η(r，u)]β}uallowed(10)

Pijk(t)表示為:

(11)

allowedk=[0，1，…，n-1]-tabuk表示t時刻螞蟻k下一步允許選擇的點。在蟻群算法中，我們假設人工蟻群系統有記憶功能，用tabuk(k=1，2，…，m)記錄螞蟻k已走過的節點。當一個周期結束，進入t+1時刻，對各路徑上的信息進行調整，即:

(12)

(13)

螞蟻K在本次循環中經過路徑ij，否則為0(14)

其中Q是常數，表示螞蟻循環一周所釋放的總信息量。 表示k只螞蟻在本次循環中所走路徑的總長度，它體現了全局范圍內的最短路徑，能都提高系統搜索的收斂速度。參數Q、C、α、β、ρ可以用實驗方法確定其最優組合。停止條件可以用固定循環次數或者當進化趨勢不明顯時便停止計算。

五、總結

蟻群算法是通過信息素傳遞來選擇路徑，具有較好的全局尋優能力，收斂速度快和穩定性強的優點，與傳統算法相比能夠很好地解決連通圖結構的問題。因此，蟻群算法是解決物流配送路徑優化問題的一個有效算法。它可以縮短運輸距離與運輸時間，減少客運商服務成本，提高服務質量。

參考文獻:

[1]謝秉磊 李 軍:《有時間窗的非滿載車輛調度問題的遺傳算法》[J].《系統工程學報》2000(3):290～294

[2]趙家俊 于寶琴:《現代物流配送管理》[M].北京大學出版社，2004:94～99

[3]崔雪麗 馬 良:《有缺貨限制的VRP螞蟻算法研究》[J].《上海理工大學學報》2003(1):39～4