導(dǎo)航中路徑規(guī)劃的優(yōu)化算法研究.pdf

1、日益增長的汽車購買量，使得城市交通環(huán)境日漸嚴(yán)峻。智能的導(dǎo)航系統(tǒng)無論在方便出行，還是提高道路運輸效率上，都起到了十分重要的作用。路徑規(guī)劃作為導(dǎo)航系統(tǒng)的核心部分，根據(jù)存儲在其內(nèi)部的電子地圖拓?fù)湫畔?，在出發(fā)地和目的地確定的情況下，按照合理的策略快速準(zhǔn)確地向出行者提供行駛方案，以達(dá)到迅速、安全、經(jīng)濟(jì)的出行目的。因此，導(dǎo)航中路徑規(guī)劃的優(yōu)化算法研究顯得尤其重要。
　　電子地圖是導(dǎo)航進(jìn)行路徑規(guī)劃的基礎(chǔ)。本文在Visual C++6.0平臺下，結(jié)

2、合MapInfo MapX組件生成用于導(dǎo)航的電子地圖，并實現(xiàn)了地圖的基本功能，如放大、縮小、漫游、居中等。
　　路網(wǎng)的拓?fù)錁?gòu)建是路徑規(guī)劃的前提和關(guān)鍵。在詳細(xì)分析MapInfo地圖數(shù)據(jù)的內(nèi)部結(jié)構(gòu)，以及路網(wǎng)表達(dá)及存儲的特點和所須滿足的條件后，確定使用圖的結(jié)構(gòu)抽象表達(dá)路網(wǎng)。根據(jù)本文定義的拓?fù)鋽?shù)據(jù)信息的數(shù)據(jù)結(jié)構(gòu)和文件結(jié)構(gòu)，研究并實現(xiàn)了動態(tài)及靜態(tài)兩種路網(wǎng)拓?fù)錁?gòu)建的方法。動態(tài)拓?fù)錁?gòu)建的范圍根據(jù)用戶指定的起點與終點確定，拓?fù)錁?gòu)建結(jié)果存儲在內(nèi)存的

3、節(jié)點表及路段表中，當(dāng)路徑規(guī)劃完畢時，會自動刪除。靜態(tài)拓?fù)錁?gòu)建在動態(tài)拓?fù)錁?gòu)建的基礎(chǔ)上提出，解決了動態(tài)拓?fù)湓诖蠓秶鷥?nèi)構(gòu)建時間過長的問題。靜態(tài)拓?fù)錁?gòu)建在用戶離線使用選擇工具選取的任意范圍內(nèi)進(jìn)行拓?fù)錁?gòu)建，并能夠拼接各個靜態(tài)拓?fù)浞謮K，靜態(tài)拓?fù)渫瓿珊蟠鎯o態(tài)拓?fù)湮募?，在加載地圖的同時自動由拓?fù)湮募x入已有的拓?fù)湫畔ⅲ∪チ寺窂揭?guī)劃在拓?fù)錁?gòu)建部分的耗時，縮短了路徑規(guī)劃的總時間，提高了實時性。構(gòu)建所得的拓?fù)湫畔⒖捎糜谝话阋饬x下的路徑規(guī)劃程序，具有一定的

4、通用性。
　　為了高效實現(xiàn)路徑規(guī)劃，本文從圖論切入，詳細(xì)介紹了經(jīng)典的Dijkstra算法及Floyd算法，并給出了具體實現(xiàn)步驟。分析二者的優(yōu)缺點后，選擇簡單易實現(xiàn)的Dijkstra算法從搜索區(qū)域及搜索方向兩個方面進(jìn)行優(yōu)化，研究并實現(xiàn)了限制搜索區(qū)域和雙向搜索的最優(yōu)路徑規(guī)劃算法。最后在拓?fù)錁?gòu)建的電子地圖中實現(xiàn)了路徑規(guī)劃的功能，驗證了改進(jìn)Dijkstra算法的正確性及有效性，并將優(yōu)化后的Dijkstra算法與原經(jīng)典Dijkstra及Fl