基于GIS 的Dijkstra算法在運輸系統的應用

于 斌

（武漢科技大學 城市學院，湖北 武漢 430083）

0 引言

隨著定位導航技術、數據通信技術、自動控制技術、圖像分析技術以及計算機網絡和信息處理技術的快速發展，運輸調度系統成為智能交通系統（ITS）的一個重要組成部分，常用的或者比較成熟的算法已經開始運用到實際運輸調度系統中。

1 車輛路徑問題概述

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

當不考慮時間要求，僅根據空間位置安排線路時，稱為車輛路徑問題（VRP），考慮時間要求安排線路時稱為車輛調度問題（VSP），本文不作嚴格區分，統稱為 VRP?，F在VRP問題的研究主要集中于尋找一些高效的啟發式算法。

2 GIS在交通領域的應用研究[1]

2.1 GIS和GPS

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

全球衛星定位系統（GPS）已廣泛應用于城市交通管理領域，實現定位、導航、車輛監控以及調度管理等功能，并且與GIS技術集成，以實現不同的具體應用目標。目前，有關GIS和GPS的主要研究方向有數據采集技術和數據庫維護技術。

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

2.2 GIS解決方案——Arc GIS

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

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

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

3 Dijkstra算法在運輸調度系統中的應用

3.1 最短路徑問題和Dijkstra算法

交通網絡可以用帶權圖表示，帶權圖的最短路徑問題即求兩個頂點間長度最短的路徑。其中，路徑長度不是指路徑上邊數的總和，而是指路徑上各邊的權值總和。

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

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

3.2 Dijkstra算法在運輸調度系統中的應用

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

4 智能運輸調度系統開發與應用

4.1 系統結構

基于上述ArcGIS軟件和Dijkstra算法，用Java開發應用于大型物流企業的運輸調度系統，完成 Unix系統下基于 Oracle的應用軟件開發，全面支持物流企業多種運輸模式的運行要求[5]。

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

圖1 智能運輸系統硬件設備結構

4.2 系統數據流程

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

圖2 智能運輸系統數據流程

4.3 系統布署和應用

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

5 結語

運輸調度系統建立起了車輛與系統用戶之間迅速、準確、有效的信息傳遞通道。進一步的研究工作是在豐富數據和積累經驗的基礎上制定更合理的交通道路路徑權值，和加強基于ArcGIS的開發應用。

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

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

[3]張超.地理信息系統應用教程[M].北京：科學出版社，2007.

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

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