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

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

關鍵詞：VRP；Dijkstra算法；地理信息系統

中圖分類號：U116.2文獻標識碼：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引言

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

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

1VRP問題數學模型

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

2VRP問題的求解算法

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

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

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

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

3GIS技術與VRP問題的結合

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

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

route.txt

起點編號，終點編號

point.txt

點編號，點類型，經度，緯度

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

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

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

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

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

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

4結論

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

參考文獻：

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

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

[3] 孫麗君，胡祥培，王征. 車輛路徑規劃問題及其求解方法研究進展[J]． 系統工程，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]. 計算機科學，2006，33(10):325-327.

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