基于改進(jìn)蟻群算法的物流運(yùn)輸路徑研究*

馬貴平,潘 峰

(西南交通大學(xué)希望學(xué)院，四川 成都 610400)

1 引言

隨著經(jīng)濟(jì)和科學(xué)技術(shù)的發(fā)展，網(wǎng)上購物逐漸成為人們必不可少的生活方式，這種購物方式不僅大幅度便利了人們的生活，而且還帶動(dòng)了物流行業(yè)的快速發(fā)展。物流作為“第三利益源泉”對(duì)經(jīng)濟(jì)發(fā)展的影響日益明顯，越來越多的企業(yè)也紛紛加入其中，物流逐漸成為當(dāng)今競(jìng)爭(zhēng)激烈的行業(yè)之一。如何實(shí)現(xiàn)科學(xué)物流配送是每一家物流企業(yè)必須面對(duì)的一個(gè)非常繁瑣而且至關(guān)重要的難題，物流企業(yè)都需要在運(yùn)輸過程中實(shí)現(xiàn)低成本、高效率的目標(biāo)。在物流配送中，物流運(yùn)輸路徑的選擇問題尤為關(guān)鍵，它是每一家物流企業(yè)都需要解決的難題。在物流運(yùn)輸過程中，降低企業(yè)物流成本，縮短運(yùn)輸時(shí)間，提升運(yùn)輸服務(wù)質(zhì)量，獲得運(yùn)輸最優(yōu)路徑是學(xué)者們研究的目標(biāo)。為此本文提出基于改進(jìn)蟻群算法的物流運(yùn)輸模型來降低物流運(yùn)輸成本,提高運(yùn)輸效率。

2 車輛路徑優(yōu)化的問題

車輛路徑優(yōu)化問題VRP(Vehicle Routing Problem)是物流配送優(yōu)化過程中的重要研究對(duì)象，車輛路徑優(yōu)化問題被明確定為NP-hard問題，隨著配送貨物數(shù)量不斷增加，傳統(tǒng)路徑規(guī)劃算法并不能在較短時(shí)間內(nèi)獲得最優(yōu)解，這類組合優(yōu)化問題利用仿生優(yōu)化算法能更好地進(jìn)行求解。國內(nèi)外學(xué)者都提出了大量的算法對(duì)該類問題進(jìn)行求解,例如王迎等[1]提出一種加入混沌擾動(dòng)的模擬退火蟻群算法CSAACO(Chaotic-Simulated Annealing Ant Colony Algorithm)，該算法設(shè)定了尋找的范圍，對(duì)信息素更新方式加以改進(jìn)，提高了算法的全局尋優(yōu)能力，在求解效率和精度方面優(yōu)于傳統(tǒng)蟻群算法；龍汀等[2]提出利用蟻群算法的思想求解VRP問題，該思想利用一種改進(jìn)的蟻群算法來求解帶時(shí)間窗的VRP，通過加入偽隨機(jī)等相關(guān)參數(shù)來改進(jìn)傳統(tǒng)蟻群算法，最后通過仿真模擬實(shí)驗(yàn)測(cè)試，實(shí)驗(yàn)結(jié)果表明該算法能有效獲得全局最優(yōu)解，加快算法收斂速度；趙美紅[3]在標(biāo)準(zhǔn)蟻群算法基礎(chǔ)之上，對(duì)信息素更新方式進(jìn)行改進(jìn)，并且加入最近鄰域算法以及局部最優(yōu)搜索策略來解決算法初期的螞蟻路徑選擇問題，同時(shí)利用動(dòng)態(tài)信息素更新方法對(duì)標(biāo)準(zhǔn)蟻群算法進(jìn)行優(yōu)化改進(jìn)，使算法趨于全局收斂，實(shí)驗(yàn)表明算法的性能得到了有效提高；王蕾等[4]搭建了多子群蟻群算法，利用各子區(qū)間之間的信息排斥與依存關(guān)系，加快最優(yōu)線路的搜索速度，縮短了運(yùn)行任務(wù)所需要的時(shí)間。

