莫以為，何新彪

MO Yi-wei,HE Xin-biao

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

0 引言

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

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

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

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

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

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

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

1.2 功能概述

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

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

2 路徑提取與存儲(chǔ)

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

2.1 地圖加載

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

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

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

主要完成路徑導(dǎo)航服務(wù)請(qǐng)求對(duì)象google.maps.DirectionsService()、路徑導(dǎo)航顯示對(duì)象google.maps.DirectionsRenderer()、請(qǐng)求對(duì)象request參數(shù)的設(shè)定。request參數(shù)包括起點(diǎn)地址、終點(diǎn)地址、是否提供備用路線、是否避開(kāi)高速路、是否避開(kāi)收費(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ù)提取與存儲(chǔ)

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

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

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

本文所研究的是配送中心給若干客戶配送的車輛調(diào)度問(wèn)題，假設(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；為方便起見(jiàn)假設(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，并保持不變，把問(wèn)題簡(jiǎn)化為m個(gè)路徑優(yōu)化問(wèn)題；然后在約束條件式(2)和式(3)下通過(guò)路徑的選擇對(duì)目標(biāo)函數(shù)1-1進(jìn)行優(yōu)化，確定優(yōu)化調(diào)度方案。

通過(guò)分析各種路徑規(guī)劃的智能算法優(yōu)劣性，采用SAGA進(jìn)行求解。該算法因遺傳算法GA的強(qiáng)大全局搜索能力可快速地搜索出全局較優(yōu)解，同時(shí)在GA主循環(huán)中插入模擬退化算法SA，利用其良好的局部搜索能力以彌補(bǔ)GA的局部搜索能力較差不足，尋求全局最優(yōu)解。具體地說(shuō)，采用SAGA算法對(duì)m輛車的路徑（包含起點(diǎn)配送中心）的構(gòu)成長(zhǎng)度為m+n+1的方案編碼進(jìn)行優(yōu)化，這是為了便于交叉、變異等算子的操作，該編碼方案直觀，不需解碼，兩個(gè)數(shù)字0之間的路徑即為一輛車的行駛路徑。例如，m=3、n=8的路徑編碼047803602510表示3輛車對(duì)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è)體表示長(zhǎng)度為m+n+1的路徑編碼，且無(wú)論隨機(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是否超過(guò)總繁殖代數(shù)或個(gè)體Smin連續(xù)最佳保持了X0代：若是則退出，并輸出Jmin、Smin；否則轉(zhuǎn)到3）;

（3）重復(fù)(1)～(2)步驟L次（L為馬爾科夫鏈長(zhǎng)度，且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對(duì)父代1和父代2進(jìn)行交叉產(chǎn)生一個(gè)子代個(gè)體[11]，若交叉不成功，各以一半的概率選擇其中一父代作為子代個(gè)體；以概率pm對(duì)該子代個(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代開(kāi)始找到總噸公里數(shù)最小的路徑（05820671516190134111221010143171890），且該路徑連續(xù)保持最小至346代，用時(shí)17秒，其總噸公里數(shù)為301.6噸公里，總路徑長(zhǎng)度為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í)考慮到配送中心客戶相對(duì)較穩(wěn)定的特點(diǎn)，文中提出獲取路徑信息方法是可行的。另一方面，增加X(jué)和X0的值可搜索出更優(yōu)的個(gè)體，因此通過(guò)合理設(shè)置算法參數(shù)可改善種群逐代收斂性能，在不超過(guò)總繁殖代數(shù)X內(nèi)搜索出了連續(xù)最佳保持X0代的優(yōu)化個(gè)體。經(jīng)過(guò)實(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]，對(duì)于客戶節(jié)點(diǎn)數(shù)n為100以下中小規(guī)模物流配送問(wèn)題，本系統(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)確性。本文通過(guò)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é)合，通過(guò)SAGA的模擬退火算法和遺傳算法的各自優(yōu)勢(shì)能較好地解決物流配送VRP問(wèn)題。采用Google地圖道路網(wǎng)數(shù)據(jù)取代兩節(jié)點(diǎn)間直線距離數(shù)據(jù)，并以車輛運(yùn)輸總噸公里數(shù)代替運(yùn)輸總路徑長(zhǎng)度作為優(yōu)化目標(biāo)函數(shù)，更符合真實(shí)情況與實(shí)際需要。與此同時(shí)，系統(tǒng)的開(kāi)發(fā)與維護(hù)成本低，具有較好的實(shí)用價(jià)值，還可將本方案延伸至VRP的變種問(wèn)題，并結(jié)合車輛監(jiān)控系統(tǒng)等可構(gòu)成更加完善的配送管理系統(tǒng)。因此，本文給出的車輛調(diào)度方案對(duì)眾多中小物流企業(yè)實(shí)際解決VRP具有一定的參考價(jià)值。

[1] 孫麗君,胡祥培,王征.車輛路徑規(guī)劃問(wèn)題及其求解方法研究進(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)的蟻群算法解決車輛路徑問(wè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問(wèn)題的改進(jìn)模擬退火遺傳算法[J].計(jì)算機(jī)工程與應(yīng)用,2010,46(5)：44-48.

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

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

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