張?jiān)骑w 楊亞茹 鄭虎龍 段傳緒 王廉拓
摘要:利用車輛導(dǎo)航技術(shù)的反饋信息,通過(guò)A*算法對(duì)靜態(tài)路網(wǎng)的最優(yōu)路徑做出動(dòng)態(tài)選擇?;陟o態(tài)路網(wǎng)信息的最優(yōu)路徑求解是現(xiàn)時(shí)車輛GPS導(dǎo)航領(lǐng)域所面臨的關(guān)鍵問(wèn)題?,F(xiàn)今流行的Dijkstra算法、A*算法等,都是基于完全靜態(tài)、確定的信息數(shù)據(jù)庫(kù)下,求解得出的最短路徑。本文通過(guò)A*算法充分利用靜態(tài)路網(wǎng)信息,借助車輛導(dǎo)航系統(tǒng)加以動(dòng)態(tài)路網(wǎng)中的適應(yīng)條件,以及實(shí)時(shí)更新的交通數(shù)據(jù),得出計(jì)算結(jié)果精確,時(shí)間復(fù)雜度較低,且符合實(shí)際情況的最佳路徑。
關(guān)鍵詞:交通調(diào)度? 動(dòng)態(tài)路網(wǎng)? 最佳路徑? A*算法? GPS
引言:
目前,隨著社會(huì)經(jīng)濟(jì)的發(fā)展、城市化進(jìn)程的加快和機(jī)動(dòng)車保有量的快速增長(zhǎng),尤其私家小汽車的快速發(fā)展,城市交通越發(fā)擁擠。由于土地資源不足,建造各種公路等物理設(shè)施的能力是有限的, 所以單純地依靠修建更多的道路、擴(kuò)大路網(wǎng)規(guī)模等這樣的措施僅僅能解一時(shí)之需, 并不能從根本上解決日益增長(zhǎng)的交通需求?;谶@種需要,提出了以車載GPS(Global Positioning System)為核心的路徑分析系統(tǒng)。該技術(shù)是以GPS技術(shù)為核心, 綜合利用廣播技術(shù)、光電傳感器、計(jì)算機(jī)網(wǎng)絡(luò)、自動(dòng)控制和人工智能等技術(shù)的一種新型車輛導(dǎo)航技術(shù)。
現(xiàn)階段,車載GPS進(jìn)入規(guī)?;l(fā)展階段。
1基于靜態(tài)路網(wǎng)的A*算法原理
一條路徑的確定取決于許多因素,如距離、行程時(shí)間、路網(wǎng)彎數(shù)、路況復(fù)雜度、轉(zhuǎn)向燈個(gè)數(shù)、交通信號(hào)燈的數(shù)目和動(dòng)態(tài)交通信息等。選擇最短路徑、最佳路徑、最低耗費(fèi)等問(wèn)題,都離不開最短路徑搜索并以其作為選擇依據(jù)。路徑選擇標(biāo)準(zhǔn)可由程序設(shè)計(jì)決定或通過(guò)用戶界面修改。最短路徑問(wèn)題的解決方法很多,包括啟發(fā)式搜索A*算法、動(dòng)態(tài)規(guī)劃方法、神經(jīng)網(wǎng)絡(luò)、Dijkstra 算法等,其中以迪杰斯特拉(Dijkstra)算法在實(shí)際應(yīng)用中較為廣泛。由于Dijkstra算法的搜索過(guò)程屬于遍歷計(jì)算,所以出現(xiàn)大量的搜索節(jié)點(diǎn)。其中,由于所引入的動(dòng)態(tài)算法,是要求處理大量的靜態(tài)數(shù)據(jù)的同時(shí),還需要實(shí)時(shí)監(jiān)測(cè)接受的動(dòng)態(tài)數(shù)據(jù),并計(jì)算當(dāng)前對(duì)于最佳路徑的影響的一些數(shù)據(jù)。因此,處理量就變得相當(dāng)大,一般來(lái)說(shuō),硬件不能支持。A*算法是比較流行的啟發(fā)式搜索算法之一,被廣泛應(yīng)用于路徑的最優(yōu)解。A*算法對(duì)比其他算法,不同之處在于A*算法引入了啟發(fā)式函數(shù)。啟發(fā)式估價(jià)函數(shù)估價(jià)每一生成節(jié)點(diǎn)以確定此節(jié)點(diǎn)的優(yōu)劣性。通過(guò)這種方式,啟發(fā)式函數(shù)決定在諸多路徑中首先遍歷那條路徑以便搜索過(guò)程更為有效,因?yàn)樗惴ㄊ紫人阉髯顑?yōu)希望的節(jié)點(diǎn)。
2基于A*算法的最佳路徑求解
現(xiàn)實(shí)生活當(dāng)中,交通信息屬于動(dòng)態(tài)信息,即每一段路都有其自己的屬性。如果單純地從距離和時(shí)間出發(fā),所得出的最短路徑與實(shí)際駕駛者所希望的并不能完全符合。譬如,得出的最短路徑上,有其中路段屬于交通擁堵嚴(yán)重的,及其路段的效率就相對(duì)低下。相對(duì)駕駛者來(lái)說(shuō),意味著比其他路徑所使用的路徑花費(fèi)更多時(shí)間。又或者即使路徑上沒(méi)有交通意外,堵塞等情況,但是路徑上出現(xiàn)較多的收費(fèi)設(shè)置,同樣對(duì)于駕駛者來(lái)說(shuō)是不利的。因?yàn)檫@意味著花費(fèi)更多的費(fèi)用。
2.1GPS/DR(航位推算,Dead-Reckoning)組合定位的反饋信息
DR的基本原理是利用方向傳感器和速度傳感器來(lái)推算車輛的瞬時(shí)位置,可以實(shí)現(xiàn)連續(xù)自主式定位。但由于其推算過(guò)程是一個(gè)累加過(guò)程,方向傳感器的誤差隨時(shí)間的延長(zhǎng)而積累,另外,推算只能確定相對(duì)位置和航向。因此,將航位推算與GPS 組合起來(lái),兩者取長(zhǎng)補(bǔ)短,可以彌補(bǔ)各自的缺點(diǎn), 確保系統(tǒng)能在任何時(shí)候都能為運(yùn)動(dòng)車輛提供較為準(zhǔn)確的導(dǎo)航信息。一方面可以利用GPS精確的定位結(jié)果輔助DR 的初始化并且可以定期地用它對(duì)DR 的定位誤差進(jìn)行在線校正。另一方面,在GPS無(wú)法定位時(shí)系統(tǒng)又可以自動(dòng)地切換到DR 導(dǎo)航方式,直至GPS 恢復(fù)正常接收后, 系統(tǒng)再回到GPS 與DR 的組合導(dǎo)航方式。從而,即使在GPS失效、單獨(dú)使用DR推算定位時(shí)也能長(zhǎng)時(shí)間保持較高的定位精度。
通過(guò)GPS反饋的定位信號(hào)進(jìn)行運(yùn)動(dòng)車輛的檢測(cè)和分割,預(yù)測(cè)其在相關(guān)路徑的運(yùn)動(dòng)軌跡,從而根據(jù)交通流量綜合其他情況進(jìn)行調(diào)度,可以把發(fā)生沖突的交通流從時(shí)間和空間上進(jìn)行分離,穩(wěn)定平衡交通流的密度。
2.2廣播和交通部門信息的雙向調(diào)控
在通信網(wǎng)絡(luò)的支持下,參考廣播電臺(tái)的實(shí)時(shí)路面路況信息,即時(shí)接受交通部門發(fā)布的突發(fā)事故,并通過(guò)GSM通信網(wǎng)與移動(dòng)中的車輛進(jìn)行通話、短信息傳輸和數(shù)據(jù)傳輸,完成車輛定位、調(diào)度、監(jiān)控、報(bào)警等功能,且在電子地圖上顯示車輛的位置,做出應(yīng)急路徑選擇,間接地約束最優(yōu)動(dòng)態(tài)路徑,避免大面積的交通癱瘓,保證動(dòng)態(tài)路網(wǎng)運(yùn)動(dòng)車輛行駛路徑的準(zhǔn)確性。
其中,接受短信息可用GSM用戶終端(如車載臺(tái)、手機(jī))或用可接收短信息功能的固定用戶設(shè)備,也可用ISDN方式直接連接到移動(dòng)通信局的短消息服務(wù)中心,并聯(lián)通車輛導(dǎo)航管理系統(tǒng),這樣接收短信息更迅捷,容量更大。
結(jié)論
本文討論分析了基于車輛監(jiān)控導(dǎo)航系統(tǒng)的A*算法最佳路徑,并通過(guò)相關(guān)的約束條件進(jìn)行優(yōu)化。針對(duì)城鄉(xiāng)路網(wǎng)的特點(diǎn),對(duì)最短路徑分析的各項(xiàng)關(guān)鍵技術(shù)進(jìn)行了研究,編寫了相關(guān)路徑選擇程序進(jìn)行了模擬,提出了一種實(shí)用的最佳路徑分析解決方案,在此基礎(chǔ)上實(shí)施了最佳路徑分析方法及技術(shù);城市交通設(shè)施和規(guī)則日益復(fù)雜,需要進(jìn)一步改進(jìn)數(shù)據(jù)模型,較完整地表達(dá)和建立了路網(wǎng)的拓?fù)潢P(guān)系。本文的算法能較準(zhǔn)確、快速地檢測(cè)和提取出運(yùn)動(dòng)目標(biāo),為交通調(diào)度提供了保障,有一定的實(shí)用價(jià)值。
參考文獻(xiàn)
[1] 楊利強(qiáng),張寧,陶志祥. 3G移動(dòng)通信技術(shù)在城市交通信息系統(tǒng)中的應(yīng)用研究[J]. 公路交通科技, 2007,(12)
[2] 楊兆升. 關(guān)于智能運(yùn)輸系統(tǒng)的關(guān)鍵理論——綜合路段行程時(shí)間預(yù)測(cè)的研究[J]. 交通運(yùn)輸工程學(xué)報(bào), 2001,(01)