基于Ｍａｐ Ｉｎｆｏ電子地圖的配送車輛線路優(yōu)化問題研究

摘要：GIS技術(shù)與VRP問題的結(jié)合，不僅提供了一種新的查詢選擇方法，同時還能提供一種直觀的解決方案。文章針對Map Info電子地圖的特點，給出了一種從電子地圖中提取客戶與道路信息應(yīng)用到解決實際的配送車輛線路優(yōu)化問題，并將求解后的線路直觀地顯示到電子地圖中的方法。在實際應(yīng)用中表明該方法是高效直觀的。

關(guān)鍵詞：VRP；Dijkstra算法；地理信息系統(tǒng)

中圖分類號：U116.2文獻(xiàn)標(biāo)識碼：A文章編號：1002-3100(2008)12-0023-03

Abstract: The combination of GIS and VRP is not only a new method to inquiry， but also offers an intuitive solution. Based on the characteristic of Map Info electro-map， a method to extract customers and routes information from the map to be used by the Vehicle Routing Problem and draw the feasible path on the map is given. It's testified that the method is efficient and intuitive in practice.

Key words: Vehicle Routing Problem; Dijkstra algorithm; GIS

0引言

配送作為直接與消費者相聯(lián)系的環(huán)節(jié)，在整個物流系統(tǒng)中起著舉足輕重的作用。相關(guān)資料表明，在生產(chǎn)企業(yè)原材料物流中運輸配送成本占整個物流成本的58%，在生產(chǎn)企業(yè)成品物流中達(dá)到73%，而在商業(yè)企業(yè)中該比例為52%[1]，因此，有效降低配送成本對降低物流系統(tǒng)運行成本具有非常重要的意義。配送車輛線路優(yōu)化問題（VRP， Vehicle Routing Problem）最早由Danzig和Ramser提出[2]，就是研究如何制定合理的配送線路，從而以最少的物流成本將貨物快速而經(jīng)濟地送達(dá)客戶手中。近年來，伴隨著經(jīng)濟全球化與物流業(yè)的迅猛發(fā)展，該問題在實踐中的應(yīng)用逐漸受到重視。

地理信息系統(tǒng)GIS是用于采集、存儲、管理、處理、檢索、分析和表達(dá)地理空間數(shù)據(jù)的計算機系統(tǒng)，是一種分析和處理海量地理數(shù)據(jù)的通用技術(shù)。利用GIS技術(shù)，可以對空間數(shù)據(jù)進(jìn)行直觀顯示和分析。基于GIS的配送車輛線路優(yōu)化系統(tǒng)是GIS應(yīng)用的一個新領(lǐng)域，也是配送車輛線路優(yōu)化問題向信息化發(fā)展的一個趨勢。集成后的配送車輛線路優(yōu)化系統(tǒng)不僅可以為企業(yè)提供一種新的查詢選擇方法，同時還能提供一種直觀的解決方案，指導(dǎo)企業(yè)選擇合理的線路。本文針對Map Info電子地圖的特點，給出了一種從電子地圖中提取客戶與道路信息應(yīng)用到解決實際的配送車輛線路優(yōu)化問題，并將求解后的線路直觀地顯示到電子地圖中的方法。

1VRP問題數(shù)學(xué)模型

約束（1）表示客戶點i在某輛車的服務(wù)線路上；約束（2），（3）表示客戶點i，j在車輛k的服務(wù)線路上，那么將由車輛k服務(wù)；約束（4）表示客戶點i僅被服務(wù)一次；約束（5）表示從配送中心出發(fā)的線路有K條；約束（6）保證了不存在未從配送中心出發(fā)的子環(huán)路；約束（7）保證每條配送線路的送貨量不超過車載容量。

2VRP問題的求解算法

國內(nèi)外有關(guān)VRP問題的求解方法，可以分為精確算法、啟發(fā)式算法和亞啟發(fā)式算法三類[3]。

（1）精確算法：主要有分支定界法、割平面法、網(wǎng)絡(luò)流算法、動態(tài)規(guī)劃法、Ｋ－樹法以及拉格朗日松弛算法，但由于VRP問題是公認(rèn)的計算機難解問題[4]，隨著問題規(guī)模的不斷擴大，求解難度大大增加，因此，在實際中的應(yīng)用不大。

（2）啟發(fā)式算法： 求解VRP問題常采用啟發(fā)式算法，保證以較小的時間與空間代價獲得滿意的可行解。啟發(fā)式算法可以分為構(gòu)造啟發(fā)式算法和改進(jìn)啟發(fā)式算法兩類，比較典型的有C-W節(jié)約算法、最鄰近法、最近插入法、掃描算法、兩階段算法、k-opt算法、λ-interchange算法等。

