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

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

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

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

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

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