劉慶華,汪 晶

(江蘇科技大學 計算機學院, 鎮(zhèn)江 212003)

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

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

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

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

1.1 配送過程介紹

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

1.2 數(shù)學模型建立

(1) 某一個節(jié)點的貨物需求只能由一輛車輛來配送;

Rk1Rk2=Φk1≠k2

(1)

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

(2)

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

0≤nk≤L

(3)

(4)

(5)

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

(6)

2 基本蟻群算法

2.1 基本原理

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

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

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

2.2 求解模型

當螞蟻在客戶點i時,它在t時刻由客戶點i向客戶點j轉移的概率為:

(7)

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

當所有的螞蟻完成一次配送循環(huán)后,需要根據(jù)各個螞蟻遍歷的好壞程度,更新相關路徑上的信息素,因為信息素是影響文中算法收斂性的重要因素,相關路徑上信息素的更新規(guī)則:

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

(8)

(9)

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

(10)

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

3 蟻群算法改進及其物流配送

3.1 客戶節(jié)點選擇策略改進

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

圖2 螞蟻簡略尋跡Fig.2 A simple trace of ants

3.2 信息素揮發(fā)系數(shù)ρ取值改進

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

(11)

式中：r為循環(huán)次數(shù);rmax為一常量;μ∈(0,1),也是一個常量,用來掌握ρ的衰減速度;ρmin為ρ的最小值,確保ρ不會因為過小而影響收斂速度．這里當r達到設定的rmax時就減小ρ,然后對r重新計數(shù),反復循環(huán),直到ρ達到最小值ρmin為止[19]．

3.3 改進客戶節(jié)點間距離計算方式

本算法中計算最優(yōu)路徑時去掉基本的蟻群算法通過傳統(tǒng)方法來計算任意兩個節(jié)點間距離,而是通過程序調用高德地圖Web服務API接口，返回任意兩個節(jié)點間實際導航距離，求得最優(yōu)解．

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

3.4 物流配送流程

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

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

4 實驗結果與分析

4.1 問題描述

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

表1 客戶點需求量

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

4.2 結果與分析

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

表2 各節(jié)點之間的實際道路距離

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

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

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

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

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

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

5 結語

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