基于洪泛查詢的最短路徑算法在智能交通系統(tǒng)中的應(yīng)用

賴培輝+曾黨泉

摘 要：針對(duì)智能交通系統(tǒng)中道路暢通情況時(shí)刻變化的最短路徑求解問(wèn)題，提出了一種基于洪泛查詢的最短路徑算法。該算法采用洪泛思想，位于路網(wǎng)上的某一節(jié)點(diǎn)收到來(lái)自另一直連節(jié)點(diǎn)的路徑信息后，向除該節(jié)點(diǎn)之外的所有直連節(jié)點(diǎn)發(fā)送該路徑信息。當(dāng)一個(gè)節(jié)點(diǎn)收到多條來(lái)自同一源和去往同一目的的路徑信息時(shí)，對(duì)多條路徑信息的權(quán)值進(jìn)行比較，只轉(zhuǎn)發(fā)權(quán)值最小的路徑信息，即最短路徑信息。同時(shí)，該算法還能獲得多條次優(yōu)的最短路徑，以作為備用路徑，當(dāng)在最短路徑的某一段道路上發(fā)現(xiàn)了擁堵情況時(shí)，可以快速切換到另外一條次優(yōu)的最短路徑，且具有良好的健壯性和高效性。

關(guān)鍵詞：洪泛；最短路徑；智能交通系統(tǒng)；權(quán)值

中圖分類(lèi)號(hào)：TP301 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2095-1302（2015）07-00-03

0 引 言

交通系統(tǒng)在城市的發(fā)展中具有舉足輕重的作用。隨著我國(guó)城市化進(jìn)程的加快和居民生活水平的提高，城市人口數(shù)量迅速增長(zhǎng)，機(jī)動(dòng)車(chē)數(shù)量越來(lái)越多，因此交通阻塞、交通事故問(wèn)題日趨惡化，交通阻塞造成的經(jīng)濟(jì)損失巨大，僅依靠修建道路、擴(kuò)大道路網(wǎng)絡(luò)規(guī)模等傳統(tǒng)方法來(lái)緩解日益增長(zhǎng)的交通需求，已很難適應(yīng)我國(guó)社會(huì)經(jīng)濟(jì)快速發(fā)展的需求，最好的解決方法是建立城市的智能交通系統(tǒng)[1]。

在智能交通系統(tǒng)中，計(jì)算車(chē)輛到目的地的最短路徑是系統(tǒng)的基本功能。隨著交通實(shí)時(shí)信息采集手段的增多，使得智能交通系統(tǒng)完全可以根據(jù)實(shí)際的情況，進(jìn)行由當(dāng)前點(diǎn)到目標(biāo)點(diǎn)的最短路徑計(jì)算，以縮短車(chē)輛在途時(shí)間，提高道路的通行能力。由于實(shí)時(shí)交通狀況在不斷變化，時(shí)間最短路徑是動(dòng)態(tài)的，在實(shí)際應(yīng)用中，就有必要不斷進(jìn)行相關(guān)的計(jì)算，以確定當(dāng)前的時(shí)間最短路徑[2]。

智能交通系統(tǒng)中最短路徑的查詢，主要是點(diǎn)到點(diǎn)之間的最短路徑，在城市交通中具有很高的實(shí)時(shí)性，要求對(duì)大量的查詢給予快速答復(fù)。有關(guān)最短路徑的算法， 經(jīng)典的有Dijkstra[3]和Floyd[4]算法， 但由于空間的限制， 現(xiàn)在基于實(shí)時(shí)系統(tǒng)計(jì)算的最短路徑往往使用Dijkstra 算法或基于其上的一些變形算法，文獻(xiàn)[5]列出并比較了一些常用的實(shí)現(xiàn)方法。本文針對(duì)智能交通系統(tǒng)中實(shí)時(shí)變化的道路信息，提出基于洪泛查詢的最短路徑算法來(lái)求解智能交通系統(tǒng)中動(dòng)態(tài)變化的道路信息的最短路徑，該算法還同時(shí)兼顧多條次優(yōu)路徑來(lái)作為備用路徑，一旦最優(yōu)路徑上某個(gè)部分發(fā)生擁塞情況就可以快速切換到備用路徑。

