基于GIS 的Dijkstra算法在運輸系統(tǒng)的應(yīng)用

于 斌

（武漢科技大學(xué) 城市學(xué)院，湖北 武漢 430083）

0 引言

隨著定位導(dǎo)航技術(shù)、數(shù)據(jù)通信技術(shù)、自動控制技術(shù)、圖像分析技術(shù)以及計算機網(wǎng)絡(luò)和信息處理技術(shù)的快速發(fā)展，運輸調(diào)度系統(tǒng)成為智能交通系統(tǒng)（ITS）的一個重要組成部分，常用的或者比較成熟的算法已經(jīng)開始運用到實際運輸調(diào)度系統(tǒng)中。

1 車輛路徑問題概述

研究運輸過程中車輛調(diào)度及路線安排的車輛路徑問題VRP（Vehicle Routing Problem），是目前運籌學(xué)領(lǐng)域中的一個熱點問題。VRP的一般描述是：對一系列集貨點或送貨點，組織適當(dāng)?shù)男熊嚶肪€，使車輛有序地通過它們，在一定的約束條件，如貨物需求量、發(fā)送量、交發(fā)貨時間、車輛容量限制、行駛里程限制、時間限制等情況下，達到一定的目標，如路程最短、費用最少、時間盡量少、使用車輛數(shù)盡量少等。其中，一般把最小的車輛數(shù)作為第一目標，而最低的行駛成本作為第二目標。

當(dāng)不考慮時間要求，僅根據(jù)空間位置安排線路時，稱為車輛路徑問題（VRP），考慮時間要求安排線路時稱為車輛調(diào)度問題（VSP），本文不作嚴格區(qū)分，統(tǒng)稱為 VRP?，F(xiàn)在VRP問題的研究主要集中于尋找一些高效的啟發(fā)式算法。

2 GIS在交通領(lǐng)域的應(yīng)用研究[1]

2.1 GIS和GPS

地理信息系統(tǒng)（GIS）[2-3]是一種空間性數(shù)據(jù)庫管理系統(tǒng)，除了具備一般數(shù)據(jù)管理系統(tǒng)的數(shù)據(jù)輸入、存儲、查詢和顯示輸出等基本功能外，能夠進行空間查詢和空間分析，用戶可以根據(jù)需要建立一個應(yīng)用分析模型，通過動態(tài)分析為評價、管理和決策服務(wù)。如一段公路，起迄點是它的地理特征，公路的造價、技術(shù)標準以及交通量等又具有統(tǒng)計數(shù)據(jù)特征。這些統(tǒng)計數(shù)據(jù)在紙介質(zhì)地圖上是難以描述的。

全球衛(wèi)星定位系統(tǒng)（GPS）已廣泛應(yīng)用于城市交通管理領(lǐng)域，實現(xiàn)定位、導(dǎo)航、車輛監(jiān)控以及調(diào)度管理等功能，并且與GIS技術(shù)集成，以實現(xiàn)不同的具體應(yīng)用目標。目前，有關(guān)GIS和GPS的主要研究方向有數(shù)據(jù)采集技術(shù)和數(shù)據(jù)庫維護技術(shù)。

交通決策要求GIS提供的數(shù)據(jù)范圍在不斷擴大，要求數(shù)據(jù)采集技術(shù)也不斷發(fā)展，這些技術(shù)包括 GPS、視頻技術(shù)、數(shù)碼攝像技術(shù)、高清晰衛(wèi)星圖像、高清晰度掃描技術(shù)以及實時數(shù)據(jù)處理系統(tǒng)和傳感器。這些實時數(shù)據(jù)來自氣象雷達、車輛身份證條碼、交通量計數(shù)器、路面溫度傳感器、ITS中的車輛導(dǎo)航系統(tǒng)等，所有這些技術(shù)均對GIS的設(shè)計實施產(chǎn)生影響。在進行數(shù)據(jù)庫選擇決策時，需要考慮采用大型的、一致性好的數(shù)據(jù)庫，支持動態(tài)更新和維護。

2.2 GIS解決方案——Arc GIS

