基于蟻群算法和動(dòng)態(tài)路阻的物流配送路徑優(yōu)化

丁柏群，姜 瑾

(東北林業(yè)大學(xué) 交通學(xué)院，哈爾濱 150040)

現(xiàn)階段，我國多數(shù)物流企業(yè)對(duì)配送車輛進(jìn)行調(diào)度時(shí)主要依據(jù)經(jīng)驗(yàn)，容易導(dǎo)致車輛使用效率低下，基于蟻群算法研究城市配送車輛路徑優(yōu)化問題有很強(qiáng)的實(shí)用性，結(jié)合動(dòng)態(tài)路阻函數(shù)的優(yōu)化后蟻群算法將考慮實(shí)際路網(wǎng)動(dòng)態(tài)交通條件的影響，其優(yōu)化目標(biāo)就是在滿足貨運(yùn)車輛完成對(duì)客戶要求產(chǎn)品需求的前提，使得所有車輛的行駛路線最合理。

1 蟻群算法基本原理

意大利學(xué)者M(jìn).Dorigo在自然界真實(shí)蟻群覓食行為的啟發(fā)下于1991年首次系統(tǒng)地提出蟻群算法。在從食物源到蟻穴并返回的過程中，螞蟻能在其走過的路徑上分泌一種化學(xué)物質(zhì)，稱為信息素，并通過這種方式形成信息素軌跡[1]。螞蟻在運(yùn)動(dòng)過程中能夠感知信息素的存在及強(qiáng)度，并依此指導(dǎo)自己的運(yùn)動(dòng)方向，使螞蟻傾向于朝著該物質(zhì)強(qiáng)度高的方向移動(dòng)，形成回到蟻穴的最短路徑。

蟻群在完成覓食并返回蟻穴的過程中具有如下特征。

(1)在從節(jié)點(diǎn)i到節(jié)點(diǎn)j的運(yùn)動(dòng)過程中或是在完成一次循環(huán)后，螞蟻在邊(i，j)上釋放一種物質(zhì)，稱為信息素軌跡。

(2)螞蟻概率地選擇下一個(gè)將要訪問的節(jié)點(diǎn)，這個(gè)概率是兩節(jié)點(diǎn)間距離和連接兩節(jié)點(diǎn)的路徑上存有信息素量的函數(shù)。

(3)為了滿足問題的約束條件，在完成一次循環(huán)之前，不允許螞蟻訪問已經(jīng)訪問過的節(jié)點(diǎn)。

(1)

其中，allowedk={0，1，…，n-1}表示螞蟻k下一步允許選擇的節(jié)點(diǎn)；tabu為用于記錄螞蟻在一次循環(huán)中已經(jīng)走過節(jié)點(diǎn)的禁忌表[3-4]。

α、β為參數(shù)，分別反映螞蟻在運(yùn)動(dòng)過程中所積累的信息和啟發(fā)信息在螞蟻選擇上的重要程度。

τij(t)為t時(shí)刻從節(jié)點(diǎn)i到節(jié)點(diǎn)j的信息素軌跡強(qiáng)度。

ηij(t)為t時(shí)刻的能見度，反映螞蟻從節(jié)點(diǎn)i到節(jié)點(diǎn)j的可期望性。

2 結(jié)合動(dòng)態(tài)路阻的蟻群算法優(yōu)化

在目前的配送路徑規(guī)劃研究中，對(duì)道路阻抗的研究很少，路阻函數(shù)是指路段行駛時(shí)間與路段交通負(fù)荷之間的關(guān)系，交通阻抗的大小將直接影響車輛對(duì)路徑的選擇，是動(dòng)態(tài)交通分配的關(guān)鍵。

2.1 路阻函數(shù)建模

道路阻抗分為靜態(tài)道路阻抗和動(dòng)態(tài)道路阻抗，在以往的靜態(tài)交通分配中，交通阻抗直接用路段長度除以實(shí)際行車速度的辦法來確定，該方法僅考慮了道路條件對(duì)路阻的影響，不能體現(xiàn)動(dòng)態(tài)交通條件對(duì)配送車輛選擇路徑的影響。本文考慮將靜態(tài)路阻函數(shù)與動(dòng)態(tài)路阻函數(shù)結(jié)合，并改進(jìn)到蟻群算法中，以便于更好的得到最優(yōu)路徑。

(2)

(3)

(4)

公式(4)中，當(dāng)某一路段上的交通量逐漸增大，達(dá)到qij=cij后，道路上的車輛將開始產(chǎn)生擁擠，此時(shí)的交通密度為極限密度，若車輛仍不斷增加，將導(dǎo)致交通阻塞，從而使車輛行駛速度為零，通過該路段的時(shí)間為無限長，則路阻函數(shù)為最大；反之，當(dāng)路段上的交通量趨于零時(shí)，車輛行駛速度為自由流速度，則路阻函數(shù)為最小。

