螞蟻算法在配送運(yùn)輸問題上的路徑優(yōu)化研究?

馮豪杰

（河南理工大學(xué)礦山空間信息技術(shù)國家測繪地理信息局重點(diǎn)實(shí)驗(yàn)室 焦作 454003）

1 引言

隨著經(jīng)濟(jì)持續(xù)不斷發(fā)展，我國物流需求規(guī)模只增不減，隨之而來的是物流成本逐年攀升，配送車輛調(diào)度問題在企業(yè)運(yùn)營中的作用越來越大，確切需要在物流配送成本方面制定新對策，去促進(jìn)降低成本，從而提高其經(jīng)營運(yùn)營能力，這對物流業(yè)的發(fā)展具有重大的現(xiàn)實(shí)與實(shí)際意義［1～4］。車輛路徑問題和車輛排程問題統(tǒng)稱為物流配送車輛優(yōu)化調(diào)度問題，該問題的提出，就受到、網(wǎng)絡(luò)分析、圖論、計(jì)算機(jī)應(yīng)用、組合數(shù)學(xué)等學(xué)科的專家與運(yùn)輸計(jì)劃制定者以及管理者的極大重視，并進(jìn)行了大量的理論研究和實(shí)驗(yàn)驗(yàn)證，將其研究成果運(yùn)用在運(yùn)輸、配送等系統(tǒng)中［5～6］。

2 螞蟻算法的原理

根據(jù)仿生學(xué)家的長期研究發(fā)現(xiàn)：在覓食的過程中螞蟻雖沒有視覺，但會在走過的路徑上釋放一種特殊分泌物—信息素［7～8］，該信息素會被伙伴識別，碰到一個(gè)沒有走過的路口時(shí)，會隨機(jī)挑選一條路徑行走，同時(shí)釋放等量的信息素，路徑越長則在這條路徑上消耗的時(shí)間越多，信息素?fù)]發(fā)的越多，相反，遺留的信息素濃度越低［9～12］。當(dāng)后來的螞蟻再遇到某個(gè)路口時(shí)，信息素濃度高的路徑被選中的概率較大，這樣便形成了一個(gè)正反饋機(jī)制［13～15］。最優(yōu)路徑上的信息素濃度越來越高，其他路徑上信息素濃度會隨著時(shí)間的流逝而逐漸消減，甚至消失，最終整個(gè)蟻群會找出最優(yōu)路徑［16～17］。圖1為螞蟻算法的最短路徑與原理示意圖。

圖1中表示60只螞蟻要經(jīng)過障礙物尋找到食物。

T=0時(shí)刻：ABC與ADC兩段路都是30只螞蟻；

T=10時(shí)刻：ABC與ADC兩段路分別為45、15只螞蟻；

T=20時(shí)刻：ABC與ADC兩段路分別為60、0只螞蟻。

圖1 螞蟻算法原理

3 路徑優(yōu)化的螞蟻算法設(shè)計(jì)與實(shí)現(xiàn)

傳統(tǒng)螞蟻算法是一種理想化狀態(tài)，沒有考慮到現(xiàn)實(shí)生活中諸多細(xì)節(jié)。在覓食過程中沒有考慮到天氣狀況、路狀、搜索時(shí)間過長以及揮發(fā)系數(shù)等，需要把這些因素綜合全部考慮到該算法中。

3.1 相關(guān)系數(shù)的改進(jìn)

螞蟻算法雖具有全局性特征，但通常會忽略局部環(huán)境中的相關(guān)因素的影響，這也是在長時(shí)間路徑選擇中需要考慮的。路徑選擇次數(shù)的增多，路徑上的信息素濃度會逐漸揮發(fā)掉，此時(shí)我們要考慮局部信息素濃度揮發(fā)程度，用揮發(fā)系數(shù)β來控制信息素濃度的揮發(fā)程度，β的大小直接關(guān)系到螞蟻群算法的全局搜索能力及其收斂速度，因此通過自適應(yīng)的調(diào)整β的大小來提高算法的全局性，0≤β≤1。

假設(shè)β的初始值為1，當(dāng)蟻群算法求得的最優(yōu)解在有限次循環(huán)內(nèi)沒有明顯改進(jìn)時(shí)，β以下式作自適應(yīng)調(diào)整：