1 算法設(shè)計(jì)

1.1 問(wèn)題描述

本文針對(duì)的是城市交通路網(wǎng)中最短路徑求解的問(wèn)題，在進(jìn)行問(wèn)題描述時(shí)，將交通路網(wǎng)映射為一個(gè)帶權(quán)有向圖模型，路網(wǎng)的交叉點(diǎn)為圖的節(jié)點(diǎn)，路徑為圖的邊，邊為帶權(quán)的有向圖，表示是雙向通行道路還是單行道。因此，該路網(wǎng)可描述為：帶權(quán)有向圖G=（V，E，w） ，其中，V 是包含N個(gè)節(jié)點(diǎn)的節(jié)點(diǎn)集，E是包含m條邊的邊集，是E中從vi到vj的邊，w是邊〈vi，vj〉（ 1≤i，j≤N） 的非負(fù)權(quán)值，其權(quán)值表示從節(jié)點(diǎn)vi到vj的度量值（度量值可以是時(shí)間，也可以是距離或是一個(gè)綜合值）。對(duì)于一條路徑從源點(diǎn)S到終點(diǎn)D，中間經(jīng)過(guò)若干個(gè)節(jié)點(diǎn)，設(shè)源點(diǎn)為v'0、終點(diǎn)為v'k，中間的節(jié)點(diǎn)為v'1， v'2，…，v'k-1，則該條路徑上的權(quán)值總和可表示為：

從源點(diǎn)S到終點(diǎn)D的路徑可能有多條，其中的Wmin為最短路徑。如何找出其中的最短路徑呢？本文設(shè)計(jì)了一種基于洪泛查詢的最短路徑搜索算法。

1.2 算法描述

基于洪泛查詢的最短路徑搜索算法采用了洪泛的思想，從源點(diǎn)S出發(fā)，向所有與之直接相連的節(jié)點(diǎn)發(fā)送數(shù)據(jù)，中間節(jié)點(diǎn)收到數(shù)據(jù)之后，向除收到數(shù)據(jù)之外的所有節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)（S，Vm，P（s，m），W（s，m）），其中S為源點(diǎn)，Vm為當(dāng)前節(jié)點(diǎn)，P（s，m）為從源點(diǎn)到當(dāng)前節(jié)點(diǎn)的路徑，W（s，m）為從源點(diǎn)到當(dāng)前節(jié)點(diǎn)的權(quán)值的總和。最先到達(dá)的終點(diǎn)的那條路徑為最短路徑。該算法的可以適應(yīng)時(shí)刻變化的城市路網(wǎng)交通，特別是在實(shí)時(shí)性非常強(qiáng)的智能交通中，城市中各條道路由于交通事故，施工等各種原因通暢和擁塞程度隨時(shí)發(fā)生變化，該算法只要有任何一條能到達(dá)終點(diǎn)的路徑都可以被搜索到，健壯性非常好。

圖1所示是一個(gè)交通路線示意圖。從源點(diǎn)S到目的地D，中間有若干個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)之間邊表示路徑，路徑上的權(quán)值表示經(jīng)過(guò)該路徑所需的時(shí)間，權(quán)值越大，所需時(shí)間越長(zhǎng)。要找出源點(diǎn)S到目的D的最短路徑也就是找出權(quán)值之和最小的路徑，根據(jù)本文的算法，最短路徑的求解過(guò)程為：

圖1 交通路線示意圖

從源點(diǎn)S出發(fā)，與S直連的節(jié)點(diǎn)有三個(gè)：V1，V2，V3，根據(jù)洪泛的思想，S會(huì)向所有與之相連的節(jié)點(diǎn)發(fā)送信息，于是，三個(gè)節(jié)點(diǎn)V1、V2和V3都會(huì)收到來(lái)自源點(diǎn)S的信息，于是這三個(gè)節(jié)點(diǎn)都會(huì)記錄來(lái)自S的信息：

