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

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

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

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