綜合路阻函數(shù)Zij由層次分析法得到的靜態(tài)路阻函數(shù)和實(shí)時(shí)交通流量轉(zhuǎn)化的動(dòng)態(tài)路阻函數(shù)相應(yīng)結(jié)合得到：

(5)

式中：γ為靜態(tài)路阻函數(shù)在綜合路阻函數(shù)中所占的比例系數(shù)。

2.2 考慮動(dòng)態(tài)路阻的蟻群算法

為考慮動(dòng)態(tài)交通條件對(duì)狀態(tài)轉(zhuǎn)移的影響，將道路阻抗函數(shù)Zij結(jié)合進(jìn)蟻群算法狀態(tài)轉(zhuǎn)移概率公式中：

(6)

3 物流配送車輛路徑優(yōu)化模型

車輛路徑問題可以描述為：某一配送中心負(fù)責(zé)向多個(gè)客戶點(diǎn)運(yùn)輸貨物，每個(gè)客戶點(diǎn)的貨物需求量為gi(i=1，2，…，n)，配送中心將派出多輛相同規(guī)格貨車負(fù)責(zé)送貨，求滿足貨物需求的最低成本的車輛運(yùn)輸行程路線。大部分物流企業(yè)的配貨，特別是有時(shí)間窗口的配貨對(duì)總行程時(shí)間的長短有所限制，對(duì)物流配送的快捷性要求較高，這里的運(yùn)輸成本則主要考慮時(shí)間成本，應(yīng)使得所行駛線路最短為研究主要目標(biāo)，但是由于實(shí)際交通條件的限制，行駛距離最短的路徑不一定就是用戶考慮最優(yōu)的路徑。

因此將各路段的距離dij經(jīng)過處理轉(zhuǎn)化為以行駛時(shí)間為標(biāo)準(zhǔn)，則路段上行駛時(shí)間為

(7)

在定義模型前，需要做出以下假設(shè)：

(2)配送中心的配送車輛為統(tǒng)一型號(hào)車輛，汽車載重量要大于在線路上經(jīng)過客戶點(diǎn)的需求量之和。

(3)每個(gè)客戶點(diǎn)的貨物需求只能由一輛車來完成。

車輛配送期望達(dá)到的目標(biāo)是[3]：

(1)按照客戶點(diǎn)的需求準(zhǔn)時(shí)送貨以提高服務(wù)質(zhì)量。

(2)在保證客戶需求量不超過車輛載重，同時(shí)滿足車輛行經(jīng)各個(gè)客戶點(diǎn)的總行駛時(shí)間最短的前提下，使得物流配送總成本最低。

相關(guān)變量：

M為車輛總數(shù)，N為客戶點(diǎn)數(shù)。

gi為客戶的貨物需求量，其中=1，2，…，n。

dij為客戶i到客戶j的距離，i，j=0，1，2，…，n，其中d0j表示配送中心到客戶j的距離，di0表示客戶i到配送中心的距離。

Q為車輛的最大裝載量，假設(shè)：

根據(jù)約束條件，建立以配送總時(shí)間最短為目標(biāo)的優(yōu)化目標(biāo)函數(shù)為：

(8)

4 實(shí)例驗(yàn)證

將優(yōu)化后的蟻群算法對(duì)哈爾濱某一物流配送中心向各個(gè)客戶需求點(diǎn)配送貨物實(shí)例應(yīng)用驗(yàn)證，要求滿足各分店的貨物需求，安排合理的配送路線，使得實(shí)時(shí)交通路況下配送線路最優(yōu)[4-7]。

在此配送案例中，依據(jù)所調(diào)查的實(shí)際情況做出以下約束：

(1)假設(shè)配送中心到各客戶需求點(diǎn)的道路路況信息為已知，實(shí)時(shí)路況信息可以隨時(shí)獲得。

(2)配送中心到各客戶點(diǎn)的距離及各客戶點(diǎn)的貨物需求量為已知。

(3)車輛在完成配送任務(wù)后要返回配送中心，各個(gè)客戶必須配送到達(dá)且只能配送一次。

用0代表配送中心，1～9代表貨物需求點(diǎn)，配送中心有載重量為5 t的相同規(guī)格配送車輛3輛，每次配送最大行駛距離為60 km。9個(gè)客戶的貨物需求量見表1。

表1 客戶貨物需求量

構(gòu)建數(shù)學(xué)模型并設(shè)定相關(guān)參數(shù)：

(1)相關(guān)變量

客戶數(shù)：N=9；

配送中心派出的車輛總數(shù)：M=3；

