基于電子地圖的改進(jìn)蟻群算法及其車輛路徑尋優(yōu)

劉慶華,汪 晶

(江蘇科技大學(xué) 計(jì)算機(jī)學(xué)院, 鎮(zhèn)江 212003)

隨著科學(xué)技術(shù)和經(jīng)濟(jì)迅猛發(fā)展,現(xiàn)實(shí)生活中車輛普及率越來(lái)越高,汽車私人擁有量也快速增加.交通事故、交通擁堵等問(wèn)題頻繁出現(xiàn),使得出行者迫切需要正確的出行路徑來(lái)盡可能避免類似事情發(fā)生.因此，路線規(guī)劃問(wèn)題成為了國(guó)內(nèi)外學(xué)者研究的一項(xiàng)重要課題[1]．國(guó)內(nèi)外學(xué)者對(duì)路徑規(guī)劃問(wèn)題進(jìn)行了大量研究,早期研究主要集中在理論及算法方面,具有重要應(yīng)用價(jià)值,比如在旅游業(yè)和物流業(yè)等行業(yè)中，合理的路線規(guī)劃能夠?yàn)樯碳夜?jié)約成本,創(chuàng)造更高價(jià)值[5]．

文獻(xiàn)[7]中首次提出了物流配送路徑優(yōu)化問(wèn)題,之后,便引起了計(jì)算機(jī)應(yīng)用等諸多領(lǐng)域的研究者們的高度關(guān)注,且迅速成為了運(yùn)籌學(xué)和組合優(yōu)化領(lǐng)域的研究熱點(diǎn)和前沿問(wèn)題，從而使得學(xué)者們對(duì)上述問(wèn)題進(jìn)行了大量理論研究和實(shí)驗(yàn)分析,并獲得了較大的進(jìn)步和成果．文獻(xiàn)[8]中提出了蟻群系統(tǒng)(ant colony system,ACS),它是一種應(yīng)用于旅行商問(wèn)題(travelling salesman problem,TSP)的分布式算法,也就是通過(guò)ACS算法研究路徑規(guī)劃問(wèn)題,通過(guò)ACS算法和模擬退火算法等進(jìn)行比較，表明ACS算法理論上能更好解決TSP問(wèn)題．文獻(xiàn)[9]中針對(duì)大型貨柜在建筑工地及購(gòu)物區(qū)堆積大量垃圾,提出了一種滾動(dòng)式廢物收集車輛路徑優(yōu)化問(wèn)題．文獻(xiàn)[10]中研究了冷藏車和一般車輛在多種類易腐食品運(yùn)輸過(guò)程中的路線規(guī)劃問(wèn)題．文獻(xiàn)[11]中做了基于仿真的交通擁堵車輛路徑規(guī)劃問(wèn)題研究,將交通擁堵轉(zhuǎn)化為非確定性動(dòng)態(tài)模型,首次將上限置信區(qū)間算法(upper confidence bound apply to tree,UCT)應(yīng)用在動(dòng)態(tài)交通問(wèn)題之中,并與蟻群算法進(jìn)行了比較,為文中方法的跨域適用性帶來(lái)了希望．文獻(xiàn)[12]中建立了帶約束條件的物流配送問(wèn)題的數(shù)學(xué)模型, 運(yùn)用蟻群算法解決物流配送路徑優(yōu)化問(wèn)題, 同時(shí)將遺傳算法的復(fù)制 、交叉和變異等遺傳算子引入蟻群算法, 以提高算法的收斂速度和全局搜索能力．文獻(xiàn)[13]中提出了一種改進(jìn)的蟻群算法，應(yīng)用于物流網(wǎng)絡(luò)中,并通過(guò)澳大利亞郵政數(shù)據(jù)進(jìn)行選址仿真實(shí)驗(yàn),驗(yàn)證了該算法模型在應(yīng)用中的求解效率和計(jì)算穩(wěn)定性．文獻(xiàn)[14]中針對(duì)救援關(guān)鍵期內(nèi)應(yīng)急物資可能供應(yīng)不足的特點(diǎn),考慮適當(dāng)?shù)膬?yōu)化目標(biāo),建立了隨機(jī)需求環(huán)境下應(yīng)急物流車輛路徑問(wèn)題的優(yōu)化模型,并基于遺傳算法設(shè)計(jì)了模型的求解方法．