物流路徑優(yōu)化的問題是一個(gè)典型的組合優(yōu)化問題，是極為復(fù)雜的系統(tǒng)性問題，上述研究在一定程度上改善了該難題。本文在以上研究基礎(chǔ)之上，提出采用改進(jìn)蟻群算法來有效改進(jìn)目前運(yùn)輸車輛在選擇路徑時(shí)存在成本高、效率低下等問題，并與文獻(xiàn)[1]中的CSAACO算法和傳統(tǒng)的蟻群優(yōu)化ACO(Ant Colony Optimization)算法進(jìn)行仿真實(shí)驗(yàn)對(duì)比，來驗(yàn)證本文改進(jìn)算法的可行性和有效性。

3 傳統(tǒng)蟻群算法

ACO算法是一種人工智能優(yōu)化算法，用以模擬自然界蟻群在搜尋食物過程中探索線路的行為。蟻群優(yōu)化算法表明螞蟻能夠根據(jù)前面螞蟻所分泌的信息素來選擇路徑，其選擇食物源線路的通往概率與該線路上分泌的信息素強(qiáng)度成正比。因此，在螞蟻經(jīng)過的路徑上會(huì)形成一種信息的反饋現(xiàn)象，即選擇某1條路徑的螞蟻數(shù)量越多，該路徑上所留下的信息素就越多，后面的螞蟻選擇該條路徑的可能性就越大，以此達(dá)到尋找到最短路徑的目的。

假設(shè)有m只螞蟻，并且螞蟻全部從規(guī)定出發(fā)點(diǎn)出發(fā)，假設(shè)它們到達(dá)食物的道路上分布有n個(gè)節(jié)點(diǎn)，τij(t)表示節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的路徑上在t時(shí)刻的信息素濃度，ηij(t)為路徑i→j對(duì)應(yīng)的啟發(fā)信息函數(shù)，則對(duì)某1只螞蟻k，從節(jié)點(diǎn)i爬行到下1節(jié)點(diǎn)j的概率為：

(1)

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

(2)

(3)

4 改進(jìn)蟻群算法模型

傳統(tǒng)蟻群算法優(yōu)點(diǎn)較多，如算法魯棒性較強(qiáng)，采用正反饋算法，并且容易和其他算法相結(jié)合等。但是，傳統(tǒng)蟻群算法也不可避免地存在一些缺陷，例如，容易陷入局部最優(yōu)解而導(dǎo)致搜索停止現(xiàn)象，而且搜索時(shí)間較長(zhǎng)，在解決車輛路徑優(yōu)化這類NP-hard問題時(shí)，傳統(tǒng)蟻群算法尋求最優(yōu)解的速度和效率就會(huì)變得相對(duì)較低。在應(yīng)用傳統(tǒng)蟻群算法優(yōu)化物流運(yùn)輸路徑過程中,常見的方法是求解出物流運(yùn)輸起始點(diǎn)到終點(diǎn)之間的最短距離,此類算法主要考慮的是利用路徑長(zhǎng)短來衡量解的優(yōu)劣。但是，在物流運(yùn)輸過程中，有必要考慮所選擇道路的平均通暢程度，所產(chǎn)生的運(yùn)輸成本以及運(yùn)輸時(shí)間等因素。因此，道路的選擇其實(shí)是1個(gè)多約束條件下的求最優(yōu)解的問題。為此，本文在標(biāo)準(zhǔn)蟻群算法基礎(chǔ)之上，加入基于多個(gè)約束條件的最優(yōu)路徑選擇的改進(jìn)蟻群算法，在傳統(tǒng)蟻群算法基礎(chǔ)之上對(duì)啟發(fā)函數(shù)和信息素更新方式分別進(jìn)行改進(jìn)，利用下1節(jié)點(diǎn)到終點(diǎn)的距離來改進(jìn)蟻群算法中的啟發(fā)函數(shù)；通過由物流運(yùn)輸時(shí)間因子、物流運(yùn)輸成本因子和道路平均通暢程度因子組成的約束函數(shù)模型來改進(jìn)算法中的信息素更新方式。改進(jìn)后的蟻群算法使得物流運(yùn)輸時(shí)間更短，運(yùn)輸途徑更短，運(yùn)輸效率更高。

