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

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

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

3、節(jié)點表及路段表中，當路徑規(guī)劃完畢時，會自動刪除。靜態(tài)拓撲構建在動態(tài)拓撲構建的基礎上提出，解決了動態(tài)拓撲在大范圍內構建時間過長的問題。靜態(tài)拓撲構建在用戶離線使用選擇工具選取的任意范圍內進行拓撲構建，并能夠拼接各個靜態(tài)拓撲分塊，靜態(tài)拓撲完成后存儲靜態(tài)拓撲文件，在加載地圖的同時自動由拓撲文件讀入已有的拓撲信息，省去了路徑規(guī)劃在拓撲構建部分的耗時，縮短了路徑規(guī)劃的總時間，提高了實時性。構建所得的拓撲信息可用于一般意義下的路徑規(guī)劃程序，具有一定的

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