對(duì)于車輛路徑優(yōu)化問(wèn)題求解,上述研究以節(jié)點(diǎn)之間的線性距離之和最短作為最優(yōu)解,但是在實(shí)際的道路中節(jié)點(diǎn)之間會(huì)存在諸多因素(如道路單向行駛、道路彎曲等)，使得以節(jié)點(diǎn)之間的線性距離最短作為求解結(jié)果難以運(yùn)用在實(shí)際需求之中．文中以鎮(zhèn)江市實(shí)際物流配送路徑合理規(guī)劃為出發(fā)點(diǎn),通過(guò)高德電子地圖提供的對(duì)應(yīng)API接口來(lái)獲取各個(gè)節(jié)點(diǎn)之間的實(shí)際道路導(dǎo)航距離,然后通過(guò)改進(jìn)蟻群算法進(jìn)行優(yōu)化求解,從而將理論與實(shí)際物流配送路徑結(jié)合,具有高度的可行性和實(shí)用性．

1 物流配送數(shù)學(xué)模型

1.1 配送過(guò)程介紹

物流配送過(guò)程可以描述為從物流配送站通過(guò)一定數(shù)量的車輛分別向若干個(gè)客戶節(jié)點(diǎn)派送貨物,車輛配送完貨物后則返回物流配送站．每輛車輛的載貨量有限,為了節(jié)約成本以及提高派送貨物的效率,則必須合理規(guī)劃車輛配送路線,使總行駛路程最短．

1.2 數(shù)學(xué)模型建立

(1) 某一個(gè)節(jié)點(diǎn)的貨物需求只能由一輛車輛來(lái)配送;

Rk1Rk2=Φk1≠k2

(1)

(2) 任意一條路徑上的節(jié)點(diǎn)需求總量之和不能超過(guò)汽車的載重量Qk;

(2)

(3) 所有節(jié)點(diǎn)都必須完成配送

0≤nk≤L

(3)

(4)

(5)

因此,文中的物流配送問(wèn)題需要達(dá)到的最優(yōu)路徑理論目標(biāo)值為:

(6)

2 基本蟻群算法

2.1 基本原理

蟻群算法是受自然界螞蟻覓食行為啟發(fā)而產(chǎn)生的一種自然模擬進(jìn)化算法[15]．文獻(xiàn)[16]中首次闡述了蟻群算法,并對(duì)其數(shù)學(xué)模型做了分析解釋．螞蟻從蟻穴到目的地的覓食過(guò)程描述如下:起初，螞蟻隨機(jī)選擇路徑,后來(lái)路徑選擇會(huì)根據(jù)覓食過(guò)程而搜索新路徑,原因在于螞蟻會(huì)在它們經(jīng)過(guò)的地方釋放一種化學(xué)物質(zhì)(信息素),而這種化學(xué)物質(zhì)的濃度與路徑長(zhǎng)度有關(guān),走過(guò)路徑越長(zhǎng),它的濃度相對(duì)越低,同時(shí)路徑上的該化學(xué)物質(zhì)的量也會(huì)隨著時(shí)間的流逝按照一定的比例逐漸減少,因此對(duì)于較短的路徑上螞蟻釋放的信息素濃度會(huì)更高,如此反復(fù)形成正反饋效應(yīng),直到最后所有的螞蟻都會(huì)走信息素濃度最高的那條路徑,也就是最短路徑．關(guān)于螞蟻覓食過(guò)程的簡(jiǎn)要流程圖如圖1．其中(a)表示所有蟻群都在起點(diǎn)處,路徑上尚未有信息素；(b)表示蟻群開(kāi)始分別以相等的概率向不同的方向覓食；(c)表示走較短路徑的蟻群首先到達(dá)覓食終點(diǎn)；(d)表示螞蟻返回起點(diǎn)過(guò)程中由于較短路徑上信息素濃度較高,所以螞蟻選擇較短路徑的概率要大于較長(zhǎng)路徑的概率,最終根據(jù)正反饋效應(yīng)螞蟻都會(huì)集中在較短路徑上[17]．

