基于Google Maps JavaScript API的物流配送車輛調(diào)度系統(tǒng)設(shè)計(jì)

莫以為，何新彪

MO Yi-wei,HE Xin-biao

（廣西大學(xué) 機(jī)械工程學(xué)院，南寧 530004）

0 引言

車輛調(diào)度問題(VRP--Vehicle Routing Problem)源于旅行商問題（TSP--Traveling Salesman Problem）。該問題描述：在滿足一定約束條件（如貨物總量不可超過車輛容量，每條路線長度不可超過車輛行駛里程，以及車輛服務(wù)節(jié)點(diǎn)時(shí)間必須滿足給定時(shí)間范圍要求等）下，組織適當(dāng)?shù)男熊嚶肪€，使車輛有序地通過指定的一系列服務(wù)（取貨送貨）節(jié)點(diǎn)，并達(dá)到預(yù)定目標(biāo)（如行車總路程最短、費(fèi)用最小、時(shí)間最少、車輛使用量最少等）。VRP包含多條行車路徑，每條路徑就是一個(gè)TSP問題。

目前VRP研究大多集中在該問題的理論及算法領(lǐng)域，例如利用各種啟發(fā)式智能算法（遺傳算法、模擬退火算法、蟻群算法、禁忌搜索算法、人工免疫算法以及混合算法等）求解VRP問題[1,2]。近些年在VRP實(shí)際應(yīng)用研究上，國外研究者結(jié)合各種VRP算法開發(fā)了各式各樣的車輛調(diào)度軟件，例如美國ESRI公司的Arelogisties系統(tǒng)、Roadnet科技公司的Roadnet5000系統(tǒng)、IBM的VSPx系統(tǒng)、美孚的HPCAD系統(tǒng)等[3]。國內(nèi)車輛調(diào)度軟件發(fā)展也較快，如北斗星車輛控制調(diào)度系統(tǒng)等，但普及化程度高的車輛優(yōu)化調(diào)度軟件較少。

GIS的快速發(fā)展使得根據(jù)實(shí)際地圖數(shù)據(jù)完成車輛調(diào)度成為可能，將空間地理數(shù)據(jù)和物流信息數(shù)據(jù)結(jié)合并對配送決策產(chǎn)生作用是開發(fā)車輛調(diào)度軟件的亮點(diǎn)[4,5]。專業(yè)GIS系統(tǒng)，如國外的AutoCAD、ArcGIS、MapInfo、GeoMedi和國內(nèi)的Supermap、MapGIS、GeoStar、TopMap等[6]，其功能強(qiáng)大，但對開發(fā)能力、開發(fā)成本要求高，造成其應(yīng)用門檻高。因此，第三方提供的GIS應(yīng)用服務(wù)成為了非專業(yè)GIS人員應(yīng)用的首選，Google Maps JavaScript API正是適應(yīng)這種需求而出現(xiàn)的[7]。Google免費(fèi)開放其地圖API供用戶調(diào)用，用戶只需學(xué)習(xí)API使用文檔即可在自己的系統(tǒng)上完成專業(yè)GIS系統(tǒng)所具有的功能，且操作調(diào)用簡單，不必花費(fèi)大量人力物力去維護(hù)地理信息數(shù)據(jù)。

鑒于專業(yè)GIS的高成本性，本文通過Google Maps JavaScript API提供的GIS應(yīng)用服務(wù)接口獲得相關(guān)空間地理信息并與物流信息緊密結(jié)合，采用模擬退火遺傳混合算法（SAGA，Simulated Annealing Genetic Algorithm）設(shè)計(jì)簡單可行、低成本的物流配送VRP解決方案。

1 系統(tǒng)架構(gòu)與功能

1.1 系統(tǒng)結(jié)構(gòu)

圖1 總體架構(gòu)與主要流程示意圖

本文系統(tǒng)設(shè)計(jì)基于B/S模式方案；后臺服務(wù)器語言采用C#編程，主要完成算法求解功能；服務(wù)器數(shù)據(jù)庫采用SQL server 2000，用于存儲客戶、車輛、訂單貨物以及路徑數(shù)據(jù)；客戶端采用Ajax技術(shù)，包括JavaScript、XML、HTML/XHTML、DOM、CSS、XMLHTTP等語言，主要完成客戶端與Web應(yīng)用服務(wù)器、Google Maps服務(wù)器的通信交互。總體架構(gòu)和主要流程如圖1所示。