5 改進(jìn)啟發(fā)信息模型

在傳統(tǒng)蟻群算法公式中，啟發(fā)函數(shù)只考慮相鄰2個(gè)節(jié)點(diǎn)之間的距離的倒數(shù)1/dij，但這樣的方式只反映了當(dāng)前節(jié)點(diǎn)與相鄰節(jié)點(diǎn)的關(guān)系，沒有反映當(dāng)前節(jié)點(diǎn)和目標(biāo)點(diǎn)的關(guān)系。這種局部的搜索范圍是以當(dāng)前節(jié)點(diǎn)為中心，周圍節(jié)點(diǎn)為半徑的類似圓形的區(qū)間，這種沒方向性的搜尋方式容易讓螞蟻陷入局部最優(yōu)，只能搜索出局部最短路徑，而且容易導(dǎo)致得到的解并非全局最優(yōu)路徑，從而失去了全局搜尋最優(yōu)解的能力。針對(duì)該問題，可將下1個(gè)節(jié)點(diǎn)j與終點(diǎn)g之間的直線距離加入到啟發(fā)函數(shù)中，表達(dá)式如下所示：

(4)

其中，dij表示當(dāng)前節(jié)點(diǎn)i到下1個(gè)節(jié)點(diǎn)j之間的距離，djg表示當(dāng)前節(jié)點(diǎn)j到節(jié)點(diǎn)g之間的距離。將下1節(jié)點(diǎn)和終點(diǎn)之間的距離引入啟發(fā)函數(shù)，增強(qiáng)了螞蟻搜尋的目的性，可加快算法收斂速度。若djgdij,則規(guī)定節(jié)點(diǎn)j為近距離節(jié)點(diǎn)。當(dāng)螞蟻搜索時(shí)，對(duì)于遠(yuǎn)距離的節(jié)點(diǎn)無需搜索，只需計(jì)算距離i較近的幾個(gè)節(jié)點(diǎn)，利用此改進(jìn)方法，能夠進(jìn)一步減少計(jì)算量，加快算法收斂速度。因此，利用式(5)對(duì)傳統(tǒng)蟻群算法進(jìn)行改進(jìn)：

(5)

5.1 改進(jìn)信息素更新模型

基于物流運(yùn)輸過程中，最優(yōu)路徑的選擇主要考慮幾個(gè)關(guān)鍵因素：運(yùn)輸?shù)臅r(shí)間、成本、道路平均通暢程度。為了更快獲取最優(yōu)解，本文通過設(shè)置運(yùn)輸時(shí)間因子、運(yùn)輸成本因子、道路平均通暢程度因子來對(duì)路徑選擇建立基于多個(gè)約束因子的數(shù)學(xué)模型X(j)，并將該模型融入到標(biāo)準(zhǔn)蟻群算法當(dāng)中,實(shí)現(xiàn)基于多約束條件的路徑實(shí)時(shí)更新和動(dòng)態(tài)選擇,引導(dǎo)物流運(yùn)輸選擇朝最優(yōu)路徑前行,更加精確地得到最優(yōu)解。

5.1.1 物流運(yùn)輸時(shí)間因子

(6)

其中，Tjmax表示物流在道路運(yùn)輸過程中允許的預(yù)估最長(zhǎng)時(shí)間上限，Tj表示物流運(yùn)輸所需的實(shí)際時(shí)間，并且

Tj≤Tjmax

(7)

X1(j)為物流運(yùn)輸時(shí)間因子，表示物流運(yùn)輸?shù)焦?jié)點(diǎn)j的實(shí)際運(yùn)輸時(shí)間與預(yù)估最長(zhǎng)時(shí)間的比值。該比值越大，說明實(shí)際運(yùn)輸時(shí)間越長(zhǎng)。