圖1 蟻群覓食行為(單位：m)Fig.1 Ant colony foraging behavior map(unit:m)

現(xiàn)實(shí)生活中，人工蟻群算法根據(jù)蟻群覓食的正反饋過(guò)程實(shí)現(xiàn),在自然界的蟻群算法上作了改進(jìn).原始自然界中，蟻群是沒(méi)有記憶功能的,而人工蟻群算法具有一定記憶功能,它會(huì)記住已經(jīng)訪問(wèn)過(guò)的節(jié)點(diǎn)．另外，人工蟻群算法會(huì)根據(jù)算法規(guī)律去選擇下一條最短路徑,它并非無(wú)目的性地選擇下一條路徑．

2.2 求解模型

當(dāng)螞蟻在客戶點(diǎn)i時(shí),它在t時(shí)刻由客戶點(diǎn)i向客戶點(diǎn)j轉(zhuǎn)移的概率為:

(7)

式中：ηij，τij分別為某時(shí)刻客戶點(diǎn)i到客戶點(diǎn)j的可見(jiàn)度以及i到j(luò)路徑上的信息素濃度,且ηij=1/dij;α為信息啟發(fā)因子,β為期望啟發(fā)因子,大小分別對(duì)應(yīng)螞蟻對(duì)信息素量和路線距離長(zhǎng)短的敏感程度;由于每只螞蟻每次巡回只能訪問(wèn)客戶節(jié)點(diǎn)一次,所以用tabu(k)表示第k只螞蟻已經(jīng)訪問(wèn)過(guò)的節(jié)點(diǎn),allowed(k)=R-tabu(k)表示第k只螞蟻還沒(méi)有訪問(wèn)的節(jié)點(diǎn)．

當(dāng)所有的螞蟻完成一次配送循環(huán)后,需要根據(jù)各個(gè)螞蟻遍歷的好壞程度,更新相關(guān)路徑上的信息素,因?yàn)樾畔⑺厥怯绊懳闹兴惴ㄊ諗啃缘闹匾蛩?相關(guān)路徑上信息素的更新規(guī)則:

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

(8)

(9)

式中：ρ為信息素?fù)]發(fā)系數(shù),0≤ρ<1,1-ρ為信息素殘留系數(shù);Δτij(t)和τijk(t)分別為這一次循環(huán)過(guò)程中i到j(luò)路徑上所有的信息素增加量和第k只螞蟻留在路徑上的信息素?cái)?shù)量;m為該循環(huán)過(guò)程中螞蟻數(shù)量;τij(t+n)和τij(t)分別為對(duì)應(yīng)時(shí)刻路徑上的信息素?cái)?shù)量．最后在上述基礎(chǔ)上得到蟻群算法的基本求解模型:

(10)

式中：Q為常數(shù),表示信息素強(qiáng)度,它在一定程度上會(huì)影響算法的收斂速度;Lk為第k只螞蟻在本次循環(huán)中走過(guò)的路徑總長(zhǎng)度[18]．

3 蟻群算法改進(jìn)及其物流配送

3.1 客戶節(jié)點(diǎn)選擇策略改進(jìn)

