于 斌
(武漢科技大學(xué) 城市學(xué)院,湖北 武漢 430083)
隨著定位導(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)中。
研究運輸過程中車輛調(diào)度及路線安排的車輛路徑問題VRP(Vehicle Routing Problem),是目前運籌學(xué)領(lǐng)域中的一個熱點問題。VRP的一般描述是:對一系列集貨點或送貨點,組織適當(dāng)?shù)男熊嚶肪€,使車輛有序地通過它們,在一定的約束條件,如貨物需求量、發(fā)送量、交發(fā)貨時間、車輛容量限制、行駛里程限制、時間限制等情況下,達(dá)到一定的目標(biāo),如路程最短、費用最少、時間盡量少、使用車輛數(shù)盡量少等。其中,一般把最小的車輛數(shù)作為第一目標(biāo),而最低的行駛成本作為第二目標(biāo)。
當(dāng)不考慮時間要求,僅根據(jù)空間位置安排線路時,稱為車輛路徑問題(VRP),考慮時間要求安排線路時稱為車輛調(diào)度問題(VSP),本文不作嚴(yán)格區(qū)分,統(tǒng)稱為 VRP。現(xiàn)在VRP問題的研究主要集中于尋找一些高效的啟發(fā)式算法。
地理信息系統(tǒng)(GIS)[2-3]是一種空間性數(shù)據(jù)庫管理系統(tǒng),除了具備一般數(shù)據(jù)管理系統(tǒng)的數(shù)據(jù)輸入、存儲、查詢和顯示輸出等基本功能外,能夠進(jìn)行空間查詢和空間分析,用戶可以根據(jù)需要建立一個應(yīng)用分析模型,通過動態(tài)分析為評價、管理和決策服務(wù)。如一段公路,起迄點是它的地理特征,公路的造價、技術(shù)標(biāo)準(zhǔn)以及交通量等又具有統(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)用目標(biāo)。目前,有關(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ù)來自氣象雷達(dá)、車輛身份證條碼、交通量計數(shù)器、路面溫度傳感器、ITS中的車輛導(dǎo)航系統(tǒng)等,所有這些技術(shù)均對GIS的設(shè)計實施產(chǎn)生影響。在進(jìn)行數(shù)據(jù)庫選擇決策時,需要考慮采用大型的、一致性好的數(shù)據(jù)庫,支持動態(tài)更新和維護。
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)上運行。
交通網(wǎng)絡(luò)可以用帶權(quán)圖表示,帶權(quán)圖的最短路徑問題即求兩個頂點間長度最短的路徑。其中,路徑長度不是指路徑上邊數(shù)的總和,而是指路徑上各邊的權(quán)值總和。
Dijkstra算法是典型最短距離算法,用于計算一個節(jié)點到其他所有節(jié)點的最短路徑。Dijkstra算法的基本原理是:每次新擴展一個距離最短的點,更新與其相鄰的點的距離。當(dāng)所有邊權(quán)都為正時,由于不會存在一個距離更短的沒擴展過的點,所以這個點的距離永遠(yuǎn)不會再被改變,因而保證了算法的正確性。因此,用 Dijkstra求最短距離的圖不能有負(fù)權(quán)邊。
Dijkstra算法的主要特點是以起始點為中心向外層層擴展,直到擴展到終點為止,結(jié)果是總能得出最短路徑的最優(yōu)解。
運輸調(diào)度系統(tǒng)是集 GPS、GIS以及無線通信技術(shù)于一體的軟、硬件綜合系統(tǒng)。其主要由三部分組成:車載終端、無線數(shù)據(jù)鏈路和監(jiān)控中心軟件系統(tǒng),可對移動車輛進(jìn)行統(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算法,計算出車輛到達(dá)目的地的最短路徑。車載無線數(shù)據(jù)通信系統(tǒng)還可將指揮中心的命令傳送到移動車輛上,從而實現(xiàn)對運輸車輛的管理控制和調(diào)度。
基于上述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),嚴(yán)格區(qū)分用戶的操作權(quán)限及范圍。此外,系統(tǒng)還采用在線用戶監(jiān)控、用戶重要操作記錄、用戶同時登錄次數(shù)限制、用戶 Session定時失效等措施進(jìn)一步加強系統(tǒng)安全性管理。
圖1 智能運輸系統(tǒng)硬件設(shè)備結(jié)構(gòu)
系統(tǒng)采用標(biāo)準(zhǔn)的三層結(jié)構(gòu),即頁面顯示、業(yè)務(wù)邏輯處理和數(shù)據(jù)庫操作,數(shù)據(jù)流程如下頁圖2所示。系統(tǒng)前端頁面請求使用統(tǒng)一的前端控制器進(jìn)行轉(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ù)流程
系統(tǒng)有多種監(jiān)控方式,已應(yīng)用于某大型物流企業(yè),客戶可以方便地通過車載終端或者手機訪問。系統(tǒng)已經(jīng)覆蓋中國大部分地區(qū),目前已經(jīng)開通多個區(qū)域,通過一年多的實際運行,系統(tǒng)穩(wěn)定性、安全性等滿足設(shè)計要求。系統(tǒng)的應(yīng)用對促進(jìn)物流企業(yè)的信息化、規(guī)范化管理,降低成本,提高效益起到了重要作用。
運輸調(diào)度系統(tǒng)建立起了車輛與系統(tǒng)用戶之間迅速、準(zhǔn)確、有效的信息傳遞通道。進(jìn)一步的研究工作是在豐富數(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.