5.1.2 運(yùn)輸成本因子

(8)

其中，X2(j)表示運(yùn)輸成本因子，表示物流運(yùn)輸?shù)焦?jié)點(diǎn)j的實(shí)際運(yùn)輸成本fj與最大預(yù)估運(yùn)輸成本fj max的比值，該比值越大，說明實(shí)際運(yùn)輸成本越高。

fj=abrasionj+Tollj+Fuelj

(9)

fj≤fjmax

(10)

其中，abrasionj表示道路運(yùn)輸過程中的磨損費(fèi)；Tollj表示通行費(fèi)；Fuelj表示燃料費(fèi)。

5.1.3 道路平均通暢程度

(11)

其中，X3(j)表示物流運(yùn)輸?shù)焦?jié)點(diǎn)j的過程中，運(yùn)輸?shù)焦?jié)點(diǎn)j的路徑的通暢程度與車輛行駛道路通暢度最低容忍度的比值，該比值越大，說明運(yùn)輸車輛選擇該路徑行使過程越通暢;Clj表示運(yùn)輸?shù)焦?jié)點(diǎn)j的路徑的通暢程度;Cljmax表示車輛行駛道路通暢度的最低容忍度。

綜上，約束函數(shù)X(j)表示如下:

X(j)=εX1(j)+φX2(j)+γX3(j)

(12)

其中,X1(j)表示物流運(yùn)輸時(shí)間因子，X2(j)表示物流運(yùn)輸成本因子，X3(j)表示道路平均通暢程度因子，ε、φ、γ分別表示在物流運(yùn)輸?shù)焦?jié)點(diǎn)j的過程中所花時(shí)間、成本、道路平均通暢程度所占權(quán)重。

5.1.4 最優(yōu)最差路徑優(yōu)化

為了加快算法的收斂速度，對(duì)質(zhì)量路最差的徑進(jìn)行削弱，加入懲罰因子，降低其被選擇的概率，增強(qiáng)質(zhì)量較好的路徑上的信息素濃度，使螞蟻選擇質(zhì)量更佳的路徑。對(duì)標(biāo)準(zhǔn)蟻群算法中信息素更新公式改進(jìn)如下：

(13)

式(13)中引入?yún)?shù)μ，μ∈[0,1]，Dbest表示遍歷到的最優(yōu)路徑，|Dbest|表示其長(zhǎng)度，Dworst表示遍歷到的最差路徑，|Dworst|表示其長(zhǎng)度,ρ為信息素濃度揮發(fā)系數(shù)。μ表示改進(jìn)蟻群算法中的信息素增強(qiáng)因子，對(duì)遍歷到的最差路徑進(jìn)行懲罰，降低其信息素濃度，對(duì)遍歷到的最優(yōu)路徑上的信息素進(jìn)行增強(qiáng)。同時(shí)，在改進(jìn)蟻群算法執(zhí)行過程中，為了防止路徑上信息素濃度無限制地累加，必須對(duì)信息素濃度進(jìn)行限制，約束表達(dá)式如下所示：

(14)

其中,τmax，τmin分別表示信息素最大值和最小值。

6 改進(jìn)后蟻群算法流程

改進(jìn)后的蟻群算法流程圖如圖1所示。

Figure 1 Flow chart of improved ACO algorithm圖1 改進(jìn)ACO算法流程圖

7 仿真實(shí)驗(yàn)