1.2 功能概述

圖1中的步驟1-8實(shí)現(xiàn)向Google Maps服務(wù)器請求提取系統(tǒng)中所有任意兩個(gè)節(jié)點(diǎn)（包括配送中心地點(diǎn)和客戶地點(diǎn)）之間的有向最短道路距離，并將其存儲到Web數(shù)據(jù)庫。Google Maps服務(wù)器會提供若干條兩節(jié)點(diǎn)之間的行駛建議路線，此處提取里程最短那條路線的距離，且因考慮了實(shí)際道路單行道不可掉頭及左行車道與右行車道路徑長短存在差異等情況，節(jié)點(diǎn)甲→乙與乙→甲的距離大小往往存在一定差異，故稱為有向最短道路距離。

圖1中的步驟9-15為具體求解一次車輛調(diào)度過程。在用戶請求下，Web服務(wù)器根據(jù)調(diào)度任務(wù)即訂單信息，獲取相關(guān)節(jié)點(diǎn)信息及節(jié)點(diǎn)間路徑信息，采用SAGA算法在用戶指定算法參數(shù)設(shè)置條件下完成路徑優(yōu)化，并最終在地圖上顯示結(jié)果。

2 路徑提取與存儲

提供給SAGA算法使用的路徑數(shù)據(jù)（有向最短道路距離）存儲于Web數(shù)據(jù)庫中。僅當(dāng)配送系統(tǒng)有新客戶加入時(shí)，才需向Google Maps服務(wù)器提取該新節(jié)點(diǎn)與已有節(jié)點(diǎn)之間的路徑數(shù)據(jù)并存儲到Web數(shù)據(jù)庫中，其過程如圖1中的步驟1-8所示。

2.1 地圖加載

首先在web頁面HTML源文件中利用URL地址導(dǎo)入Google Maps JavaScript API應(yīng)用函數(shù)接口庫文件，如下所示。

隨后進(jìn)行地圖初始化參數(shù)設(shè)置，主要包括地圖對象、地圖路徑導(dǎo)航服務(wù)請求對象、地圖縮放比例、地圖路徑導(dǎo)航顯示對象、地圖中心點(diǎn)、地圖類型、地圖顯示容器、街景模式、交通狀況等屬性的設(shè)置。

2.2 提取請求參數(shù)設(shè)置

主要完成路徑導(dǎo)航服務(wù)請求對象google.maps.DirectionsService()、路徑導(dǎo)航顯示對象google.maps.DirectionsRenderer()、請求對象request參數(shù)的設(shè)定。request參數(shù)包括起點(diǎn)地址、終點(diǎn)地址、是否提供備用路線、是否避開高速路、是否避開收費(fèi)站、出行方式等。其中起點(diǎn)地址和終點(diǎn)地址為系統(tǒng)中需要提取路徑數(shù)據(jù)的兩個(gè)不同的客戶節(jié)點(diǎn)地址，系統(tǒng)定義節(jié)點(diǎn)甲→乙與乙→甲的路徑為兩個(gè)不相同路徑，地址可以是能被Google Maps JavaScript API正確解析文字格式地址或經(jīng)緯度格式地址。

2.3 兩節(jié)點(diǎn)間路徑數(shù)據(jù)提取與存儲

