GPS車載導(dǎo)航系統(tǒng)最優(yōu)路徑搜索算法研究.pdf

1、近年來，隨著交通運(yùn)輸業(yè)的不斷進(jìn)步發(fā)展，車載導(dǎo)航系統(tǒng)成為目前交通應(yīng)用領(lǐng)域里的重要研究課題。車載導(dǎo)航系統(tǒng)為用戶提供基于實(shí)時路況信息的最優(yōu)路徑規(guī)劃，可以減少車輛在道路上的停留時間，減少汽車尾氣排放量，達(dá)到減少霧霾改善環(huán)境的目的，也為出行者節(jié)省了大量的出行時間，使道路資源得到充分地利用。因此，用戶出行的路徑規(guī)劃變的尤為重要。
　　車載導(dǎo)航系統(tǒng)的核心部分是路徑規(guī)劃，路徑規(guī)劃要求系統(tǒng)能夠根據(jù)存儲的電子地圖拓?fù)湫畔?，按照某種規(guī)劃算法幫助駕駛者從

2、始發(fā)地到目的地規(guī)劃出一條最優(yōu)路徑，車載導(dǎo)航系統(tǒng)中路徑規(guī)劃算法研究具有重要意義。車載導(dǎo)航系統(tǒng)中常見的路徑規(guī)劃算法主要是Dijkstra算法和A*算法，但現(xiàn)有算法在路徑規(guī)劃過程中效率低，不適合直接應(yīng)用于車載導(dǎo)航系統(tǒng)中，需要對其進(jìn)行相應(yīng)的改進(jìn)和優(yōu)化。
　　本論文主要從改進(jìn)算法數(shù)據(jù)結(jié)構(gòu)和A*算法估價(jià)函數(shù)兩方面入手，對原始算法進(jìn)行優(yōu)化。鑒于偵測交通路況的技術(shù)目前已經(jīng)很成熟，本文假設(shè)在路段交通情況已知的情況下，對多種經(jīng)典算法規(guī)劃的路徑進(jìn)行評估

3、，并在原有算法的基礎(chǔ)上進(jìn)行改良。先研究了Dijkstra算法，對該算法的實(shí)現(xiàn)過程進(jìn)行了描述，由于Dijkstra算法屬于貪心算法，計(jì)算最短路徑的過程是將路網(wǎng)中所有節(jié)點(diǎn)進(jìn)行遍歷，算法執(zhí)行效率很低，并且占用大量存儲空間，不適合直接應(yīng)用于車載系統(tǒng)。然后對A*算法的實(shí)現(xiàn)過程進(jìn)行了描述，通過對Dijkstra算法和A*算法進(jìn)行比較，重點(diǎn)對啟發(fā)式搜索算法A*算法進(jìn)行優(yōu)化改進(jìn)。在數(shù)據(jù)結(jié)構(gòu)優(yōu)化方面，通過二叉堆排序的方法對節(jié)點(diǎn)進(jìn)行排序，在反復(fù)存取節(jié)點(diǎn)的過

4、程中節(jié)約了大量時間，有效地提高了算法的執(zhí)行效率。在估價(jià)函數(shù)的改進(jìn)方面，在路段搜索時加入方向性判別，選擇與終點(diǎn)為同一方向且距離較近的節(jié)點(diǎn)，提高算法的執(zhí)行效率。在實(shí)際路況應(yīng)用中，應(yīng)充分考慮影響行車時間的各類因素，比如交通擁堵、路段時速等因素。論文提出綜合考慮距離和路段時速因素，對距離和路段時速分配不同的權(quán)值，規(guī)劃出距離終點(diǎn)近且速度快的路段，從而規(guī)劃出行車所需時間最少的路徑，使之成為最優(yōu)路徑。
　　論文最后通過微軟公司的Microsof

5、t Visual Studio2010軟件和Mapinfo軟件，分別產(chǎn)生不同數(shù)量的節(jié)點(diǎn)和線路，并對路網(wǎng)中的節(jié)點(diǎn)和線路進(jìn)行了路徑規(guī)劃。最終通過實(shí)驗(yàn)數(shù)據(jù)證明，當(dāng)路網(wǎng)節(jié)點(diǎn)為200個時，原始算法規(guī)劃路徑為15.7公里，論文改進(jìn)算法為13.2公里，規(guī)劃路徑距離減少了2.5公里;原始算法規(guī)劃時間為53毫秒，論文改進(jìn)算法為20毫秒，效率提高了33毫秒。當(dāng)路網(wǎng)節(jié)點(diǎn)為1000個時，原始算法規(guī)劃路徑為76.1公里，論文改進(jìn)算法為64.7公里，規(guī)劃路徑距離減