（3）亞啟發(fā)式算法：為了避免啟發(fā)式算法易陷入局部最優(yōu)解的缺點，亞啟發(fā)式算法在搜索過程中允許解的劣化甚至是不可行中間狀態(tài)解的存在。目前，求解VRP問題的亞啟發(fā)式算法有：模擬退火算法、禁忌搜索算法、遺傳算法、蟻群算法與神經(jīng)網(wǎng)絡(luò)算法[5]。

3GIS技術(shù)與VRP問題的結(jié)合

理論上的VRP問題通常都是給定節(jié)點之間的距離，實際應(yīng)用中，有時為了簡便起見常采用節(jié)點間的直線距離，因此，對指導(dǎo)實踐還有一定的差距。將GIS技術(shù)與VRP問題進(jìn)行結(jié)合后，就可以利用電子地圖提供的信息，采用Dijstra算法計算任意兩個節(jié)點間的最短距離作為實際線路距離，然后用于VRP問題的優(yōu)化求解，再將模型得到的優(yōu)化結(jié)果返回地理信息系統(tǒng)，直觀的呈現(xiàn)出來。具體步驟如下：

（1）數(shù)據(jù)的獲取與處理。根據(jù)Map Info電子地圖提供的道路圖層和道路交匯點圖層中提取點線信息，保存到文本文件route.txt中，從道路交匯點圖層和客戶點圖層中提取點信息，保存到文本文件point.txt中。文件的格式如下：

route.txt

起點編號，終點編號

point.txt

點編號，點類型，經(jīng)度，緯度

在實際處理時，可以根據(jù)客戶點和道路交叉點將道路分段，每段路都看作直線；而對于弧度特別大的路段，可以通過在路段拐點處添加虛擬點的方法來減小弧度數(shù)，從而看作直線處理；然后將分段后的道路信息存儲到route.txt文件；

由于客戶點都會和某段道路的端點相重合，所以把道路交匯點、配送點和虛擬點信息保存在同一個文件point.txt中，這樣便于創(chuàng)建鄰接矩陣，實現(xiàn)客戶點間最短路徑的搜索，其中點類型將區(qū)分出客戶點與其他的點類型。

（2）求解客戶點間最短路徑。由于route.txt實際上保存的是一個相鄰點矩陣，可以很輕易的轉(zhuǎn)化成一個不含權(quán)重的鄰接矩陣；根據(jù)鄰接矩陣提供的信息，從point.txt文件中獲取相鄰點的經(jīng)緯度，從而算出各個相鄰點之間的球面距離，作為鄰接矩陣的權(quán)重，這樣就獲得了Dijkstra算法所需要的鄰接矩陣，然后可以根據(jù)Dijkstra算法求解客戶點間最短路徑。

（3）VRP問題的求解。根據(jù)生成的客戶點鄰接矩陣，并讀入各客戶點的需求量數(shù)據(jù)，根據(jù)建立的VRP問題數(shù)學(xué)模型和選擇的求解算法，求解出配送車輛線路。

（4）線路的顯示。運算后生成的配送線路，保存到數(shù)據(jù)庫文件中，利用Map Info從數(shù)據(jù)庫中讀取配送線路，生成新的線路圖層，添加到地圖上，就可以直觀的看到生成的配送線路。

對于實際的配送車輛線路優(yōu)化問題，由于規(guī)模過大，可以采用“先聚類后排程”的兩階段算法，只對聚在一起的客戶點求解最短路徑，這樣可以極大降低求解所需要的時間。

4結(jié)論

本文針對Map Info電子地圖的特點，給出了一種從電子地圖中提取客戶與道路信息應(yīng)用到解決實際的配送車輛線路優(yōu)化問題，并將求解后的線路直觀地顯示到電子地圖中的方法。在實際應(yīng)用中表明，對于一個中等大小城市的日用品配送線路優(yōu)化問題，VRP問題使用“先聚類后排程”的兩階段算法，整個過程大約耗時1個小時的時間，求解非常高效與直觀。

參考文獻(xiàn)：

[1] 張勇. 物流配送路徑優(yōu)化算法研究[D]. 北京：北京交通大學(xué)，2005．

[2] Dantzig G. B， Ramser J. H． The Truck Dispatching Problem[J]. Management Science， 1959，6(1):80-91.

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

[4]Lenstra， J. K.， and Rinnooy Kan， A. H. G． Complexity of vehicle routing and scheduling problems[J]. Networks， 1981，11:221

-227.

[5]Michel G， Gilbert L， Potvin J.Y. Meta-heuristics for the vehicle routing problem[C]//Les Cahiers du GERAD G-89-04， Ecole des Hautes Etudes Commerciales de Montreal， 1999.

[6] 李艷，劉志鏡. GIS中的最短路徑算法[J]. 計算機科學(xué)，2006，33(10):325-327.

[7] 胡志杰. 基于GIS的配送路徑規(guī)劃方法研究[D]. 武漢：武漢理工大學(xué)，2005．