基于物聯(lián)網(wǎng)的智能交通系統(tǒng)車輛路徑規(guī)劃算法優(yōu)化研究

摘要：本文提出了適用于智能交通系統(tǒng)的基于雙向搜索的改進(jìn)算法。典型的最短路徑算法被認(rèn)為是Dijkstra算法，其時(shí)間復(fù)雜度是O（n2）。但一個(gè)城市的路網(wǎng)地圖有很多節(jié)點(diǎn)，該算法的時(shí)間復(fù)雜度高和解決速度慢。為了改變這種情況，我們從算法的設(shè)計(jì)方面進(jìn)行了討論，提出了改進(jìn)的雙向搜索算法。實(shí)踐證明，改進(jìn)后的算法能夠提高了搜索速度，適用于智能交通系統(tǒng)。

關(guān)鍵詞：物聯(lián)網(wǎng)；智能交通；路徑規(guī)劃；雙向搜索算法

中圖分類號(hào)：U492.22 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9599 （2012） 17-0000-02

1 引言

智能交通系統(tǒng)的核心即動(dòng)態(tài)車輛的路徑規(guī)劃問題，如何能提高路徑規(guī)劃算法的速度是保證整個(gè)智能交通更好更快發(fā)展的前提。目前具有代表性的最短路徑算法是Dijkstra算法，其時(shí)間復(fù)雜度為O（n2）。但因Dijstra 算法是一個(gè)NP完備算法，面對城市交通路網(wǎng)的眾多結(jié)點(diǎn)，此算法的時(shí)間復(fù)雜度高，很難滿足導(dǎo)航系統(tǒng)中的實(shí)時(shí)性要求。本文從算法設(shè)計(jì)方面對現(xiàn)有的雙向搜索算法進(jìn)行優(yōu)化，實(shí)驗(yàn)證明，能夠達(dá)到提高算法效率的目的，使其適用于智能交通中的車輛導(dǎo)航系統(tǒng)。

2 算法的優(yōu)化原理

所謂雙向搜索指的是搜索沿兩個(gè)方向同時(shí)進(jìn)行，正向搜索：從初始結(jié)點(diǎn)向目標(biāo)結(jié)點(diǎn)方向搜索；逆向搜索：從目標(biāo)結(jié)點(diǎn)向初始結(jié)點(diǎn)方向搜索；每個(gè)新結(jié)點(diǎn)生成后，不僅要與本隊(duì)列中的每個(gè)結(jié)點(diǎn)判重，還要和對方隊(duì)列中的節(jié)點(diǎn)判重，如果有相同結(jié)點(diǎn)，即發(fā)生雙向搜索相遇事件，搜索完成，搜索步數(shù)等于兩個(gè)方向搜索步數(shù)之和，生成的搜索樹是菱形的，極大的減少了搜索結(jié)點(diǎn)的數(shù)量，提高了搜索效率。實(shí)驗(yàn)表明，和單向搜索展開的結(jié)點(diǎn)數(shù)相比，雙向搜索展開的結(jié)點(diǎn)數(shù)至少可以減少1/2，搜索效率明顯提高。

此算法的最優(yōu)狀態(tài)是正向和逆向的搜索在圖中相遇，最不利的情況是正向搜索和逆向搜索沒有相遇的結(jié)點(diǎn)，這樣反而使算法的搜索時(shí)間增加了一倍。因此適當(dāng)?shù)姆艑捤阉鹘K止條件才能真正縮短搜索時(shí)間。我們的優(yōu)化就是在不增加算法的時(shí)間復(fù)雜度基礎(chǔ)上，解決在雙向搜索中結(jié)點(diǎn)沒有相遇的情況。

算法的優(yōu)化

在搜索過程中，將每次搜索到的新結(jié)點(diǎn)向源結(jié)點(diǎn)和目標(biāo)結(jié)點(diǎn)的連線做投影，計(jì)算從正向搜索到的新結(jié)點(diǎn)的投影到源結(jié)點(diǎn)的距離和從逆向搜索到的新結(jié)點(diǎn)的投影到目標(biāo)結(jié)點(diǎn)的距離，并計(jì)算這兩個(gè)距離的和，如果距離之和比源結(jié)點(diǎn)和目標(biāo)結(jié)點(diǎn)的連線的直線距離長，我們認(rèn)為雙向搜索不會(huì)有重合點(diǎn)，立刻停止某一方向的路徑搜索，繼續(xù)另一方向的結(jié)點(diǎn)搜索，雙向搜索中選擇某個(gè)方向繼續(xù)進(jìn)行搜索或某個(gè)方向停止搜索，主要取決于哪個(gè)方向的結(jié)點(diǎn)個(gè)數(shù)較少，就向那個(gè)方向進(jìn)行擴(kuò)展。眾所周知，“兩點(diǎn)之間直線距離最短”，如果我們所要尋找的結(jié)點(diǎn)恰好在同一條邊上，這條邊就是我們要找的最短路徑，否則，和兩點(diǎn)間連線的夾角最小的邊是最短路徑的可能性較大。如圖1所示，在城市路網(wǎng)中搜索兩點(diǎn)A和E之間的最短路徑的優(yōu)化后算法的步驟如下：

（1）結(jié)點(diǎn)A為出發(fā)地，結(jié)點(diǎn)E為目的地。在結(jié)點(diǎn)A和結(jié)點(diǎn)E之間，建立一條連線AE，若AE之間存在一條邊和AE連線重合，則這條邊就是我們所求的最短路徑。