客戶端通過函數(shù)directionsService.route(request,function(result,status) 向Google Maps 服務(wù)器發(fā)送request參數(shù)以請求路徑導(dǎo)航服務(wù)。若返回的status=OK，表示請求成功，否則表示無響應(yīng)或響應(yīng)錯(cuò)誤，此時(shí)提取不到路徑數(shù)據(jù)，則賦為有向最短道路距離無窮大。反復(fù)循環(huán)，直至所需路徑數(shù)據(jù)全部提取完。最后，將提取到的路徑數(shù)據(jù)及相關(guān)信息儲存到Web數(shù)據(jù)庫中，包括起點(diǎn)信息（編號、名稱、地址、經(jīng)緯度）、終點(diǎn)信息（編號、名稱、地址、經(jīng)緯度）、條件（是否避開高速路、是否避開收費(fèi)站、出行方式）及起點(diǎn)到終點(diǎn)的有向最短道路距離。

3 配送車輛調(diào)度與基于SAGA算法的求解

3.1 配送車輛調(diào)度問題描述

本文所研究的是配送中心給若干客戶配送的車輛調(diào)度問題，假設(shè)其路線是封閉的（即起點(diǎn)和終點(diǎn)同為配送中心），不考慮時(shí)間窗[8]，且車型單一（車輛容量為q，車輛凈重為Q），其數(shù)量不受限。假定配送客戶（節(jié)點(diǎn)）集，A={Ai}，i∈{0,1,...,n}，其中A0為配送中心，客戶Ai貨物需求量為gi（且假定gi≤q），且令配送中心貨物需求量g0=0；所需最少車輛數(shù)為m；第k輛車的行車路徑稱為第條子路徑，由所經(jīng)nk個(gè)節(jié)點(diǎn)與配送中心組成，第k輛的nk個(gè)節(jié)點(diǎn)集為pk，其節(jié)點(diǎn)元素依次為，節(jié)點(diǎn)pk(l-1)與pkl間的距離為dpk(l-1)pkl；為方便起見假設(shè)其中pk0、pk(nk+1)均表示配送中心0，則配送車輛調(diào)度優(yōu)化數(shù)學(xué)模型如下：

式(1)為目標(biāo)函數(shù)，表示該任務(wù)運(yùn)輸噸公里數(shù)，其中小括弧內(nèi)表示車輛從節(jié)點(diǎn)pk(l-1)到節(jié)點(diǎn)pkl時(shí)車輛的總重量（包括車輛凈重和貨物重量），中括弧表示到達(dá)pkl時(shí)的噸公里數(shù)；式(2)為約束條件，表示單輛車服務(wù)的所有客戶需求總量不大于車輛容量；式(3)表示所有車輛服務(wù)的客戶節(jié)點(diǎn)總數(shù)為n，且任意不同的兩輛車服務(wù)的客戶節(jié)點(diǎn)不重復(fù)；式(4)表示所需最少車輛數(shù)，中括弧表示取整。具體實(shí)現(xiàn)步驟如下：首先，根據(jù)式(4)確定某配送任務(wù)的出車數(shù)量m，并保持不變，把問題簡化為m個(gè)路徑優(yōu)化問題；然后在約束條件式(2)和式(3)下通過路徑的選擇對目標(biāo)函數(shù)1-1進(jìn)行優(yōu)化，確定優(yōu)化調(diào)度方案。

通過分析各種路徑規(guī)劃的智能算法優(yōu)劣性，采用SAGA進(jìn)行求解。該算法因遺傳算法GA的強(qiáng)大全局搜索能力可快速地搜索出全局較優(yōu)解，同時(shí)在GA主循環(huán)中插入模擬退化算法SA，利用其良好的局部搜索能力以彌補(bǔ)GA的局部搜索能力較差不足，尋求全局最優(yōu)解。具體地說，采用SAGA算法對m輛車的路徑（包含起點(diǎn)配送中心）的構(gòu)成長度為m+n+1的方案編碼進(jìn)行優(yōu)化，這是為了便于交叉、變異等算子的操作，該編碼方案直觀，不需解碼，兩個(gè)數(shù)字0之間的路徑即為一輛車的行駛路徑。例如，m=3、n=8的路徑編碼047803602510表示3輛車對8個(gè)客戶進(jìn)行送貨的路線安排，3輛車的路線分別為04780,0360,02510。由此，利用所獲相關(guān)GIS地理數(shù)據(jù)與物流信息數(shù)據(jù)，采用SAGA算法搜尋優(yōu)化配送方案，完成配送車輛調(diào)度。

3.2 基于SAGA的優(yōu)化算法

SAGA算法中的個(gè)體表示長度為m+n+1的路徑編碼，且無論隨機(jī)、換位法、交叉、變異產(chǎn)生的新個(gè)體都必須滿足約束式(2)和式(3)的要求。求解步驟如下：

1）設(shè)定種群規(guī)模N，總繁殖代數(shù)X，初始代數(shù)x=0，初始溫度t0，第x代溫度tx，a為退火率；隨機(jī)產(chǎn)生規(guī)模為N的初始種群P0，在P0中搜索最小值Jmin的個(gè)體Smin;

2）判斷x是否超過總繁殖代數(shù)或個(gè)體Smin連續(xù)最佳保持了X0代：若是則退出，并輸出Jmin、Smin；否則轉(zhuǎn)到3）;

（3）重復(fù)(1)～(2)步驟L次（L為馬爾科夫鏈長度，且L=γ*n，γ一般取100，n為自變量維數(shù)，即客戶節(jié)點(diǎn)數(shù)）[9]；

4）在第x代種群Px中搜索目標(biāo)函數(shù)值J(x)min最小的個(gè)體Sx；比較J(x)min〈Jmin，是則Jmin=J(x)min，Smin=Sx；

5）在Px中按照輪盤賭選擇法產(chǎn)生父代1和父代2[10]，即以個(gè)體目標(biāo)函數(shù)值越小被選中的概率也越大的思想選擇個(gè)體；以概率pc對父代1和父代2進(jìn)行交叉產(chǎn)生一個(gè)子代個(gè)體[11]，若交叉不成功，各以一半的概率選擇其中一父代作為子代個(gè)體；以概率pm對該子代個(gè)體進(jìn)行變異操作產(chǎn)生新個(gè)體以代替該個(gè)體[12]，若變異不成功，保持該個(gè)體作為子代個(gè)體；

6）重復(fù)步驟5）直到產(chǎn)生N個(gè)子代個(gè)體構(gòu)成種群Px+1；x=x+1，tx=a*tx；返回步驟2）。

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

假設(shè)配送客戶節(jié)點(diǎn)數(shù)n =20，各節(jié)點(diǎn)需求量如表1所示，并根據(jù)客戶地址利用上述方法從Google Maps獲得各節(jié)點(diǎn)間的有向路徑距離矩陣如表2所示。

假設(shè)車輛載重量q=6噸，凈重Q=2噸，根據(jù)表1數(shù)據(jù)與式1-4確定所需最少車輛數(shù)m=3；設(shè)SAGA算法參數(shù)選擇為：種群大小N=100，連續(xù)最佳代數(shù)X0=300，總繁殖代數(shù)X=1000，交叉率pc=0.95，變異率pm=0.01，退火率a=0.95，初溫t0=[max（dij）]*n（i,j∈n，且i≠j）；實(shí)驗(yàn)條件（環(huán)境下）：CUP2.6GHz、內(nèi)存1.0GB、網(wǎng)絡(luò)帶寬512Kbps、Windows XP系統(tǒng)。

在上述實(shí)驗(yàn)環(huán)境下，從Google地圖服務(wù)器提取到了表2中全部420條路徑數(shù)據(jù)用時(shí)5分鐘；用SAGA算法從46代開始找到總噸公里數(shù)最小的路徑（05820671516190134111221010143171890），且該路徑連續(xù)保持最小至346代，用時(shí)17秒，其總噸公里數(shù)為301.6噸公里，總路徑長度為74.5km，所得3輛車路徑分別如圖2-圖4所示。

圖2 第1輛車路徑

表1 各客戶節(jié)點(diǎn)貨物需求量gi（噸）

表2 各節(jié)點(diǎn)間路徑距離dij矩陣表（km）

圖3 第2輛車路徑

圖4 第3輛車路徑

實(shí)驗(yàn)結(jié)果表明，在網(wǎng)絡(luò)數(shù)據(jù)傳輸穩(wěn)定時(shí)可方便從Google地圖服務(wù)器獲取數(shù)據(jù)，同時(shí)考慮到配送中心客戶相對較穩(wěn)定的特點(diǎn)，文中提出獲取路徑信息方法是可行的。另一方面，增加X和X0的值可搜索出更優(yōu)的個(gè)體，因此通過合理設(shè)置算法參數(shù)可改善種群逐代收斂性能，在不超過總繁殖代數(shù)X內(nèi)搜索出了連續(xù)最佳保持X0代的優(yōu)化個(gè)體。經(jīng)過實(shí)驗(yàn)驗(yàn)證，在算法參數(shù)N=20～100，X0=100～300，X=500～1000，pc=0.6～0.95，pm=0.001～0.01，a=0.75～0.95設(shè)定下[9,10]，對于客戶節(jié)點(diǎn)數(shù)n為100以下中小規(guī)模物流配送問題，本系統(tǒng)能在1分鐘內(nèi)給出較優(yōu)路徑方案，完成車輛調(diào)度。

5 結(jié)論

本文車輛調(diào)度算法所用節(jié)點(diǎn)間路徑數(shù)據(jù)源于業(yè)內(nèi)公認(rèn)衡量其他地圖軟件默認(rèn)標(biāo)準(zhǔn)的Google地圖[14]，其提供清晰的衛(wèi)星照片地圖更證明了Google地圖數(shù)據(jù)的真實(shí)可靠性和準(zhǔn)確性。本文通過Google Maps JavaScript API實(shí)現(xiàn)了Google Maps與實(shí)際物流配送系統(tǒng)結(jié)合決策生成VRP優(yōu)化方案的應(yīng)用系統(tǒng)，利用Google地圖道路網(wǎng)數(shù)據(jù)與物流配送信息結(jié)合，通過SAGA的模擬退火算法和遺傳算法的各自優(yōu)勢能較好地解決物流配送VRP問題。采用Google地圖道路網(wǎng)數(shù)據(jù)取代兩節(jié)點(diǎn)間直線距離數(shù)據(jù)，并以車輛運(yùn)輸總噸公里數(shù)代替運(yùn)輸總路徑長度作為優(yōu)化目標(biāo)函數(shù)，更符合真實(shí)情況與實(shí)際需要。與此同時(shí)，系統(tǒng)的開發(fā)與維護(hù)成本低，具有較好的實(shí)用價(jià)值，還可將本方案延伸至VRP的變種問題，并結(jié)合車輛監(jiān)控系統(tǒng)等可構(gòu)成更加完善的配送管理系統(tǒng)。因此，本文給出的車輛調(diào)度方案對眾多中小物流企業(yè)實(shí)際解決VRP具有一定的參考價(jià)值。

[1] 孫麗君,胡祥培,王征.車輛路徑規(guī)劃問題及其求解方法研究進(jìn)展[J].系統(tǒng)工程,2006,24(11)：31-37.

[2] Asvin Goel,Volker Gruh.A General Vehicle Routing Problem[J].European Journal of Operational Research,191(2008)：650-660.

[3] 王廠.基于Google Map ApI的郵政運(yùn)輸調(diào)度系統(tǒng)的分析與設(shè)計(jì)[D].濟(jì)南：山東大學(xué),2010.

[4] 劉昕雨.GIS技術(shù)及路徑優(yōu)化算法在煙草物流配送中的應(yīng)用研究[D].重慶：重慶大學(xué),2009.

[5] 楊湘燕.基于WebGIS的物流配送路徑規(guī)劃系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[D].廈門：廈門大學(xué),2009.

[6] 夏鼎.改進(jìn)的蟻群算法解決車輛路徑問題及其WebGIS實(shí)現(xiàn)[D].上海：上海交通大學(xué),2009.

[7] Google Maps JavaScript API V3. http：//code.google.com/intl/zh-CN/apis/maps/documentation/javascript /basics.html.

[8] 秦本濤.基于遺傳算法的車輛調(diào)度系統(tǒng)設(shè)計(jì)[D].浙江工業(yè)大學(xué),2009.

[9] 王銀年,葛洪偉.求解TSP問題的改進(jìn)模擬退火遺傳算法[J].計(jì)算機(jī)工程與應(yīng)用,2010,46(5)：44-48.

[10]張建光.基于退火遺傳算法的戰(zhàn)時(shí)非滿載車輛調(diào)度問題研究[D].國防科學(xué)技術(shù)大學(xué),2009.

[11]但正剛.基于多代理的兩階段實(shí)時(shí)車輛調(diào)度系統(tǒng)研究[D].清華大學(xué),2008.

[12]美國在線地圖軟件測評：谷歌居首必應(yīng)次之.http：//tech.qq.com/a/20101006/000072.htm.