基于時間最短原則的路徑規(guī)劃算法研究.pdf

1、車載智能導航終端是車聯(lián)網(wǎng)中的重要節(jié)點，在汽車數(shù)量日益增加、路況條件逐漸緊張的情況下，具有提高出行效率的作用。它通過路徑規(guī)劃的方式輔助駕駛員選擇行車路線。路徑規(guī)劃可以按照距離和時間等條件選擇最佳路線。隨著國家對車聯(lián)網(wǎng)的重視以及人們生活節(jié)奏的加快，研究基于時間最短原則的路徑規(guī)劃算法以及它在車載導航系統(tǒng)上的實現(xiàn)方法，有助于滿足人們的實際出行需求并為車聯(lián)網(wǎng)的具體開展提供依據(jù)。論文在研究地圖數(shù)據(jù)存儲技術的基礎上，重點對路網(wǎng)數(shù)據(jù)存儲結構和基于時間最

2、短原則的路徑規(guī)劃算法展開研究，并在車載導航系統(tǒng)中實現(xiàn)和驗證路徑規(guī)劃算法。
　　論文的主要研究內容如下：
　　1.地圖數(shù)據(jù)存儲技術研究。
　　在分析地圖數(shù)據(jù)模型和實際需求基礎上，本文設計一種二進制數(shù)據(jù)存儲方式存儲地圖數(shù)據(jù)，數(shù)據(jù)占用的存儲空間較小。分開存儲屬性信息和幾何數(shù)據(jù)信息，建立兩種數(shù)據(jù)的交互索引關系。針對經(jīng)緯度坐標到平面坐標轉換計算較為復雜的情況，本文建立線性轉化模型實現(xiàn)地心地固(Earth-centered, Ea

3、rth-fixed, ECEF)坐標系下經(jīng)緯度坐標到本地坐標系下平面坐標的快速轉換。在保證地圖精度的條件下，提出整型數(shù)據(jù)代替浮點數(shù)據(jù)的存儲方式，在進一步減小數(shù)據(jù)存儲的物理空間的同時，提高了地圖幾何數(shù)據(jù)到屏幕坐標的轉換效率，加快了地圖繪制的速度。
　　2.路網(wǎng)數(shù)據(jù)存儲方法研究。
　　基于地圖數(shù)據(jù)形成的路網(wǎng)是路徑規(guī)劃的基礎，路網(wǎng)的質量直接影響路徑規(guī)劃算法的效率。為了加快拓展速度和減小存儲空間，設計了一種節(jié)點向后拓展結構來存儲路網(wǎng)

4、的拓撲關系數(shù)據(jù)結構。分析以時間為基礎的路段不同類型權值的計算方法，將時間作為路網(wǎng)數(shù)據(jù)的一部分實現(xiàn)路網(wǎng)數(shù)據(jù)存儲，支持路徑規(guī)劃算法中對路段時間權值的解算。
　　3.路徑規(guī)劃算法研究。
　　重點研究Dijkstra和A*路徑規(guī)劃算法原理，對比其在搜索空間和執(zhí)行時間上的差異；針對實際應用中始點和終點為具體目標點而與道路獨立的情況，分析始點和終點到道路節(jié)點的匹配全過程。在此基礎上，針對課題需求，通過建立路況數(shù)據(jù)庫模擬實時路況，將實時路

5、況信息與屬性數(shù)據(jù)結合進行路段動態(tài)行駛時間的預測，研究并提出了一種改進的A*算法，并建立了改進算法的節(jié)點估計、時間預測算法和實現(xiàn)流程。
　　4.車載導航系統(tǒng)中行程時間最短的路徑規(guī)劃算法實現(xiàn)。
　　以ARM為控制核心基于Linux系統(tǒng)設計完成了車載導航系統(tǒng)，主要功能包括地圖顯示、地圖縮放和漫游、目標點和興趣點搜索、實時定位、地圖匹配、路徑規(guī)劃以及路徑引導。作為車載導航系統(tǒng)的核心功能，在完成常用的以最短距離等效的行程時間最短路徑規(guī)