（2）若不滿足上述條件，則我們從出發(fā)點(diǎn)A和目的地E同時(shí)向中部搜索與AE這條直線夾角最小的邊，在搜索過程中，每次都選擇結(jié)點(diǎn)個(gè)數(shù)較少的那個(gè)方向先擴(kuò)展。

（3）重復(fù)步驟（2）直到兩個(gè)方向的搜索能匯合于同一結(jié)點(diǎn)或同一條邊。把兩個(gè)方向搜索過的結(jié)點(diǎn)聚集，就能得出從A到E的完整最短路徑。

（4）在搜索過程中，將雙向搜索到的新結(jié)點(diǎn)向AE直線做投影，計(jì)算從A方向搜索到的結(jié)點(diǎn)的投影到A的距離和從E方向搜索到的結(jié)點(diǎn)的投影到E的距離，并計(jì)算這兩個(gè)距離之和，如果距離之和比AE直線距離長，我們就認(rèn)為雙向搜索不會(huì)有重合點(diǎn)，立刻停止某一方向的路徑搜索，繼續(xù)向結(jié)點(diǎn)個(gè)數(shù)較少的那個(gè)方向進(jìn)行擴(kuò)展，搜索結(jié)果為單向擴(kuò)展的結(jié)點(diǎn)為所求的最短路徑。

3 路徑規(guī)劃算法設(shè)計(jì)

3.1 算法的實(shí)現(xiàn)。設(shè)置兩個(gè)隊(duì)列c：array[0..1，1..maxn] of jid，分別表示正向搜索和逆向搜索的擴(kuò)展隊(duì)列；兩個(gè)頭指針head：array[0..1] of integer 分別表示正向搜索和逆向搜索中當(dāng)前將擴(kuò)展結(jié)點(diǎn)的頭指針；設(shè)置兩個(gè)尾指針tail：array[0..1] of integer 分別表示正向搜索和逆向搜索的尾指針。

主程序：選擇節(jié)點(diǎn)數(shù)較少且隊(duì)列未空、未滿的方向先擴(kuò)展

if （tail[0]<=tail[1]） and not（（head[0]>=tail[0]）or（tail[0]>=maxn）） then expand（0）；

if （tail[1]<=tail[0]） and not（（head[1]>=tail[1]）or（tail[1]>=maxn）） then expand（1）；

如果一方搜索終止，繼續(xù)另一方的搜索，直到兩個(gè)方向都終止

if not（（head[0]>=tail[0]）or（tail[0]>=maxn）） then expand（0）；

if not（（head[1]>=tail[1]）or（tail[1]>=maxn）） then expand（1）；

Until （（head[0]>=tail[0]）or（tail[0]>=maxn）） And （（head[1]>=tail[1]）or（tail[1]>=maxn））

通過實(shí)驗(yàn)表明，雙向搜索和單向搜索展開的結(jié)點(diǎn)數(shù)相比至少減少了1/2，在本項(xiàng)目中采用的鄰接表存儲(chǔ)并采用雙向搜索算法，能大大減少存儲(chǔ)空間并有效降低算法的時(shí)間復(fù)雜度。

3.2 實(shí)驗(yàn)及結(jié)果分析。為了驗(yàn)證算法的可行性，我們分別用經(jīng)典的Dijstra算法和優(yōu)化后的雙向搜索算法對長春市區(qū)的部分街道進(jìn)行最短路徑的搜索。在搜索過程中，我們主要搜索的是長春市的主干道，忽略了一些小的胡同。如下部分長春市地圖中共存儲(chǔ)189個(gè)結(jié)點(diǎn)和567條弧。對同一起點(diǎn)和終點(diǎn)完成最短路徑搜索，兩種算法搜索的結(jié)點(diǎn)個(gè)數(shù)和花費(fèi)的時(shí)間如表1所示。

4 結(jié)論

本文的路徑規(guī)劃算法采取鄰接表的存儲(chǔ)方式，并在此拓?fù)浣Y(jié)構(gòu)的基礎(chǔ)上對雙向搜索法進(jìn)行優(yōu)化，對雙向搜索算法中雙向結(jié)點(diǎn)搜索不相遇而導(dǎo)致的時(shí)間復(fù)雜度增加問題，通過停止一方搜索給出了解決的辦法，使此算法適用于智能交通中對路徑規(guī)劃速度的要求，并給出了在此拓?fù)浣Y(jié)構(gòu)中交通管制帶來的單向行駛問題在本算法中的解決方式。大部分的雙向搜索都能在圖中相遇，雖然個(gè)別沒有在圖中相遇的，此算法也能得到相應(yīng)的解，通過實(shí)驗(yàn)表明此算法雖然不能每次都得到一個(gè)最優(yōu)解，但最終的理論研究和案例分析的結(jié)果表明改進(jìn)后的算法能夠克服以往算法的不足，符合智能交通中路徑規(guī)劃的快速性要求，在實(shí)際應(yīng)用中是可行的。

參考文獻(xiàn)：

[1]趙亦林.車輛定位與導(dǎo)航系統(tǒng)[M].譚國真.北京：電子工業(yè)出版社，1999：110-132.

[2]Lu Ruqian.Artificial intelligence[M].Beijing：Science Press，1989

[基金項(xiàng)目]吉林省教育廳科研計(jì)劃項(xiàng)目（吉教科[2012] 380）