高德地圖及改進(jìn)ACA在車輛路徑尋優(yōu)中的應(yīng)用*

劉慶華 汪 晶

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

1 引言

隨著經(jīng)濟(jì)和科學(xué)技術(shù)的快速發(fā)展，現(xiàn)實(shí)生活中車輛的普及率越來越高，汽車私人擁有量也急劇增加。而這些都使得出行者迫切需要正確的出行路徑，因此路線規(guī)劃問題成為了廣大國(guó)內(nèi)外學(xué)者研究的一項(xiàng)重要課題［1～3］。近些年來，國(guó)內(nèi)外許多學(xué)者對(duì)路徑規(guī)劃問題進(jìn)行了大量的研究，這些研究主要集中在理論及算法領(lǐng)域方面，其中旅游業(yè)和物流業(yè)等行業(yè)中合理的路線規(guī)劃能夠?yàn)樯碳夜?jié)約成本，創(chuàng)造更高的價(jià)值［4～6］。

在國(guó)外汽車行業(yè)相對(duì)于國(guó)內(nèi)較為發(fā)達(dá)，所以早在1959年Dantzig和 Ramser等［7］首次提出了物流配送路徑優(yōu)化問題，之后便引起了計(jì)算機(jī)應(yīng)用等諸多領(lǐng)域的研究者們的高度重視，并很快成為了組合優(yōu)化領(lǐng)域和運(yùn)籌學(xué)的研究熱點(diǎn)及前沿問題。從而使得各個(gè)領(lǐng)域?qū)W者們對(duì)上述問題進(jìn)行了大量的資料查找、理論研究和實(shí)驗(yàn)分析，并獲得了較大的進(jìn)步和成果。20世紀(jì)末Dorigo M等［8］在他們的論文中提出了蟻群系統(tǒng)（ACS），一種應(yīng)用于旅行商問題（TSP）的分布式算法，也就是通過ACS算法研究路徑規(guī)劃問題，在文中他們通過ACS算法和模擬退火算法等進(jìn)行比較結(jié)果表明ACS算法理論上更好地解決了TSP問題。Juyoung等［9］在他們的研究中針對(duì)大型貨柜在建筑工地及購(gòu)物區(qū)堆積大量的垃圾，提出了一種滾動(dòng)式廢物收集車輛路徑優(yōu)化問題。Mahmoudi M等［10］提出了基于時(shí)空交通網(wǎng)絡(luò)中車輛承載狀態(tài)集成的VRPPDTW時(shí)間離散多商品網(wǎng)絡(luò)流模型，通過時(shí)間窗口（VRPPDTW）解決了一類復(fù)雜的車輛路線問題。在國(guó)內(nèi)，張維澤等［11］建立了帶約束條件的物流配送問題的數(shù)學(xué)模型，運(yùn)用蟻群算法解決物流配送路徑優(yōu)化問題，同時(shí)將遺傳算法的復(fù)制、交叉和變異等遺傳算子引入蟻群算法，以提高算法的收斂速度和全局搜索能力。程碧榮［12］等針對(duì)救援關(guān)鍵期內(nèi)應(yīng)急物資可能供應(yīng)不足的特點(diǎn)，考慮適當(dāng)?shù)膬?yōu)化目標(biāo)，建立了隨機(jī)需求環(huán)境下應(yīng)急物流車輛路徑問題的優(yōu)化模型，并基于遺傳算法設(shè)計(jì)了模型的求解方法。

對(duì)于車輛路徑優(yōu)化問題，絕大多數(shù)研究者們?cè)诒姸嗟姆抡鎸?shí)驗(yàn)案例中都是采用道路節(jié)點(diǎn)之間的線性距離之和最短作為最優(yōu)解，但是在實(shí)際的道路節(jié)點(diǎn)之間會(huì)存在諸多因素導(dǎo)致與節(jié)點(diǎn)之間的線性距離相差甚遠(yuǎn)。由此本文根據(jù)鎮(zhèn)江市的實(shí)際物流配送路徑合理規(guī)劃為出發(fā)點(diǎn)，提出了一種首先通過高德地圖提供的對(duì)應(yīng)API接口來獲取各個(gè)道路節(jié)點(diǎn)之間的實(shí)際道路距離，然后交給改進(jìn)的蟻群算法進(jìn)行優(yōu)化得到最優(yōu)解，從而有效地將理論與實(shí)際物流配送路徑相結(jié)合，具有高度的可行性和實(shí)用性。

