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

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

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

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

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

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