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

1、日益增長(zhǎng)的汽車購(gòu)買量，使得城市交通環(huán)境日漸嚴(yán)峻。智能的導(dǎo)航系統(tǒng)無(wú)論在方便出行，還是提高道路運(yùn)輸效率上，都起到了十分重要的作用。路徑規(guī)劃作為導(dǎo)航系統(tǒng)的核心部分，根據(jù)存儲(chǔ)在其內(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平臺(tái)下，結(jié)

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

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

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