Dijkstra算法的改進(jìn)及其在車(chē)輛導(dǎo)航系統(tǒng)中的應(yīng)用

郭春樺

摘 要：本文分別闡述傳統(tǒng)Dijkstra算法和改進(jìn)Dijkstra算法的算法思想，并在仿真實(shí)驗(yàn)中比較這兩個(gè)算法在實(shí)際應(yīng)用中的效果，用具體數(shù)據(jù)證明改進(jìn)Dijkstra算法能更好的解決當(dāng)前交通擁堵問(wèn)題。

關(guān)鍵詞：Dijkstra算法；最短路徑；最優(yōu)路徑；帶權(quán)圖；車(chē)輛導(dǎo)航

1 引言

隨著我國(guó)經(jīng)濟(jì)的快速發(fā)展，很多家庭都擁有汽車(chē)，私家車(chē)數(shù)量的劇增，使得交通路況惡化，交通擁堵現(xiàn)象越來(lái)越嚴(yán)重。這給居民的出行帶來(lái)了極大的不便，嚴(yán)重影響了我們的工作生活。為了解決交通擁堵的問(wèn)題，各相關(guān)部門(mén)采取了很多措施，增派交警到關(guān)鍵路段指揮，車(chē)輛限行政策，甚至是增加道路基礎(chǔ)設(shè)施建設(shè)，但這些措施要么收效甚微，要么成本昂貴。這種情況下，各國(guó)紛紛致力于新興交通科技的研究，以應(yīng)對(duì)目前嚴(yán)峻的交通環(huán)境。車(chē)輛導(dǎo)航系統(tǒng)就是其中最重要的一項(xiàng)技術(shù)，它通過(guò)向駕駛員提供到達(dá)目的地的最優(yōu)路徑來(lái)引導(dǎo)駕駛員行駛，縮短車(chē)輛在道路上的停留時(shí)間，進(jìn)而減少擁堵，改善交通情況。

2 最優(yōu)路徑的內(nèi)涵

對(duì)于車(chē)輛導(dǎo)航的研究，為駕駛者選擇一條最好的路徑是關(guān)鍵。人們剛開(kāi)始關(guān)注的是基于已有道路基礎(chǔ)的從當(dāng)前位置到目標(biāo)地點(diǎn)路程最短的路徑，這種路徑是靜態(tài)不變。但在現(xiàn)實(shí)應(yīng)用中，由于交通情況是不斷變化的，兩點(diǎn)間路程最短并不表示出行時(shí)間最短，當(dāng)最短路徑擁堵時(shí)，路程長(zhǎng)的路徑可能反倒耗時(shí)短。因此最優(yōu)路徑必須將實(shí)時(shí)交通流的分布狀況和其他因素加入到考慮分析中，選擇行駛時(shí)間最短的路徑，更能滿足實(shí)際的需要，這種時(shí)間最短的路徑，是基于實(shí)時(shí)交通信息的、是動(dòng)態(tài)的。

3 Dijkstra算法求路程最短路徑

Dijkstra算法是目前求解最短路徑問(wèn)題的理論上最完備、應(yīng)用最廣泛的經(jīng)典算法，它可以求出帶權(quán)圖中指定頂點(diǎn)到圖中其他所有頂點(diǎn)的最短路徑。其基本思想是按路徑長(zhǎng)度遞增的次序產(chǎn)生最短路徑：

把圖中所有頂點(diǎn)V分成兩組：

⑴S：已求出最短路徑的頂點(diǎn)的集合

⑵T=V-S：尚未確定最短路徑的頂點(diǎn)集合

依據(jù)起點(diǎn)v到T中頂點(diǎn)vk的最短路徑，要么是從v到vk的直接路徑的權(quán)值，要么是從v經(jīng)S中頂點(diǎn)到vk的路徑權(quán)值之和，將T中頂點(diǎn)按最短路徑遞增的次序加入到S中。

那么，現(xiàn)在只要把交通路網(wǎng)抽象成一個(gè)帶權(quán)圖，就可以利用Dijkstra算法確定兩地間的最短路徑，具體規(guī)定如下：

⑴頂點(diǎn)：道路的交叉口或端點(diǎn)

⑵?。簝身旤c(diǎn)之間的路段（含有方向）

⑶弧的權(quán)：路段長(zhǎng)度

⑷路段上的任一地點(diǎn)依靠其最近的頂點(diǎn)。

4 改進(jìn)Dijkstra算法求基于實(shí)時(shí)交通信息的時(shí)間最短路徑——最優(yōu)路徑

4.1 影響行駛時(shí)間的因素有哪些

⑴擁堵情況；

⑵紅綠燈的延誤時(shí)間；

4.2 把影響因素按照一定標(biāo)準(zhǔn)進(jìn)行量化

對(duì)于擁堵情況，我國(guó)公布的《城市交通管理評(píng)價(jià)指標(biāo)體系》中規(guī)定，用城市路上機(jī)動(dòng)車(chē)的平均行駛速度來(lái)描述起交通擁堵程度：⑴暢通：不低于30km/h；⑵輕度擁擠：20～30km/h；⑶擁擠：10～20km/h；⑷嚴(yán)重?fù)頂D：低于10km/h。這樣就能根據(jù)路段長(zhǎng)度和平均行駛速度計(jì)算得到該路段的行駛時(shí)間。對(duì)于紅綠燈，直接把延誤時(shí)間作為度量標(biāo)準(zhǔn)。這些實(shí)時(shí)數(shù)據(jù)，可以通過(guò)各種交通服務(wù)設(shè)施獲得，如環(huán)形線圈檢測(cè)器等。

4.3 將城市路網(wǎng)抽象，建立相關(guān)網(wǎng)絡(luò)模型

