基于圖論的動態(tài)導(dǎo)航系統(tǒng)最短路徑算法研究.pdf

1、近幾年來，隨著國民經(jīng)濟的發(fā)展，城市中機動車輛漸漸增多，交通需求在不斷增加，公路交通流量也越來越大，由此導(dǎo)致了交通擁堵的頻繁發(fā)生，城市交通正面臨著越來越大的壓力。在這種形勢下，基于靜態(tài)地圖的自主導(dǎo)航雖然可為駕駛員規(guī)劃一條“最短”路徑，但卻無法避開前方道路可能發(fā)生的交通擁擠。而動態(tài)導(dǎo)航則不同，系統(tǒng)獲知出發(fā)點與目的地之間的交通狀況，經(jīng)過規(guī)劃得到一條滿足用戶需求的合理路徑。這種導(dǎo)航方式不僅可以有效的避開擁堵，節(jié)省出行成本，而且對整個路網(wǎng)有著良性

2、影響。 本文研究了車載動態(tài)導(dǎo)航系統(tǒng)最優(yōu)路徑規(guī)劃的系統(tǒng)方法，包括：交通路網(wǎng)的矢量地圖表達(dá)，圖論中的最短路徑算法，動態(tài)時間權(quán)重的最優(yōu)路徑規(guī)劃等。 首先，簡述了有關(guān)地理信息系統(tǒng)的一些基本概念，包括地理信息系統(tǒng)概念、地理信息系統(tǒng)數(shù)據(jù)模型、地理信息系統(tǒng)數(shù)據(jù)的組織和管理，針對城市交通道路網(wǎng)的特點，著重分析研究了城市交通道路網(wǎng)的矢量地圖表達(dá)、網(wǎng)絡(luò)中的交通限制信息的表示等。 其次，本文介紹了圖論的相關(guān)理論，研究了圖的鄰接矩陣、鄰

3、接表的表達(dá)方式，對圖的搜索方式進行了分析，基于邊帶的通用圖搜索，基于FIFO隊列的廣度優(yōu)先搜索，基于棧的深度優(yōu)先搜索。同時分析了Dijkstra算法求單源點最短路徑問題，即圖的最短路徑樹，以及用在交通網(wǎng)絡(luò)中的歐幾米得試探法。 最后，本文研究了基于交通路網(wǎng)的A*算法，該算法能夠有效降低Dijkstra算法的時間復(fù)雜性，提高系統(tǒng)的運行效率。提出了從起點到終點所用時間最短的路徑的方法，即所謂的時間最短路徑算法。確定了算法對路段動態(tài)阻抗