在仿真實(shí)驗(yàn)中,具體的實(shí)驗(yàn)環(huán)境設(shè)置如下:CPU 為2.30 GHz，內(nèi)存為4 GB，操作系統(tǒng)為Windows 2003，采用 Matlab 7.0實(shí)現(xiàn)編程。改進(jìn)后的蟻群算法參數(shù)設(shè)定為：螞蟻數(shù)量為100，初始的信息啟發(fā)因子α=1，期望啟發(fā)因子β=1，信息素?fù)]發(fā)系數(shù)ρ=0.5，ε=1/3，φ=1/3，γ=1/3，最大的迭代次數(shù)為300次，采用快遞物流公司的5個(gè)配送網(wǎng)點(diǎn)的數(shù)據(jù)，其物流配送服務(wù)的客戶規(guī)模如圖2和圖3的橫坐標(biāo)所示，配送時(shí)間縮短量和配送距離縮短量如圖2和圖3中的縱坐標(biāo)所示。采用本文改進(jìn)的蟻群算法、ACO算法和CSAACO算法分別對(duì)物流運(yùn)輸車輛進(jìn)行最優(yōu)路徑求解，求解結(jié)果用圖2和圖3中的折線表示。

從圖2可以看出,改進(jìn)算法的平均尋優(yōu)路徑的時(shí)間比ACO算法和CSAACO算法的分別縮短258 004 s和15 000 s；當(dāng)客戶規(guī)模在100～200時(shí)，傳統(tǒng)的ACO算法、CSAACO算法和本文的改進(jìn)算法的任務(wù)時(shí)間方面差異不是那么明顯，當(dāng)隨著客戶規(guī)模不斷增加，在執(zhí)行同樣規(guī)模任務(wù)的情況下，本文算法的時(shí)間遠(yuǎn)低于CSAACO和ACO的，本文算法能夠彌補(bǔ)CSAACO算法和ACO算法的尋優(yōu)時(shí)間較長(zhǎng)的不足，具有更快的求解速度。

Figure 2 Relationship between customer size and time shortening圖2 客戶規(guī)模與時(shí)間縮短量的關(guān)系

Figure 3 Relationship between customer size and distance reduction圖3 客戶規(guī)模與距離縮短量的關(guān)系

從圖3可以看出,本文改進(jìn)算法的求解路徑距離相比ACO和CSAACO分別減少25 000 m和5 854 m。當(dāng)客戶任務(wù)規(guī)模為100時(shí)，本文算法與CSAACO算法相比，距離縮短了約2 650 m；改進(jìn)算法與傳統(tǒng)ACO算法相比，距離縮短了約5 000 m；而且隨著規(guī)模的增加，差距在逐漸擴(kuò)大，本文改進(jìn)算法表現(xiàn)出來的優(yōu)勢(shì)更加明顯，具有更好的路徑尋優(yōu)能力。

以上實(shí)驗(yàn)結(jié)果表明，改進(jìn)算法在尋優(yōu)效率和尋優(yōu)質(zhì)量方面相比于CSAACO算法和ACO算法都有著明顯的提升。特別是隨著服務(wù)客戶的規(guī)模不斷擴(kuò)大，該算法能更有效地解決物流配送耗時(shí)長(zhǎng)和求解質(zhì)量差等問題，優(yōu)勢(shì)得到了更好的體現(xiàn)，利用本文改進(jìn)蟻群算法在同樣客戶規(guī)模任務(wù)的情況下，能夠有效縮短執(zhí)行配送任務(wù)的時(shí)間，減少運(yùn)輸路徑距離，加快算法收斂速度，最大化地提高物流行業(yè)整體配送效率。

8 結(jié)束語

物流運(yùn)輸?shù)穆窂竭x擇問題對(duì)物流企業(yè)的運(yùn)送成本、時(shí)間與效率的影響至關(guān)重要，是所有物流行業(yè)所面臨的難題。本文在傳統(tǒng)蟻群算法基礎(chǔ)之上對(duì)路徑上的信息素濃度進(jìn)行限制，同時(shí)加入基于運(yùn)輸時(shí)間、成本、道路平均通暢程度因子的約束條件，改進(jìn)信息素更新方式，從而改變了物流路徑轉(zhuǎn)移概率，增加了全局尋優(yōu)能力，縮短了配送路徑，降低了物流企業(yè)配送所花費(fèi)的成本，提高了配送效率，促進(jìn)了物流行業(yè)的快速發(fā)展。