如圖2,假設(shè)螞蟻經(jīng)過(guò)A,B,C點(diǎn)運(yùn)動(dòng)到了D位置,在D位置螞蟻可以選尚未去過(guò)的E,F,G中任意一點(diǎn)作為下一個(gè)訪問(wèn)節(jié)點(diǎn),且D點(diǎn)到E,F,G這3點(diǎn)的距離/信息素分別是2/2,5/2,3/3．根據(jù)式(7)，在α=1,β=2的條件下可計(jì)算得到從D點(diǎn)到E,F,G這3個(gè)節(jié)點(diǎn)的概率分別為24%,60%和16%．因?yàn)镈到F的概率值大于D到其他點(diǎn)的概率值,所以螞蟻?zhàn)匀贿x擇F點(diǎn)作為下一個(gè)訪問(wèn)節(jié)點(diǎn),同樣，在螞蟻選擇其他節(jié)點(diǎn)時(shí)也會(huì)出現(xiàn)類似情況,這樣全部螞蟻選擇的路徑是相同的,使算法陷入停滯狀態(tài)．采用輪盤選擇策略可以很好解決這一問(wèn)題,首先在[0,1]之間隨機(jī)取一個(gè)數(shù)R,然后用R減去D到E路徑上的概率,倘若得到的結(jié)果≤0，則E點(diǎn)即為下一個(gè)訪問(wèn)節(jié)點(diǎn),否則將得到的結(jié)果繼續(xù)減去D到F路徑上的概率,以此類推直到得到的結(jié)果≤0時(shí)將對(duì)應(yīng)的點(diǎn)作為下個(gè)一訪問(wèn)節(jié)點(diǎn)．通過(guò)采用這種策略可以有效避免算法停滯或陷入局部最優(yōu)解,因?yàn)檫@種方式在螞蟻選擇下一個(gè)訪問(wèn)節(jié)點(diǎn)時(shí)不會(huì)總往概率大的路徑上走,而是向概率大的路徑上走的可能性更大,但是依然有可能向概率小的路徑上走．

圖2 螞蟻簡(jiǎn)略尋跡Fig.2 A simple trace of ants

3.2 信息素?fù)]發(fā)系數(shù)ρ取值改進(jìn)

信息素?fù)]發(fā)系數(shù)ρ是一個(gè)常量,它的取值直接影響算法的求解結(jié)果,若ρ值過(guò)小,則影響算法的收斂速度,取值過(guò)大,則會(huì)使沒(méi)有被搜索過(guò)的路徑被選擇的概率減小,影響算法的全局搜索．所以在求解過(guò)程對(duì)ρ值進(jìn)行調(diào)整,在算法初期為了盡快找到較優(yōu)解，ρ值應(yīng)比較大;到了后期當(dāng)算法停滯不前就可以將ρ值減小,減小信息素對(duì)蟻群的影響,取得更優(yōu)解．ρ值調(diào)整公式如下:

(11)

式中：r為循環(huán)次數(shù);rmax為一常量;μ∈(0,1),也是一個(gè)常量,用來(lái)掌握ρ的衰減速度;ρmin為ρ的最小值,確保ρ不會(huì)因?yàn)檫^(guò)小而影響收斂速度．這里當(dāng)r達(dá)到設(shè)定的rmax時(shí)就減小ρ,然后對(duì)r重新計(jì)數(shù),反復(fù)循環(huán),直到ρ達(dá)到最小值ρmin為止[19]．

3.3 改進(jìn)客戶節(jié)點(diǎn)間距離計(jì)算方式

本算法中計(jì)算最優(yōu)路徑時(shí)去掉基本的蟻群算法通過(guò)傳統(tǒng)方法來(lái)計(jì)算任意兩個(gè)節(jié)點(diǎn)間距離,而是通過(guò)程序調(diào)用高德地圖Web服務(wù)API接口，返回任意兩個(gè)節(jié)點(diǎn)間實(shí)際導(dǎo)航距離，求得最優(yōu)解．

