莫以為，何新彪

MO Yi-wei,HE Xin-biao

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

0 引言

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

目前VRP研究大多集中在該問題的理論及算法領(lǐng)域，例如利用各種啟發(fā)式智能算法（遺傳算法、模擬退火算法、蟻群算法、禁忌搜索算法、人工免疫算法以及混合算法等）求解VRP問題[1,2]。近些年在VRP實際應(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ù)據(jù)完成車輛調(diào)度成為可能，將空間地理數(shù)據(jù)和物流信息數(shù)據(jù)結(jié)合并對配送決策產(chǎn)生作用是開發(fā)車輛調(diào)度軟件的亮點[4,5]。專業(yè)GIS系統(tǒng)，如國外的AutoCAD、ArcGIS、MapInfo、GeoMedi和國內(nèi)的Supermap、MapGIS、GeoStar、TopMap等[6]，其功能強大，但對開發(fā)能力、開發(fā)成本要求高，造成其應(yīng)用門檻高。因此，第三方提供的GIS應(yīng)用服務(wù)成為了非專業(yè)GIS人員應(yīng)用的首選，Google Maps JavaScript API正是適應(yīng)這種需求而出現(xiàn)的[7]。Google免費開放其地圖API供用戶調(diào)用，用戶只需學(xué)習(xí)API使用文檔即可在自己的系統(tǒng)上完成專業(yè)GIS系統(tǒng)所具有的功能，且操作調(diào)用簡單，不必花費大量人力物力去維護地理信息數(shù)據(jù)。

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

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

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

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

本文系統(tǒng)設(shè)計基于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ù)器的通信交互?？傮w架構(gòu)和主要流程如圖1所示。

1.2 功能概述

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

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

2 路徑提取與存儲

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

2.1 地圖加載

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 實驗及結(jié)果分析

假設(shè)配送客戶節(jié)點數(shù)n =20，各節(jié)點需求量如表1所示，并根據(jù)客戶地址利用上述方法從Google Maps獲得各節(jié)點間的有向路徑距離矩陣如表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）；實驗條件（環(huán)境下）：CUP2.6GHz、內(nèi)存1.0GB、網(wǎng)絡(luò)帶寬512Kbps、Windows XP系統(tǒng)。

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

圖2 第1輛車路徑

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

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

圖3 第2輛車路徑

圖4 第3輛車路徑

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

5 結(jié)論

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

[1] 孫麗君,胡祥培,王征.車輛路徑規(guī)劃問題及其求解方法研究進展[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的郵政運輸調(diào)度系統(tǒng)的分析與設(shè)計[D].濟南：山東大學(xué),2010.

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

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

[6] 夏鼎.改進的蟻群算法解決車輛路徑問題及其WebGIS實現(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è)計[D].浙江工業(yè)大學(xué),2009.

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

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

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

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