S->V1（S， V1， （S， V1）， 10）；

S->V2（S， V2， （S， V2）， 5）；

S->V3（S， V3， （S， V3）， 8）

同時(shí)，在洪泛的方式下，V1會(huì)把來(lái)自S的信息發(fā)送給V2，V2會(huì)把來(lái)自S的信息發(fā)送給V1和V3，V3會(huì)把來(lái)自S的信息發(fā)送給V2，于是V1、V2、V3又會(huì)記錄以下信息：

S->V1（S， V1， （S， V2，V1）， 7）；

S->V1（S， V1， （S， V3， V2， V1）， 15）；

S->V2（S， V2， （S， V1， V2）， 12）；

S->V2（S， V2， （S， V3， V2）， 12）；

S->V3（S， V3， （S， V2， V3）， 9）；

S->V3（S， V3， （S， V1， V2， V3）， 16）

根據(jù)權(quán)值比較，選擇最短的路徑即權(quán)值最小的路徑為：

S->V1（S， V1， （S， V2， V1）， 7）；

S->V2（S， V2， （S， V2）， 5）；

S->V3（S， V3， （S， V3）， 8）

同理，與V1直連的有V4，與V2直連的有V5，與V3直連的有V6，所以V4會(huì)收到來(lái)自V1的信息，V5會(huì)收到來(lái)自V2的信息，V6會(huì)收到來(lái)自V3的信息，于是從源點(diǎn)S出發(fā)到V4、V5、V6的路徑信息為：

S->V4（S， V4， （S， V2， V1， V4）， 13）

S->V5（S， V5， （S， V2， V5）， 14）

S->V6（S， V6， （S， V3， V6）， 16）

在它們各自收到信息之后，由于洪泛的原理也會(huì)轉(zhuǎn)發(fā)給其它相鄰的節(jié)點(diǎn)，于是V4、V5、V6的其它路徑信息為：

S->V4（S， V4， （S， V2， V5， V4）， 16）；

S->V4（S， V4， （S， V3， V6， V5， V4）， 23）；

S->V5（S， V5， （S， V2， V1， V4，V5）， 15）；

S->V5（S， V5， （S， V3， V6， V5）， 21）；

S->V6（S， V6， （S， V2， V1， V4， V5， V6）， 20）；

S->V6（S， V6， （S， V2， V5， V6）， 19）

根據(jù)權(quán)值比較，選擇最短的路徑即權(quán)值最小的路徑為：

S -> V4 （S， V4， （S， V2， V1， V4）， 13）；

S -> V5 （S， V5， （S， V2， V5）， 14）；

S-> V6（S， V6， （S， V3， V6， 16）

最后，V4、V5、V6都直連到目的地D，所以到D的路徑分別為：

S ->D （S， D， （S， V2， V1， V4， D）， 19）；

S-> D （S， D， （S， V2， V5， D）， 20）；

S -> D（S， D， （S， V3， V6， D）， 20）

根據(jù)權(quán)值比較，選擇最短的路徑即權(quán)值最小的路徑為：

S -> D （ S， D， （S， V2， V1， V4， D）， 19）

這條路徑即為從源到目的最短路徑，其實(shí)在計(jì)算的時(shí)候有三條可達(dá)路徑，其中一條為最短路徑，其余兩條可以作為備用路徑，一旦其中一條路徑出現(xiàn)問(wèn)題時(shí)，可以快速切換到另外一條備用路徑。例如當(dāng)?shù)竭_(dá)V2點(diǎn)時(shí)，發(fā)現(xiàn)V1到V4的路徑發(fā)現(xiàn)了擁塞，那么此時(shí)可以立即切換到另外一條路徑：S -> D （S， D， （S， V2， V5， D）， 20）。

