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

張云飛 楊亞茹 鄭虎龍 段傳緒 王廉拓

摘要：利用車輛導(dǎo)航技術(shù)的反饋信息，通過A*算法對靜態(tài)路網(wǎng)的最優(yōu)路徑做出動態(tài)選擇?；陟o態(tài)路網(wǎng)信息的最優(yōu)路徑求解是現(xiàn)時車輛GPS導(dǎo)航領(lǐng)域所面臨的關(guān)鍵問題?，F(xiàn)今流行的Dijkstra算法、A*算法等，都是基于完全靜態(tài)、確定的信息數(shù)據(jù)庫下，求解得出的最短路徑。本文通過A*算法充分利用靜態(tài)路網(wǎng)信息，借助車輛導(dǎo)航系統(tǒng)加以動態(tài)路網(wǎng)中的適應(yīng)條件，以及實時更新的交通數(shù)據(jù)，得出計算結(jié)果精確，時間復(fù)雜度較低，且符合實際情況的最佳路徑。

關(guān)鍵詞：交通調(diào)度? 動態(tài)路網(wǎng)? 最佳路徑? A*算法? GPS

引言：

目前，隨著社會經(jīng)濟(jì)的發(fā)展、城市化進(jìn)程的加快和機(jī)動車保有量的快速增長，尤其私家小汽車的快速發(fā)展，城市交通越發(fā)擁擠。由于土地資源不足，建造各種公路等物理設(shè)施的能力是有限的， 所以單純地依靠修建更多的道路、擴(kuò)大路網(wǎng)規(guī)模等這樣的措施僅僅能解一時之需， 并不能從根本上解決日益增長的交通需求?；谶@種需要，提出了以車載GPS（Global Positioning System）為核心的路徑分析系統(tǒng)。該技術(shù)是以GPS技術(shù)為核心， 綜合利用廣播技術(shù)、光電傳感器、計算機(jī)網(wǎng)絡(luò)、自動控制和人工智能等技術(shù)的一種新型車輛導(dǎo)航技術(shù)。

現(xiàn)階段，車載GPS進(jìn)入規(guī)?；l(fā)展階段。

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

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

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

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

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

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

通過GPS反饋的定位信號進(jìn)行運(yùn)動車輛的檢測和分割，預(yù)測其在相關(guān)路徑的運(yùn)動軌跡，從而根據(jù)交通流量綜合其他情況進(jìn)行調(diào)度，可以把發(fā)生沖突的交通流從時間和空間上進(jìn)行分離，穩(wěn)定平衡交通流的密度。

2.2廣播和交通部門信息的雙向調(diào)控

在通信網(wǎng)絡(luò)的支持下，參考廣播電臺的實時路面路況信息，即時接受交通部門發(fā)布的突發(fā)事故，并通過GSM通信網(wǎng)與移動中的車輛進(jìn)行通話、短信息傳輸和數(shù)據(jù)傳輸，完成車輛定位、調(diào)度、監(jiān)控、報警等功能，且在電子地圖上顯示車輛的位置，做出應(yīng)急路徑選擇，間接地約束最優(yōu)動態(tài)路徑，避免大面積的交通癱瘓，保證動態(tài)路網(wǎng)運(yùn)動車輛行駛路徑的準(zhǔn)確性。

其中，接受短信息可用GSM用戶終端（如車載臺、手機(jī)）或用可接收短信息功能的固定用戶設(shè)備，也可用ISDN方式直接連接到移動通信局的短消息服務(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)的特點，對最短路徑分析的各項關(guān)鍵技術(shù)進(jìn)行了研究，編寫了相關(guān)路徑選擇程序進(jìn)行了模擬，提出了一種實用的最佳路徑分析解決方案，在此基礎(chǔ)上實施了最佳路徑分析方法及技術(shù);城市交通設(shè)施和規(guī)則日益復(fù)雜，需要進(jìn)一步改進(jìn)數(shù)據(jù)模型，較完整地表達(dá)和建立了路網(wǎng)的拓?fù)潢P(guān)系。本文的算法能較準(zhǔn)確、快速地檢測和提取出運(yùn)動目標(biāo)，為交通調(diào)度提供了保障，有一定的實用價值。

參考文獻(xiàn)

[1] 楊利強(qiáng)，張寧，陶志祥. 3G移動通信技術(shù)在城市交通信息系統(tǒng)中的應(yīng)用研究[J]. 公路交通科技， 2007，（12）

[2] 楊兆升. 關(guān)于智能運(yùn)輸系統(tǒng)的關(guān)鍵理論——綜合路段行程時間預(yù)測的研究[J]. 交通運(yùn)輸工程學(xué)報， 2001，（01）