基于GPS的最佳動(dòng)態(tài)路徑分析與仿真研究

張?jiān)骑w 楊亞茹 鄭虎龍 段傳緒 王廉拓

摘要：利用車輛導(dǎo)航技術(shù)的反饋信息，通過A*算法對靜態(tài)路網(wǎng)的最優(yōu)路徑做出動(dòng)態(tài)選擇。基于靜態(tài)路網(wǎng)信息的最優(yōu)路徑求解是現(xiàn)時(shí)車輛GPS導(dǎo)航領(lǐng)域所面臨的關(guān)鍵問題。現(xiàn)今流行的Dijkstra算法、A*算法等，都是基于完全靜態(tài)、確定的信息數(shù)據(jù)庫下，求解得出的最短路徑。本文通過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)車保有量的快速增長，尤其私家小汽車的快速發(fā)展，城市交通越發(fā)擁擠。由于土地資源不足，建造各種公路等物理設(shè)施的能力是有限的， 所以單純地依靠修建更多的道路、擴(kuò)大路網(wǎng)規(guī)模等這樣的措施僅僅能解一時(shí)之需， 并不能從根本上解決日益增長的交通需求。基于這種需要，提出了以車載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ī)模化發(fā)展階段。

1基于靜態(tài)路網(wǎng)的A*算法原理

一條路徑的確定取決于許多因素，如距離、行程時(shí)間、路網(wǎng)彎數(shù)、路況復(fù)雜度、轉(zhuǎn)向燈個(gè)數(shù)、交通信號燈的數(shù)目和動(dòng)態(tài)交通信息等。選擇最短路徑、最佳路徑、最低耗費(fèi)等問題，都離不開最短路徑搜索并以其作為選擇依據(jù)。路徑選擇標(biāo)準(zhǔn)可由程序設(shè)計(jì)決定或通過用戶界面修改。最短路徑問題的解決方法很多，包括啟發(fā)式搜索A*算法、動(dòng)態(tài)規(guī)劃方法、神經(jīng)網(wǎng)絡(luò)、Dijkstra 算法等，其中以迪杰斯特拉（Dijkstra）算法在實(shí)際應(yīng)用中較為廣泛。由于Dijkstra算法的搜索過程屬于遍歷計(jì)算，所以出現(xiàn)大量的搜索節(jié)點(diǎn)。其中，由于所引入的動(dòng)態(tài)算法，是要求處理大量的靜態(tài)數(shù)據(jù)的同時(shí)，還需要實(shí)時(shí)監(jiān)測接受的動(dòng)態(tài)數(shù)據(jù)，并計(jì)算當(dāng)前對于最佳路徑的影響的一些數(shù)據(jù)。因此，處理量就變得相當(dāng)大，一般來說，硬件不能支持。A*算法是比較流行的啟發(fā)式搜索算法之一，被廣泛應(yīng)用于路徑的最優(yōu)解。A*算法對比其他算法，不同之處在于A*算法引入了啟發(fā)式函數(shù)。啟發(fā)式估價(jià)函數(shù)估價(jià)每一生成節(jié)點(diǎn)以確定此節(jié)點(diǎn)的優(yōu)劣性。通過這種方式，啟發(fā)式函數(shù)決定在諸多路徑中首先遍歷那條路徑以便搜索過程更為有效，因?yàn)樗惴ㄊ紫人阉髯顑?yōu)希望的節(jié)點(diǎn)。

2基于A*算法的最佳路徑求解

現(xiàn)實(shí)生活當(dāng)中，交通信息屬于動(dòng)態(tài)信息，即每一段路都有其自己的屬性。如果單純地從距離和時(shí)間出發(fā)，所得出的最短路徑與實(shí)際駕駛者所希望的并不能完全符合。譬如，得出的最短路徑上，有其中路段屬于交通擁堵嚴(yán)重的，及其路段的效率就相對低下。相對駕駛者來說，意味著比其他路徑所使用的路徑花費(fèi)更多時(shí)間。又或者即使路徑上沒有交通意外，堵塞等情況，但是路徑上出現(xiàn)較多的收費(fèi)設(shè)置，同樣對于駕駛者來說是不利的。因?yàn)檫@意味著花費(fèi)更多的費(fèi)用。

2.1GPS/DR（航位推算，Dead-Reckoning）組合定位的反饋信息

DR的基本原理是利用方向傳感器和速度傳感器來推算車輛的瞬時(shí)位置，可以實(shí)現(xiàn)連續(xù)自主式定位。但由于其推算過程是一個(gè)累加過程，方向傳感器的誤差隨時(shí)間的延長而積累，另外，推算只能確定相對位置和航向。因此，將航位推算與GPS 組合起來，兩者取長補(bǔ)短，可以彌補(bǔ)各自的缺點(diǎn)， 確保系統(tǒng)能在任何時(shí)候都能為運(yùn)動(dòng)車輛提供較為準(zhǔn)確的導(dǎo)航信息。一方面可以利用GPS精確的定位結(jié)果輔助DR 的初始化并且可以定期地用它對DR 的定位誤差進(jìn)行在線校正。另一方面，在GPS無法定位時(shí)系統(tǒng)又可以自動(dòng)地切換到DR 導(dǎo)航方式，直至GPS 恢復(fù)正常接收后， 系統(tǒng)再回到GPS 與DR 的組合導(dǎo)航方式。從而，即使在GPS失效、單獨(dú)使用DR推算定位時(shí)也能長時(shí)間保持較高的定位精度。

通過GPS反饋的定位信號進(jìn)行運(yùn)動(dòng)車輛的檢測和分割，預(yù)測其在相關(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ā)事故，并通過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ān)的約束條件進(jìn)行優(yōu)化。針對城鄉(xiāng)路網(wǎng)的特點(diǎn)，對最短路徑分析的各項(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)確、快速地檢測和提取出運(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ù)測的研究[J]. 交通運(yùn)輸工程學(xué)報(bào)， 2001，（01）