車輛導航系統(tǒng)中的路徑規(guī)劃算法研究.pdf

1、隨著城市化進程的推動和城市規(guī)模的擴大，交通中存在的問題如交通擁堵、交通事故等在一定程度上制約著城市化的發(fā)展。要改善這一問題，最有效的方法之一就是通過高效的導航系統(tǒng)來提高駕駛員的出行效率。最優(yōu)路徑規(guī)劃技術(shù)是車輛導航系統(tǒng)中的關(guān)鍵性技術(shù)，高性能的路徑查詢算法以及其有效實現(xiàn)，對車輛導航系統(tǒng)來說是很重要的。算法的優(yōu)越程度，在很大程度上影響著導航設備的性能。
　　 目前，國內(nèi)外學者對此已作出了大量的研究。傳統(tǒng)的以Dijkstra算法為代表最

2、優(yōu)路徑規(guī)劃算法，大都屬于貪心搜索算法的范疇，存在局部最小問題，而且計算量過大，隨著數(shù)據(jù)規(guī)模的增大，這種現(xiàn)象將更加突出；即使帶有啟發(fā)性搜索的A*算法也存在局部最優(yōu)等特點，很難從整體上找到最優(yōu)解，并且啟發(fā)函數(shù)的確定也是件不容易的事；新興的仿生型蟻群算法，很大程度上依賴于參數(shù)的設置，而且易于陷入局部最優(yōu)解等。當前大多數(shù)算法在進行路徑查詢時，搜索是建立在整個數(shù)據(jù)集上，沒提前對數(shù)據(jù)集進行較為合理的優(yōu)化，降低了算法的執(zhí)行效率?？梢娧芯扛咝У?、高質(zhì)

3、量的、易于實現(xiàn)的路徑規(guī)劃算法是很必要的。
　　 論文綜合分析了交通中存在的問題、導航系統(tǒng)的國內(nèi)外研究現(xiàn)狀及其相關(guān)技術(shù)，并對路徑算法做了深入的研究，重點研究了Dijkstra算法、A*算法、遺傳算法和蟻群算法。并對上述算法的優(yōu)缺點、應用條件及運用范圍進行了深入研究和分析。A*算法通過引入啟發(fā)函數(shù)，啟發(fā)函數(shù)由代表從起點到當前結(jié)點的實際代價和當前結(jié)點到目標的估計代價兩部分組成，在執(zhí)行過程中，通過比較當前結(jié)點的啟發(fā)函數(shù)值來決定下一個被擴

4、散的結(jié)點；燃燒算法是一種類似于點擴散的算法，算法從指定的點開始逐漸蔓延到周圍的臨接點，直到找到另一點為止。在此基礎(chǔ)上，通過引入虛的起始點、中心點等方法建立了預處理模型，以實現(xiàn)對數(shù)據(jù)集的快速優(yōu)化，使最有可能成為最優(yōu)路徑上的數(shù)據(jù)進入將被搜索的數(shù)據(jù)集合：在路徑更新階段引入結(jié)點互換策略等，綜合燃燒算法和A*算法的思想，提出了改進的路徑算法-A-燃算法，A-燃算法在執(zhí)行上分為預處理階段和處理階段，前者實現(xiàn)對有效數(shù)據(jù)的快速界定，后者實現(xiàn)對路段的計算