車輛的最大載重量：Q=5 t；

車輛的最大行駛距離：D=60 km。

(2)確定優(yōu)化目標(biāo)函數(shù)

(9)

為驗(yàn)證考慮路阻函數(shù)的改進(jìn)蟻群算法在解決物流配送路徑優(yōu)化問題上的應(yīng)用，使用軟件對(duì)哈爾濱市某一物流配送中心所選擇的9個(gè)客戶點(diǎn)的貨物配送路徑優(yōu)化進(jìn)行配送求解?？紤]蟻群算法的搜索循環(huán)次數(shù)和解的最優(yōu)性，選定所需參數(shù)螞蟻數(shù)量m=15，啟發(fā)式因子α=3，啟發(fā)式因子β=3，信息素的揮發(fā)系數(shù)ρ=0.5，螞蟻釋放的信息素量Q=100。

靜態(tài)蟻群算法和優(yōu)化后的蟻群算法由于客戶點(diǎn)需求量的限制，對(duì)客戶節(jié)點(diǎn)運(yùn)行的結(jié)果得到的較優(yōu)路徑中各車輛的配送路線為：配送中心-建國街-保障街-濱江站-通達(dá)街-配送中心；配送中心-神州物流-禧龍大市場(chǎng)-內(nèi)陸港-配送中心；配送中心-哈平西路-新疆東路-配送中心。圖1和圖2分別是兩者得到的優(yōu)化行駛路徑。

圖1 靜態(tài)蟻群算法的實(shí)際最優(yōu)路徑

圖2 動(dòng)態(tài)蟻群算法的實(shí)際最優(yōu)路徑

根據(jù)優(yōu)化目標(biāo)函數(shù)，使得貨物從配送中心出發(fā)到達(dá)各個(gè)客戶點(diǎn)后返回物流中心的總行程時(shí)間最短，靜態(tài)蟻群算法和優(yōu)化后的動(dòng)態(tài)蟻群算法的計(jì)算數(shù)據(jù)見表2。

表2 兩種算法的計(jì)算結(jié)果比較

從表2可以看出，融合路阻函數(shù)的蟻群算法較傳統(tǒng)靜態(tài)蟻群算法在相同迭代次數(shù)下總行駛距離相差不大，行駛時(shí)間節(jié)省了約15%左右，滿足了優(yōu)化目標(biāo)函數(shù)使得行駛時(shí)間最短的要求，因此在求解車輛路徑問題時(shí)，基于動(dòng)態(tài)路阻函數(shù)的優(yōu)化蟻群算法是有效的。

5 結(jié)束語

在基本蟻群算法原理和物流配送模型的基礎(chǔ)上，考慮實(shí)際交通情況下的動(dòng)態(tài)路阻函數(shù)，將其優(yōu)化進(jìn)蟻群算法形成動(dòng)態(tài)路徑優(yōu)化方法，在物流中心對(duì)配送路徑選擇時(shí)有效縮短配送時(shí)間，在本文案例驗(yàn)證計(jì)算中，結(jié)合動(dòng)態(tài)路阻函數(shù)的蟻群算法較靜態(tài)蟻群算法節(jié)省了配送時(shí)間15%左右；通過軟件開發(fā)能夠?qū)?yōu)化動(dòng)態(tài)路徑選擇作為具有實(shí)用價(jià)值的物流管理服務(wù)系統(tǒng)的組成部分，為用戶提供更有效路徑選擇的指示和導(dǎo)航。

【參 考 文 獻(xiàn)】

[1] 李世勇.蟻群算法及其應(yīng)用[M].哈爾濱：哈爾濱工業(yè)大學(xué)大學(xué)出版社，2004.

[2] 馬 良，朱 剛，寧愛兵.蟻群優(yōu)化算法[M].北京：科技出版社，2008.

[3] 尹訓(xùn)波.基于蟻群算法的物流配送路徑優(yōu)化[J].科技信息，2006，23(6).195-196.

[4] 李 慧.基于蟻群算法的物流配送路徑優(yōu)化[D].太原：山西大學(xué)，2011.

[5] 溫惠英，沈毅賢.適于物流配送車輛導(dǎo)航路徑規(guī)劃的路網(wǎng)阻抗確定方法研究[J].交通科技2008，34(1).94-97.

[6] 李慧子，王爾媚，周 沫，等.甩掛運(yùn)輸車隊(duì)運(yùn)營組織模式分析[J].森林工程，2014，30(1)：157-160.

[7] 鄭 遠(yuǎn)，杜豫川，孫立軍.美國聯(lián)邦公路局路阻函數(shù)探討[J].交通與運(yùn)輸(學(xué)術(shù)版)，2007，(1).31-33.