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

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

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

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

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