程序中計(jì)算任意兩個(gè)節(jié)點(diǎn)距離的接口服務(wù)地址為https:∥restapi.amap.com/v3/distance?parameters.接口的請(qǐng)求參數(shù)包括key(請(qǐng)求服務(wù)權(quán)限),origins(出發(fā)點(diǎn)),destination(目的地),type(路徑計(jì)算的方式和方法),output(返回?cái)?shù)據(jù)格式類型xml或json,文中取json),callback(回調(diào)函數(shù)).文中，上述請(qǐng)求參數(shù)tpye直接取缺省值,表示駕車導(dǎo)航距離．返回結(jié)果參數(shù)包括status(0表示請(qǐng)求失敗,1表示請(qǐng)求成功)、info(返回狀態(tài)說(shuō)明)、result(距離等信息列表)．這里得到的任意兩個(gè)客戶節(jié)點(diǎn)之間的距離是實(shí)際道路之間的有向距離,而不是傳統(tǒng)方式所采取的根據(jù)勾股定理來(lái)計(jì)算的直線距離,而且通過(guò)接口在不同時(shí)間段取得的值不同,因?yàn)榉?wù)接口中考慮了實(shí)時(shí)路況,躲避了交通擁堵等．

3.4 物流配送流程

物流配送的具體流程如下：首先，確定車輛數(shù)以及客戶點(diǎn)信息；隨后，計(jì)算車輛下一時(shí)刻對(duì)每條路徑的選擇概率，從而確定下一個(gè)即將訪問(wèn)的客戶點(diǎn)，并根據(jù)規(guī)則對(duì)前文中的ρ值進(jìn)行改進(jìn)，滿足條件后返回，依次遍歷每輛車；最后，根據(jù)每輛車的最優(yōu)選擇結(jié)果得出最合適的配送方案.流程圖如圖3.

圖3 物流配送算法流程Fig.3 Algorithm flowchart of logistics

4 實(shí)驗(yàn)結(jié)果與分析

4.1 問(wèn)題描述

物流配送以鎮(zhèn)江市實(shí)際道路點(diǎn)為基礎(chǔ),分別向本市10個(gè)不同的客戶點(diǎn)進(jìn)行物流配送,尋求最優(yōu)的配送路徑．這里以鎮(zhèn)江站位置為物流配送中心,以十里長(zhǎng)山、鎮(zhèn)江南站、江蘇大學(xué)、江科大東校區(qū)、大港中學(xué)、明都大飯店、金山公園、中醫(yī)院、江大附屬醫(yī)院、八佰伴為客戶點(diǎn)位置．物流配送中心車輛充足,且每輛車載質(zhì)量為8 t,10個(gè)客戶點(diǎn)的需求量qi如表1,現(xiàn)在要求合理安排車輛及規(guī)劃路線,使配送過(guò)程的總路程最短．由表1可知10個(gè)客戶節(jié)點(diǎn)總需求量為29.4 t,而每輛車的載質(zhì)量為8 t,初始估計(jì)配送車輛為4輛．

表1 客戶點(diǎn)需求量

另外上述算法中參數(shù)α值過(guò)大，搜索路徑的隨機(jī)性會(huì)減弱,過(guò)小的話會(huì)陷入局部最優(yōu);β值過(guò)大容易選擇局部最短路徑,過(guò)小算法收斂速度太低,通過(guò)計(jì)算分析文中信息啟發(fā)因子α和期望啟發(fā)因子β的取值，分別定為1和2;初期為了盡快找到最優(yōu)解，信息素?fù)]發(fā)系數(shù)ρ取0.95,算法后期根據(jù)實(shí)際情況對(duì)ρ值進(jìn)行調(diào)整;迭代次數(shù)為200．

4.2 結(jié)果與分析

通過(guò)高德地圖服務(wù)API得到的物流配送中心與各個(gè)客戶點(diǎn)以及客戶點(diǎn)和客戶點(diǎn)之間的實(shí)際道路距離如表2．其中(0,0)表示物流配送中心,1～10表示10個(gè)客戶節(jié)點(diǎn),由表2中可知dij和dij距離不相等,這是因?yàn)楸?中所有節(jié)點(diǎn)之間的距離都是根據(jù)API接口取得的實(shí)時(shí)駕車導(dǎo)航距離,而不是傳統(tǒng)的道路節(jié)點(diǎn)之間的直線距離．另外程序在取得道路節(jié)點(diǎn)間的實(shí)際距離時(shí)可以根據(jù)接口傳參考慮諸多因素,如實(shí)時(shí)路況,是否躲避交通擁堵路段,還是不考慮路況直接走最短路線路段,以及不走高速且避開(kāi)收費(fèi)等,通過(guò)高德地圖API取得實(shí)際道路距離后，再使用蟻群算法求得最優(yōu)解．