其中 βmin為 β的最小值，可以防止 β過小降低算法的收斂速度。

在經(jīng)過時(shí)間t1后，蟻群會完成路徑的一個(gè)循環(huán)選擇，這時(shí)殘留在每條路徑上的信息素濃度為

式中Q表示信息素濃度，影響算法的收斂快慢，通常為常數(shù)；LK表示螞蟻K在本次循環(huán)中走過的所有路徑的總長度。

3.2 局部最優(yōu)的改進(jìn)

由于初始信息素濃度相等，導(dǎo)致開始時(shí)螞蟻盲目搜索，產(chǎn)生大量無關(guān)路徑，對信息素濃度局部更新產(chǎn)生誤導(dǎo)。該問題不僅會導(dǎo)致初始搜索時(shí)間過長，并且無關(guān)路徑信息素濃度被加強(qiáng)，阻礙最優(yōu)路徑搜索過程。本文根據(jù)無向圖路徑信息，在初始信息素濃度時(shí)加入方向性引導(dǎo)，初始化信息素公式修改如下：

其中Q表示信息素濃度，代表每次搜索分配的總信息素，一般為給定的參數(shù)；dij，djk分別表示節(jié)點(diǎn)j與起點(diǎn)i和終點(diǎn)k的直線距離。起點(diǎn)i與終點(diǎn)k的最短距離為兩點(diǎn)之間的直線距離，從式（4）中可以得出，當(dāng)節(jié)點(diǎn)j越趨于連線ik時(shí)，（dij+djk）越小，則X（0）越大，蟻群越傾向于選擇該節(jié)點(diǎn)方向?yàn)橐苿拥姆较颍环粗?，則偏離該節(jié)點(diǎn)。該算法在搜索起始點(diǎn)時(shí)對節(jié)點(diǎn)引入不同權(quán)值，對起始搜索產(chǎn)生很合理的方向引導(dǎo)，減弱了對較長路徑的搜索，從而加速了尋找到全局最優(yōu)解的速度。

3.3 配送運(yùn)輸路徑優(yōu)化算法的實(shí)現(xiàn)

物流業(yè)發(fā)展中，對車輛配送路徑優(yōu)化問題的求解方面，可借助人工螞蟻替代車輛來服務(wù)客戶點(diǎn)，返回到配送中心的標(biāo)準(zhǔn)是下一個(gè)服務(wù)客戶點(diǎn)的運(yùn)載總量比最遠(yuǎn)行駛距離或是汽車載重量多的時(shí)候，并不同車輛完成的此次運(yùn)輸，在此基礎(chǔ)上，車輛可以對其他客戶進(jìn)行全方位服務(wù)，繼而該車輛的人工螞蟻就可以完成一次巡游標(biāo)志，該標(biāo)記是對客戶進(jìn)行的一次服務(wù)，一次服務(wù)也可以是一次循環(huán)，之后，需要根據(jù)螞蟻巡游路徑的時(shí)間長短將其他信息素進(jìn)行分配，從而更好地對信息素增量進(jìn)行不同程度的更新，以此進(jìn)行不斷的更新，得到最優(yōu)路徑或是選擇相同路徑，這樣就可以完成求解了。

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

為了驗(yàn)證本文改進(jìn)算法的優(yōu)越性與有效性，選擇AutoCAD進(jìn)行實(shí)例驗(yàn)證。將基本螞蟻算法與本文改進(jìn)的算法所得到的具體參數(shù)就行對比，可得到如表1的結(jié)果。

表1 兩種算法的對比

從表1中可以看出，在使用的車輛是相同的情況下，本文的算法到達(dá)目的地所使用的行程更短，說明本文算法在通行效率上更具有優(yōu)勢。

4 結(jié)語

針對實(shí)際道路配送運(yùn)輸問題，本文提出了改進(jìn)的螞蟻算法，對相關(guān)系數(shù)的改進(jìn)和對局部最優(yōu)的優(yōu)化為突破口。實(shí)例驗(yàn)證本文算法在行駛里程等方面更具有優(yōu)越性。