GIS系統(tǒng)軟件的選擇，直接影響數(shù)據(jù)庫管理軟件的選擇，影響系統(tǒng)解決方案，也影響著系統(tǒng)建設(shè)周期和效益。Arc GIS[4]作為一個可伸縮的平臺，無論是在桌面，在服務(wù)器，在數(shù)據(jù)組織使用，為個人用戶也為群體用戶提供優(yōu)良的GIS服務(wù)。Arc GIS是基于一套由共享GIS組件組成的通用組件庫實現(xiàn)的，這些組件被稱為Arc Objects。使用Arc Objects建成的Arc GIS平臺為開發(fā)者提供了一個應(yīng)用開發(fā)的容器，包括桌面GIS（ArcGIS Desktop），嵌入式GIS（ArcGIS Engine）以及服務(wù)端GIS（ArcGIS Server）。

ArcGIS Server是一個發(fā)布企業(yè)級GIS應(yīng)用程序的綜合平臺，支持的GIS軟件可以集中管理并且支持多用戶。ArcGIS Server包含了空間數(shù)據(jù)管理技術(shù)，用于通過多種關(guān)系型數(shù)據(jù)庫來管理基于多用戶和事務(wù)的地理數(shù)據(jù)庫。ArcGIS Server提供了用于.NET和Java的應(yīng)用程序開發(fā)框架（ADF），可以滿足各種客戶端的各種需求。ADF可以幫助用戶創(chuàng)建和配置.NET或者Java桌面和網(wǎng)絡(luò)應(yīng)用，它們在GIS Server中運行時需要調(diào)用ArcObjects。

面向Java的ArcGIS Server ADF可以在微軟的Windows Server和各種UNIX平臺上運行，且支持很多網(wǎng)絡(luò)服務(wù)器。另外，ArcGIS Server可以在單CPU或者多個CPU組成的分布式服務(wù)器系統(tǒng)上運行。

3 Dijkstra算法在運輸調(diào)度系統(tǒng)中的應(yīng)用

3.1 最短路徑問題和Dijkstra算法

交通網(wǎng)絡(luò)可以用帶權(quán)圖表示，帶權(quán)圖的最短路徑問題即求兩個頂點間長度最短的路徑。其中，路徑長度不是指路徑上邊數(shù)的總和，而是指路徑上各邊的權(quán)值總和。

Dijkstra算法是典型最短距離算法，用于計算一個節(jié)點到其他所有節(jié)點的最短路徑。Dijkstra算法的基本原理是：每次新擴展一個距離最短的點，更新與其相鄰的點的距離。當(dāng)所有邊權(quán)都為正時，由于不會存在一個距離更短的沒擴展過的點，所以這個點的距離永遠不會再被改變，因而保證了算法的正確性。因此，用 Dijkstra求最短距離的圖不能有負權(quán)邊。

Dijkstra算法的主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止，結(jié)果是總能得出最短路徑的最優(yōu)解。

3.2 Dijkstra算法在運輸調(diào)度系統(tǒng)中的應(yīng)用

運輸調(diào)度系統(tǒng)是集 GPS、GIS以及無線通信技術(shù)于一體的軟、硬件綜合系統(tǒng)。其主要由三部分組成：車載終端、無線數(shù)據(jù)鏈路和監(jiān)控中心軟件系統(tǒng)，可對移動車輛進行統(tǒng)一集中管理和實時監(jiān)控調(diào)度指揮。安裝在車輛上的GPS定位儀可以實時確定車輛的位置信息，通過車載無線數(shù)據(jù)通信系統(tǒng)，將信息傳送到指揮監(jiān)控中心，監(jiān)控中心把車輛的位置顯示在監(jiān)控中心的電子地圖上。監(jiān)控中心系統(tǒng)軟件利用獲取的實時車輛信息和GIS交通道路信息，在交通網(wǎng)絡(luò)中根據(jù)實時道路交通狀況、交通流量、交通費用或途中所需的時間信息等，比照原有統(tǒng)計數(shù)據(jù)計算出各條交通道路路徑的權(quán)值，使用Dijkstra算法，計算出車輛到達目的地的最短路徑。車載無線數(shù)據(jù)通信系統(tǒng)還可將指揮中心的命令傳送到移動車輛上，從而實現(xiàn)對運輸車輛的管理控制和調(diào)度。

4 智能運輸調(diào)度系統(tǒng)開發(fā)與應(yīng)用

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