表2 各節(jié)點(diǎn)之間的實(shí)際道路距離

物流配送路徑的優(yōu)化結(jié)果對(duì)比如表3,表中列出了具有代表性的10次配送路徑、對(duì)應(yīng)的根據(jù)傳統(tǒng)方式得到的節(jié)點(diǎn)間直線行駛路程和根據(jù)實(shí)際道路行駛得到的行駛路程．由表3可知節(jié)點(diǎn)間最小直線行駛路程的最優(yōu)解為62.598 km,但是與其對(duì)應(yīng)的節(jié)點(diǎn)間的實(shí)際道路行駛路程卻不是最小的,而表中第5行所對(duì)應(yīng)的路徑得出的實(shí)際道路行駛路程89.378 km才是最小值．這充分說(shuō)明了在實(shí)際應(yīng)用中,最優(yōu)路徑求解過(guò)程中根據(jù)節(jié)點(diǎn)間的直線距離來(lái)計(jì)算最小路程是難以解決實(shí)際問(wèn)題的,應(yīng)該根據(jù)文中提出的由實(shí)際道路節(jié)點(diǎn)距離來(lái)計(jì)算最優(yōu)路徑,這樣才能得到實(shí)際的最優(yōu)解．這里由于文中提供的客戶點(diǎn)較少且距離比較近,所以不同路徑所對(duì)應(yīng)實(shí)際道路行駛路程相差不是太大,但是在客戶點(diǎn)較多或客戶點(diǎn)之間相距比較遠(yuǎn)時(shí),這種差距就會(huì)十分明顯,且更能體現(xiàn)由實(shí)際道路距離作為最優(yōu)路徑求解結(jié)果的正確性與優(yōu)越性．

在算法收斂性方面,文中的最優(yōu)解在迭代40次以上基本上已經(jīng)趨于穩(wěn)定,迭代過(guò)程中平均路徑長(zhǎng)度和最短路徑長(zhǎng)度如圖4．

表3 路徑優(yōu)化求解結(jié)果對(duì)比

圖4 路徑優(yōu)化結(jié)果收斂Fig.4 Convergence graph of path optimization result

最后,在實(shí)驗(yàn)中根據(jù)傳統(tǒng)蟻群算法和文中改進(jìn)的蟻群算法，同樣在迭代200次的基礎(chǔ)上，以及在相同約束條件下,對(duì)比直線最短路程、平均路程和最大路程，如表4．可知文中改進(jìn)算法相比于未改進(jìn)之前增強(qiáng)了算法的正反饋機(jī)制,避免了算法停滯現(xiàn)象,對(duì)路徑規(guī)劃問(wèn)題具有較好的適應(yīng)性和實(shí)用性．

表4 算法改進(jìn)前后數(shù)據(jù)對(duì)比

5 結(jié)語(yǔ)

文中從物流配送路徑優(yōu)化問(wèn)題出發(fā),以鎮(zhèn)江市實(shí)際道路節(jié)點(diǎn)為基礎(chǔ),通過(guò)改進(jìn)的蟻群算法來(lái)求得配送過(guò)程中所走的實(shí)際道路節(jié)點(diǎn)的最短路程．在前人研究基礎(chǔ)上,文中求得的最優(yōu)路徑并非通過(guò)節(jié)點(diǎn)間直線行駛最短距離來(lái)求得,而是通過(guò)高德API服務(wù)接口獲取各道路節(jié)點(diǎn)之間的實(shí)時(shí)導(dǎo)航距離，并由改進(jìn)的蟻群算法求得最優(yōu)解．實(shí)驗(yàn)結(jié)果證明,傳統(tǒng)求解方式難以應(yīng)用于實(shí)際,而文中提出的求解方式在實(shí)際應(yīng)用中具有更好的應(yīng)用價(jià)值,實(shí)用性更高．