2 高德地圖API簡(jiǎn)介

高德地圖API是一組基于云的地圖服務(wù)接口，包括互聯(lián)網(wǎng)地圖API和手機(jī)地圖API。高德地圖API通過互聯(lián)網(wǎng)、移動(dòng)互聯(lián)網(wǎng)向桌面和移動(dòng)終端用戶提供豐富的地圖服務(wù)功能，如地圖顯示、標(biāo)注、位置檢索、駕車出行方案檢索、公交查詢、地址解析等。通過高德地圖API，開發(fā)者可以輕松地在自己的應(yīng)用中定制強(qiáng)大、快速、輕便的地圖功能。基于高德地圖的云服務(wù)接口，開發(fā)者無需考慮系統(tǒng)維護(hù)，無需購(gòu)買地圖數(shù)據(jù)，便可以結(jié)合業(yè)務(wù)需求快速構(gòu)建地圖應(yīng)用，可大大降低地圖服務(wù)的使用成本［13］。其中高德Web服務(wù)API向開發(fā)者提供HTTP接口，開發(fā)者可通過這些接口使用各類型的地理數(shù)據(jù)服務(wù)，返回結(jié)果支持JSON和XML格式。本文中提到的道路節(jié)點(diǎn)之間的實(shí)際距離就是通過高德Web服務(wù)API中的對(duì)應(yīng)請(qǐng)求接口獲取的。

3 物流配送的數(shù)學(xué)模型建立及蟻群算法

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

3.1.1 物流配送過程介紹

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

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

建立數(shù)學(xué)模型需要引入以下符號(hào)定義：物流汽車數(shù)量K（1，2…K），汽車的載重量Qk；配送的客戶點(diǎn)個(gè)數(shù)為L(zhǎng)，客戶點(diǎn)集合為R=（R=｛i｝|i=1，2…L），客戶點(diǎn)的需求量為qi；dij為客戶i到客戶j的距離，其中i、j=0，1，2…L，當(dāng)i=j=0時(shí)表示配送中心；nk為車輛k（k=1，2…K）配送的客戶總數(shù)，當(dāng) nk=0時(shí)，表示車輛k沒有參與配送；Rk為車輛k配送的客戶點(diǎn)集合，當(dāng) nk=0時(shí)，Rk=Φ ，當(dāng) nk≠0時(shí)，Rk=其中表示在車輛k配送客戶點(diǎn)集合中第i個(gè)配送的客戶。根據(jù)實(shí)際情況物流配送路線優(yōu)化需要滿足如下約束條件。

1）某一個(gè)客戶點(diǎn)的貨物需求只能由一輛車輛來配送；

2）任意一條路徑上的客戶需求總量之和不能超過汽車的載重量Qk；

3）所有客戶點(diǎn)都必須完成配送

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

3.2 基本蟻群算法

3.2.1 蟻群算法的基本原理

蟻群算法是受自然界螞蟻覓食行為的啟發(fā)而產(chǎn)生的一種自然模擬進(jìn)化算法。20世紀(jì)90年代，M.Dorigo在他的博士論文中闡述了蟻群算法，并對(duì)其數(shù)學(xué)模型做了分析解釋。

螞蟻從蟻穴到目的地覓食的大致過程可以描述如下：起初螞蟻選擇路徑是隨機(jī)的，后來路徑的選擇會(huì)隨著覓食的過程而適應(yīng)性的搜索新的路徑，原因在于螞蟻會(huì)在它們經(jīng)過的地方釋放信息素這一化學(xué)物質(zhì)，而路徑上的信息素濃度與路徑長(zhǎng)度有關(guān)，經(jīng)過路徑越長(zhǎng)，則路徑上的信息素濃度相對(duì)越低，同時(shí)路徑上的信息素也會(huì)隨著時(shí)間的流逝按照一定的比例逐漸減少，因此對(duì)于較短的路徑上螞蟻釋放的信息濃度會(huì)更高，如此反復(fù)形成正反饋效應(yīng)，直到最后所有的螞蟻都會(huì)走信息素濃度最高的那條路徑，也就是最短路徑。關(guān)于螞蟻覓食過程的簡(jiǎn)要流程圖如圖1所示。其中圖1中（a）表示所有蟻群都在起點(diǎn)處，路徑上尚未有信息素，（b）表示蟻群開始分別以相等的概率向不同的方向覓食，（c）表示走較短路徑的蟻群首先到達(dá)覓食終點(diǎn)，（d）表示螞蟻返回起點(diǎn)過程中由于較短路徑上信息素濃度較高，所以螞蟻選擇較短路徑的概率要大于較長(zhǎng)路徑的概率，最終根據(jù)正反饋效應(yīng)螞蟻都會(huì)集中在較短路徑上［14～15］。