⑴頂點(diǎn)V：道路交叉口或端點(diǎn)

⑵頂點(diǎn)的權(quán)Wv：紅綠燈延誤時(shí)間

⑶弧R：兩頂點(diǎn)間的路段

⑷弧的權(quán)Wr：路段需要的行駛時(shí)間

⑸路段上的任一地點(diǎn)依靠其最近的頂點(diǎn)。

傳統(tǒng)的Dijkstra算法中，頂點(diǎn)是不含權(quán)重的，但我們確定最短時(shí)間路徑時(shí)，交叉口的時(shí)間延誤必須考慮在內(nèi)，所以頂點(diǎn)是有權(quán)值的。

4.4 在上述網(wǎng)絡(luò)模型中求時(shí)間最短路徑的算法

根據(jù)以上分析，為了求時(shí)間最短路徑，改進(jìn)的Dijkstra算法描述如下：

⑴假設(shè)用帶權(quán)鄰接矩陣arcs表示帶權(quán)有向圖，arcs[i][j]表示弧的權(quán)，若弧不存在，則權(quán)值為∞；用向量W表示頂點(diǎn)的權(quán)，W[i]表示頂點(diǎn)vi的權(quán)值；S表示已求出最短路徑的頂點(diǎn)的集合，初態(tài)為空；V-S表示尚未確定最短路徑的頂點(diǎn)集合，初態(tài)為全部頂點(diǎn)；向量D，它的每個(gè)分量D[i]表示從始點(diǎn)v到每個(gè)終點(diǎn)vi的最短路徑的長(zhǎng)度，初態(tài)為：

⑵取vj，使得

vj就是當(dāng)前求得的一條從v出發(fā)的最短路徑的終點(diǎn)，令

⑶修改從v出發(fā)到集合V-S上任一頂點(diǎn)vk可達(dá)的最短路徑長(zhǎng)度，如果

則修改D[k]為

⑷重復(fù)操作（2）（3），直到求出到指定頂點(diǎn)的最短路徑。

⑸仿真實(shí)驗(yàn)

下面以一個(gè)模擬路網(wǎng)為例，說(shuō)明路程行駛時(shí)間和最優(yōu)路徑求解方法。

圖1表示按傳統(tǒng)方法抽象的交通路網(wǎng)，這里，弧上的權(quán)表示路程（單位km），為了簡(jiǎn)化示意圖，直線表示雙行線，箭頭表示單行線。

取得實(shí)時(shí)交通信息之后，計(jì)算出每段路程所需的行駛時(shí)間，并添加紅綠燈延誤時(shí)間，得到新的帶權(quán)有向圖（圖2），其中，弧上的權(quán)表示所需行駛時(shí)間，頂點(diǎn)中的權(quán)表示紅綠燈延誤時(shí)間，單位分鐘。

1）假設(shè)始點(diǎn)是v，目標(biāo)地點(diǎn)是v5，傳統(tǒng)Dijkstra算法執(zhí)行過(guò)程：

求出v到達(dá)v5的路程最短路徑為v—v3—v2—v5，路程長(zhǎng)度為12km。

2）改進(jìn)Dijkstra算法算法執(zhí)行過(guò)程：

求出v到達(dá)v5的行駛時(shí)間最短路徑為v—v1—v5，所需行駛時(shí)間為15分鐘，而傳統(tǒng)Dijkstra算法求出的路徑在相同的交通情況中需要時(shí)間31分鐘，實(shí)驗(yàn)數(shù)據(jù)表明，改進(jìn)的Dijkstra算法求得的路徑雖然路程比較遠(yuǎn)（21km），但由于只要經(jīng)過(guò)一個(gè)紅綠燈，延誤時(shí)間少，而且，路況良好，車(chē)流比較順暢，所以所需行駛時(shí)間比傳統(tǒng)Dijkstra算法求得的路徑少了許多，這種方案更能滿足用戶(hù)的實(shí)際需要，而且引導(dǎo)駕駛者避免擁擠的路段，選擇車(chē)流相對(duì)順暢的路段，更能解決交通擁堵的問(wèn)題。

[參考文獻(xiàn)]

[1]賀正兵，關(guān)偉.考慮信號(hào)交叉口影響的分散路徑誘導(dǎo)策略[J].北京工業(yè)大學(xué)學(xué)報(bào)，2013（10）.

[2]嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）.清華大學(xué)出版社.1996.

[3]王一松.基于實(shí)時(shí)交通信息的最優(yōu)路徑規(guī)劃算法研究[J].計(jì)算機(jī)與現(xiàn)代化，2013（2）.

[4]衛(wèi)瑋.基于實(shí)時(shí)交通信息的最優(yōu)路徑算法研究與實(shí)現(xiàn)[D].長(zhǎng)安大學(xué).2009.

[5]翟振，孫鑫，李志鋒.基于Dijkstra算法的車(chē)輛導(dǎo)航系統(tǒng)路線優(yōu)化技術(shù)[J].測(cè)繪科學(xué).2008（S1）.

[6]李妍峰.基于實(shí)時(shí)交通信息的城市動(dòng)態(tài)網(wǎng)絡(luò)車(chē)輛路徑優(yōu)化問(wèn)題[J].系統(tǒng)工程理論與實(shí)踐.2013（7）.

[7]田明星.路徑規(guī)劃在車(chē)輛導(dǎo)航系統(tǒng)中的應(yīng)用研究[D].北京交通大學(xué). 2009.

[8]李進(jìn)燕.基于簡(jiǎn)化路網(wǎng)模型的行程時(shí)間預(yù)測(cè)及導(dǎo)航算法研究[D].重慶大學(xué).2012.