基于上述ArcGIS軟件和Dijkstra算法，用Java開發(fā)應(yīng)用于大型物流企業(yè)的運輸調(diào)度系統(tǒng)，完成 Unix系統(tǒng)下基于 Oracle的應(yīng)用軟件開發(fā)，全面支持物流企業(yè)多種運輸模式的運行要求[5]。

系統(tǒng)分為硬件設(shè)備和軟件系統(tǒng)兩大部分。硬件設(shè)備包括車載信息終端、服務(wù)器、終端計算機、互聯(lián)網(wǎng)、無線通信網(wǎng)等，如圖1所示。軟件系統(tǒng)分為業(yè)務(wù)管理、客戶服務(wù)、車輛監(jiān)控、車輛調(diào)度四個子系統(tǒng)。為了提高業(yè)務(wù)數(shù)據(jù)安全性，業(yè)務(wù)管理子系統(tǒng)和客戶服務(wù)子系統(tǒng)采用B/S架構(gòu)，將數(shù)據(jù)庫服務(wù)器放于中心內(nèi)網(wǎng)，將應(yīng)用服務(wù)器放于中心外網(wǎng)，嚴格區(qū)分用戶的操作權(quán)限及范圍。此外，系統(tǒng)還采用在線用戶監(jiān)控、用戶重要操作記錄、用戶同時登錄次數(shù)限制、用戶 Session定時失效等措施進一步加強系統(tǒng)安全性管理。

圖1 智能運輸系統(tǒng)硬件設(shè)備結(jié)構(gòu)

4.2 系統(tǒng)數(shù)據(jù)流程

系統(tǒng)采用標準的三層結(jié)構(gòu)，即頁面顯示、業(yè)務(wù)邏輯處理和數(shù)據(jù)庫操作，數(shù)據(jù)流程如下頁圖2所示。系統(tǒng)前端頁面請求使用統(tǒng)一的前端控制器進行轉(zhuǎn)發(fā)，便于理清系統(tǒng)工作流程、權(quán)限管理和編碼轉(zhuǎn)換等。針對每一個業(yè)務(wù)流程中的對象建立模塊，對每一個操作建立類，通過數(shù)據(jù)訪問對象（DAO）獲得數(shù)據(jù)庫支持。在整個應(yīng)用程序中DAO可以將底層數(shù)據(jù)訪問邏輯與業(yè)務(wù)邏輯分離開來，在數(shù)據(jù)庫和業(yè)務(wù)邏輯中間設(shè)置中間接口（Bean），便于升級為EJB。

圖2 智能運輸系統(tǒng)數(shù)據(jù)流程

4.3 系統(tǒng)布署和應(yīng)用

系統(tǒng)有多種監(jiān)控方式，已應(yīng)用于某大型物流企業(yè)，客戶可以方便地通過車載終端或者手機訪問。系統(tǒng)已經(jīng)覆蓋中國大部分地區(qū)，目前已經(jīng)開通多個區(qū)域，通過一年多的實際運行，系統(tǒng)穩(wěn)定性、安全性等滿足設(shè)計要求。系統(tǒng)的應(yīng)用對促進物流企業(yè)的信息化、規(guī)范化管理，降低成本，提高效益起到了重要作用。

5 結(jié)語

運輸調(diào)度系統(tǒng)建立起了車輛與系統(tǒng)用戶之間迅速、準確、有效的信息傳遞通道。進一步的研究工作是在豐富數(shù)據(jù)和積累經(jīng)驗的基礎(chǔ)上制定更合理的交通道路路徑權(quán)值，和加強基于ArcGIS的開發(fā)應(yīng)用。

[1]許煥明,王貴恩,孫永林.內(nèi)河船舶監(jiān)督預(yù)警通信管理系統(tǒng)運行模式的研究[J].通信技術(shù),2008,41(09):227-229.

[2]吳立新，史文中.地理信息系統(tǒng)原理與算法[M].北京：科學(xué)出版社，2003.

[3]張超.地理信息系統(tǒng)應(yīng)用教程[M].北京：科學(xué)出版社，2007.

[4]吳秀芹，張洪巖,李瑞政,等.ArcGIS 9地理信息系統(tǒng)應(yīng)用與實踐(上下冊)[M].北京：清華大學(xué)出版社，2007.

[5]Horst R, Pardalos P M, Thoai N V.全局優(yōu)化引論[M].北京：清華大學(xué)出版社，2003.