圖1 蟻群覓食行為圖

現(xiàn)實(shí)生活中的人工蟻群算法原理就是根據(jù)蟻群覓食的這種正反饋過程來實(shí)現(xiàn)的，但是人工蟻群算法在自然界的蟻群算法上做了改進(jìn)，原始自然界中的蟻群是沒有記憶功能的，而人工蟻群算法具有一定的記憶功能，它會(huì)記住已經(jīng)訪問過的節(jié)點(diǎn)。另外就是人工蟻群算法在選擇下一條路徑的時(shí)候并不是完全毫無無目的性的去選擇，而是按照一定的算法規(guī)律去尋找最短路徑。

3.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的可見度以及i到j(luò)路徑上的信息素濃度，且ηij=1/dij；α為信息啟發(fā)因子，β為期望啟發(fā)因子，大小分別對(duì)應(yīng)螞蟻對(duì)信息素量和路線距離長(zhǎng)短的敏感程度；由于每只螞蟻每次巡回只能訪問客戶節(jié)點(diǎn)一次，所以用tabu（k）表示第k只螞蟻已經(jīng)訪問過的客戶點(diǎn)，allowed（k）=R-tabu（k）表示第k只螞蟻尚未訪問的客戶點(diǎn)。

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

式（8）、（9）中ρ表示信息素?fù)]發(fā)系數(shù)，0≤ρ＜1，1-ρ表示信息素殘留系數(shù)和分別表示本次循環(huán)過程中路徑（i，j）上的信息素增量和第k只螞蟻留在該路徑上的信息素?cái)?shù)量；m表示該循環(huán)過程中螞蟻數(shù)量；τij(t+n)和τij(t)分別表示對(duì)應(yīng)時(shí)刻在路徑上的信息素?cái)?shù)量。最后在上述基礎(chǔ)上得到蟻群算法的基本求解模型：

式（10）中Q為常數(shù)，表示信息素強(qiáng)度，它在一定程度上會(huì)影響算法的收斂速度，Lk為第k只螞蟻在本次循環(huán)中走過的路徑總長(zhǎng)度［16］。

3.3 蟻群算法的改進(jìn)

3.3.1 客戶點(diǎn)選擇策略的改進(jìn)

圖2 螞蟻簡(jiǎn)略尋跡圖

如圖2所示，假設(shè)螞蟻在D點(diǎn)，ABC為已經(jīng)去過的客戶點(diǎn)，EFG為沒去過的點(diǎn)，現(xiàn)在螞蟻要在EFG中選擇一個(gè)點(diǎn)作為下一步要到達(dá)的點(diǎn)。且D到E，F(xiàn)，G點(diǎn)的信息素/距離如圖2所示，那么理論上在α=1，β=2根據(jù)式（7）算得D到E，F(xiàn)，G的概率為24%，60%，16%，這樣選擇會(huì)導(dǎo)致一個(gè)問題，每只螞蟻到了D點(diǎn)都會(huì)選擇F點(diǎn)作為下一個(gè)訪問點(diǎn)，同樣在其他的點(diǎn)上也會(huì)有這種情況發(fā)生，就是每只螞蟻選擇的下一個(gè)點(diǎn)都是同一個(gè)點(diǎn)，這會(huì)導(dǎo)致所有螞蟻找到的路徑都是相同的，會(huì)使螞蟻失去探索新路徑的機(jī)會(huì)，算法陷入停滯。因此文中采用輪盤選擇法，在［0，1］之間取一個(gè)隨機(jī)數(shù)R。然后用R減D到E的概率，如果減去后的結(jié)果小于等于0就選E作為下一個(gè)點(diǎn)，如果減去后還大于0，就繼續(xù)再減去D到F的概率，直到減去后的結(jié)果小于等于0。然后用最后減去時(shí)的那個(gè)概率值對(duì)應(yīng)的點(diǎn)作為下一個(gè)點(diǎn)。使用輪盤選擇法可以使螞蟻往概率值大的地方走的可能性大，但也有一定的可能往概率小的地方走，這樣可以使螞蟻探索新的路徑，避免算法停滯或者進(jìn)入局部最優(yōu)解。

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