1.3 時(shí)間復(fù)雜度分析

在該算法中，每個(gè)節(jié)點(diǎn)會(huì)收到來(lái)自所有入度的數(shù)據(jù)，并根據(jù)權(quán)值的大小進(jìn)行比較，選擇權(quán)值最小的那條路徑信息向所有的出度進(jìn)行轉(zhuǎn)發(fā)，所以該算法處理的時(shí)間復(fù)雜度只跟邊的數(shù)量有關(guān)，所以時(shí)間復(fù)雜度為O（n），n為邊的數(shù)量。

2 實(shí)例分析

現(xiàn)以前面算法描述中的圖1為例來(lái)分析該算法的工作過(guò)程和特點(diǎn)。

首先起點(diǎn)S向直接的節(jié)點(diǎn)V1、V2、V3發(fā)送洪泛信息，具體如圖2所示。

圖2 從源點(diǎn)S洪泛到直連節(jié)點(diǎn)

V1、V2、V3收到S的信息之后，也都會(huì)向與之直連的節(jié)點(diǎn)洪泛，如圖3所示，節(jié)點(diǎn)V1向所有直連的除收到信息之外的節(jié)點(diǎn)（即除源節(jié)點(diǎn)S之外）洪泛信息。

其它的節(jié)點(diǎn)V2、V3做同樣的操作。最后從源S到目的地D的最短路徑如圖4所示。

圖3 節(jié)點(diǎn)V1向其它節(jié)點(diǎn)洪泛信息

圖4 S到D的最短路徑

該算法在計(jì)算時(shí)，可以獲得三條可達(dá)路徑，其中一條為最短路徑，其余兩條為次優(yōu)路徑，可作為備用路徑，一旦其中一條路徑出現(xiàn)問(wèn)題時(shí)，可以快速切換到另外一條備用路徑。例如當(dāng)?shù)竭_(dá)V2節(jié)點(diǎn)時(shí)，發(fā)現(xiàn)V1到V4的路徑發(fā)生了擁塞，那么，此時(shí)可以立即切換到另外一條路徑，如圖5所示。

圖5 切換到備用路徑

3 結(jié) 語(yǔ)

本文提出了一種基于洪泛思想的最短路徑算法， 利用洪泛的特點(diǎn)，在整個(gè)路網(wǎng)中搜索到達(dá)目的地的最短路徑，在搜索最短路徑的同時(shí)，還可以搜索到若干條次優(yōu)路徑，在最優(yōu)路徑出現(xiàn)問(wèn)題時(shí)可以快速切換到次優(yōu)路徑，以適應(yīng)智能交通系統(tǒng)中時(shí)刻變化的道路通暢情況。該算法的時(shí)間復(fù)雜度為O（n），跟經(jīng)典的Dijkstra和Floyd算法比較，大大降低了搜索范圍、提高了計(jì)算效率， 而且在保證最短路徑求解的同時(shí)，還能求出備用路徑， 非常適用于動(dòng)態(tài)變化的智能交通系統(tǒng)的最短路徑的求解問(wèn)題。

參考文獻(xiàn)

[1]丁革媛，李振江，鄭宏云. 智慧城市的應(yīng)用體系架構(gòu)研究[J].微型機(jī)與應(yīng)用，2013，22（24）：1-3.

[2] 王元彪.智能交通系統(tǒng)中 Dijkstra 算法的高效實(shí)現(xiàn)[J].計(jì)算機(jī)工程，2007，33（ 6）：256-261.

[3] Dijkstra E W. A note on two problems in connection with graphs[J].Numerische Mathematik， 1959（1）： 269- 271.

[4] Floyd R N. Algorithm 97 shortest path [J]. Comm ACM， 1962， 5 （6）：345.

[5] Zhan F B. Three fastest shortest path algorithms on real road networks： data structures and procedures [J].JGIDA， 1998， 1（1）： 69-82.