基于GPS的最佳動態路徑分析與仿真研究

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

摘要：利用車輛導航技術的反饋信息，通過A*算法對靜態路網的最優路徑做出動態選擇。基于靜態路網信息的最優路徑求解是現時車輛GPS導航領域所面臨的關鍵問題。現今流行的Dijkstra算法、A*算法等，都是基于完全靜態、確定的信息數據庫下，求解得出的最短路徑。本文通過A*算法充分利用靜態路網信息，借助車輛導航系統加以動態路網中的適應條件，以及實時更新的交通數據，得出計算結果精確，時間復雜度較低，且符合實際情況的最佳路徑。

關鍵詞：交通調度? 動態路網? 最佳路徑? A*算法? GPS

引言：

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

現階段，車載GPS進入規模化發展階段。

1基于靜態路網的A*算法原理

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

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

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

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

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

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

2.2廣播和交通部門信息的雙向調控

在通信網絡的支持下，參考廣播電臺的實時路面路況信息，即時接受交通部門發布的突發事故，并通過GSM通信網與移動中的車輛進行通話、短信息傳輸和數據傳輸，完成車輛定位、調度、監控、報警等功能，且在電子地圖上顯示車輛的位置，做出應急路徑選擇，間接地約束最優動態路徑，避免大面積的交通癱瘓，保證動態路網運動車輛行駛路徑的準確性。

其中，接受短信息可用GSM用戶終端（如車載臺、手機）或用可接收短信息功能的固定用戶設備，也可用ISDN方式直接連接到移動通信局的短消息服務中心，并聯通車輛導航管理系統，這樣接收短信息更迅捷，容量更大。

結論

本文討論分析了基于車輛監控導航系統的A*算法最佳路徑，并通過相關的約束條件進行優化。針對城鄉路網的特點，對最短路徑分析的各項關鍵技術進行了研究，編寫了相關路徑選擇程序進行了模擬，提出了一種實用的最佳路徑分析解決方案，在此基礎上實施了最佳路徑分析方法及技術;城市交通設施和規則日益復雜，需要進一步改進數據模型，較完整地表達和建立了路網的拓撲關系。本文的算法能較準確、快速地檢測和提取出運動目標，為交通調度提供了保障，有一定的實用價值。

參考文獻

[1] 楊利強，張寧，陶志祥. 3G移動通信技術在城市交通信息系統中的應用研究[J]. 公路交通科技， 2007，（12）

[2] 楊兆升. 關于智能運輸系統的關鍵理論——綜合路段行程時間預測的研究[J]. 交通運輸工程學報， 2001，（01）