信息素?fù)]發(fā)系數(shù)ρ是一個(gè)常量，它的取值直接影響算法的求解結(jié)果，若ρ取值過小，則影響算法的收斂速度，取值過大，則會(huì)使沒有被搜索過的路徑被選擇的概率減小，影響算法的全局搜索。所以在求解過程中對(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è)常量，控制ρ的衰減速度；ρmin為ρ的最小值，確保ρ不會(huì)因?yàn)檫^小而影響收斂速度。這里當(dāng)r達(dá)到設(shè)定的rmax時(shí)就減小ρ，然后對(duì)r重新計(jì)數(shù)，反復(fù)循環(huán)，直到ρ達(dá)到最小值ρmin為止。

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

本文算法中求解最優(yōu)路徑結(jié)果時(shí)去掉基本的蟻群算法通過傳統(tǒng)方法來計(jì)算任意兩個(gè)節(jié)點(diǎn)的距離，而是通過程序調(diào)用高德地圖web服務(wù)API接口返回任意兩個(gè)節(jié)點(diǎn)間的實(shí)際導(dǎo)航距離來求得最優(yōu)解。通過該改進(jìn)，可以提高算法的實(shí)用性和運(yù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)說明），result（距離等信息列表）。這里得到的任意兩個(gè)客戶節(jié)點(diǎn)之間的距離是實(shí)際道路之間的有向距離，而不是傳統(tǒng)算法所采取的根據(jù)勾股定理來計(jì)算的直線距離，而且通過接口在不同時(shí)間段取得的值不同，因?yàn)榉?wù)接口中考慮了實(shí)時(shí)路況，躲避了交通擁堵等。

3.4 物流配送的算法流程圖

物流配送的算法流程簡(jiǎn)圖如圖3所示。

圖3 算法流程簡(jiǎn)圖

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

4.1 實(shí)驗(yàn)問題描述

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

表1 客戶點(diǎn)需求量（單位：噸）

根據(jù)表1可知客戶總需求量為29.4噸，而每輛車的載重量為8噸，初始估計(jì)配送車輛為4輛。算法初始化參數(shù)設(shè)置為信息啟發(fā)因子α=1，期望啟發(fā)因子β=2，信息素?fù)]發(fā)系數(shù)初始值ρ=0.95，后期根據(jù)實(shí)際情況在程序中對(duì)ρ的取值進(jìn)行調(diào)整，迭代次數(shù)為200。

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

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

根據(jù)上述初始化條件，程序運(yùn)行結(jié)果可以得到表3所示的物流配送路徑的優(yōu)化結(jié)果對(duì)比表，表中總結(jié)出了具有代表性的10次配送路徑，以及對(duì)應(yīng)的根據(jù)傳統(tǒng)方式得到的節(jié)點(diǎn)間直線行駛路程和根據(jù)實(shí)際道路行駛得到的行駛路程。由表3可知節(jié)點(diǎn)間最小直線行駛路程的最優(yōu)解為62.598km，但是與其對(duì)應(yīng)的節(jié)點(diǎn)間的實(shí)際道路行駛路程卻不是最小的，而是表中第5行所對(duì)應(yīng)的路徑得出的實(shí)際道路行駛路程89.378km才是最小值。這充分說明了在實(shí)際應(yīng)用中，最優(yōu)路徑求解根據(jù)節(jié)點(diǎn)間的直線距離來計(jì)算最小路程是難以解決實(shí)際問題的，應(yīng)該根據(jù)本文中提出的由實(shí)際道路節(jié)點(diǎn)距離來計(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)定，迭代過程中平均路徑長(zhǎng)度和最短路徑長(zhǎng)度如圖4所示。

圖4 路徑優(yōu)化結(jié)果收斂圖

表2 各節(jié)點(diǎn)之間的實(shí)際道路距離（單位：km）

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

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

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

5 結(jié)語(yǔ)

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