一種動態(tài)限制搜索區(qū)域的最短路徑規(guī)劃算法

摘要：提出一種動態(tài)限制搜索區(qū)域的最短路徑規(guī)劃算法，它是根據(jù)實際道路網(wǎng)絡(luò)的空間分布特性，動態(tài)限制搜索區(qū)域，以降低算法的搜索規(guī)模，降低算法的時間復(fù)雜度和空間復(fù)雜度，提高算法的運行效率。實驗證明，對于實際城市道路網(wǎng)絡(luò)結(jié)構(gòu)相對比較規(guī)則的最短路徑規(guī)劃，此算法極大地提高了規(guī)劃的效率。

關(guān)鍵詞：動態(tài)限制搜索區(qū)域； 最短路徑規(guī)劃算法； Dijkstra算法； 道路網(wǎng)絡(luò)

中圖分類號：TP301．6文獻標(biāo)志碼：A

文章編號：1001－3695(2007)07－0089－03

路徑規(guī)劃是智能交通系統(tǒng)研究的重要內(nèi)容，是在車輛行駛前或行駛過程中為司機提供從起始點到目標(biāo)點的一條或若干條路線，用來對司機的行車進行導(dǎo)航[1]。它一直是計算機科學(xué)、運籌學(xué)、交通工程學(xué)、地理信息學(xué)等學(xué)科的一個研究熱點[2，3]。路徑規(guī)劃研究方面的專家學(xué)者追求的一個主要目標(biāo)就是路徑規(guī)劃算法的實時性，即對于一個給定了起始點和目標(biāo)點的特定路徑規(guī)劃問題，要在盡可能短的時間內(nèi)給出規(guī)劃后的路徑。利用計算機進行路徑規(guī)劃時需要借助圖論中的理論。經(jīng)典的圖論與不斷發(fā)展完善的計算機數(shù)據(jù)結(jié)構(gòu)及算法的有效結(jié)合使得新的最短路徑算法不斷涌現(xiàn)。由于這些算法主要誕生于計算機科學(xué)及運籌學(xué)領(lǐng)域，大多數(shù)算法均存在一個問題：在設(shè)計過程中只考慮了抽象網(wǎng)絡(luò)的拓?fù)涮匦裕η笸ㄟ^各種新型的計算機數(shù)據(jù)結(jié)構(gòu)和運籌學(xué)方法，從理論上減少算法的時間復(fù)雜度，而忽略了具體網(wǎng)絡(luò)可能具有的空間分布特性。

1算法原理

1．1道路網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)

最短路徑算法設(shè)計與實現(xiàn)的基礎(chǔ)是具有拓?fù)浣Y(jié)構(gòu)的道路網(wǎng)絡(luò)[4]。在計算機中，具有拓?fù)浣Y(jié)構(gòu)的城市道路網(wǎng)絡(luò)由節(jié)點、邊及相應(yīng)的拓?fù)潢P(guān)系構(gòu)成。其中節(jié)點是道路的交叉點、端點，邊是兩節(jié)點間的一段道路。與普通的平面網(wǎng)絡(luò)圖相比，描述實際城市道路網(wǎng)絡(luò)的拓?fù)鋱D通常具有網(wǎng)絡(luò)結(jié)構(gòu)相對比較規(guī)則(特別是經(jīng)過規(guī)劃的現(xiàn)代大都市)的特點[2，5]。反映在實際道路網(wǎng)絡(luò)中，相對比較規(guī)則指的是政府職能部門在進行城市總體規(guī)劃時力圖使道路布局整齊，以提高行車質(zhì)量和安全性[6]。

描述實際城市道路網(wǎng)絡(luò)的拓?fù)鋱D通常用鄰接矩陣、鄰接表、十字鏈表、鄰接多重表等來表示。這幾種圖的存儲結(jié)構(gòu)比較如表1[7]所示。

1．2經(jīng)典Dijkstra算法

荷蘭計算機科學(xué)家Dijkstra于1959年提出了經(jīng)典Dijkstra算法。其基本思想是按節(jié)點距起始點距離遞增順序來產(chǎn)生最短路徑，因此該算法在最短路徑的搜索過程中具有很大的盲目性，隨時都準(zhǔn)備向其四面八方展開。這樣，最終掃過的搜索區(qū)域基本上是以起始點為原點、起始點與目標(biāo)點的歐氏距離為半徑的一個圓，如圖1中的圓[2]。

1．3橢圓限制搜索區(qū)域算法

橢圓限制搜索區(qū)域算法最早見于文獻[8]。其基本思想如下：設(shè)網(wǎng)絡(luò)中的一個點N到起始點S和目標(biāo)點G的直線距離分別為|SN|、|GN|，限制條件可以寫成|SN|+|GN|≤M。顯然，這正好形成了一個以S和G為焦點、以M為長軸的橢圓，如圖1中的橢圓。在進行路徑規(guī)劃時，算法只考慮位于橢圓之內(nèi)的節(jié)點，對位于橢圓之外的節(jié)點不予考慮。在橢圓限制搜索區(qū)域算法中，關(guān)鍵是求解合適的橢圓長軸M，以結(jié)合起始點、目標(biāo)點的坐標(biāo)構(gòu)造限制橢圓。通常采用統(tǒng)計分析方法求解橢圓限制算法中的長軸M。其方法是:選定一塊能夠反映城市道路狀況的區(qū)域，從這個區(qū)域中隨機取點，分別放入集合A和B，將它們的笛卡爾乘積記為C，即C=A×B={(a，b)|(a∈A)∧(b∈B)}。所有在C中的元素都可以看成是待求最短路徑的起始點和目標(biāo)點，其直線距離為e，兩點間的最短路徑為p，它們的比值r=p/e構(gòu)成采樣點的集合R。對這個集合進行統(tǒng)計分析就可以得出一個特定的系數(shù)，使得R中總數(shù)為滿足95%置信水平的元素，其值不大于。然后利用這個系數(shù)作為乘系數(shù)，即可以通過起止點之間的距離得出橢圓的長軸長度M=|SG|×[3，9]。以西安市電子地圖為例，從4 525個點中分別隨機各抽取30個點放入集合A、B中；經(jīng)過笛卡爾乘積，C中就含有900對點；分別求取r，并對這900對點求算術(shù)平均值，可以得到≈1．352，則M=|SG|×=1．352×|SG|。

在橢圓限制算法中，一般給出的置信水平為95%，這表明在橢圓內(nèi)找不到全局最短路徑的可能性不大于5%。但即使是剩下的5%不是全局最短路徑，也至少是局部最短路徑，所以一般認(rèn)為這5%是完全可以忽略的[9]。

橢圓限制搜索區(qū)域算法將搜索節(jié)點集限制在橢圓內(nèi)，大幅度縮小了最短路徑算法的搜索規(guī)模。但是這種算法的缺點是在判斷每個新擴展出的節(jié)點是否落在限定的橢圓內(nèi)時需執(zhí)行大量的乘積與開方計算，占用的時間較多。

1．4矩形限制搜索區(qū)域算法

針對橢圓限制搜索區(qū)域算法效率不高的缺點，陸鋒等人提出矩形限制搜索區(qū)域算法。其基本思想為求出限制橢圓的最小包含矩形，矩形的四條邊處于水平或是垂直方向，以此作為限制區(qū)域，減少算法的搜索規(guī)模，如圖1中大的矩形。以橢圓的最小包含矩形作為限制搜索區(qū)域，對新擴展出的節(jié)點，判斷其是否落在限制搜索區(qū)域內(nèi)，只需將其坐標(biāo)與矩形邊界進行比較即可，不需要其他復(fù)雜運算[3]。矩形限制搜索區(qū)域算法既繼承了橢圓搜索算法對搜索規(guī)模合理地進行限制的思想，又避免了算法中大量的乘積與開方計算，具有較橢圓搜索算法更高的效率。

1．5動態(tài)限制搜索區(qū)域的最短路徑規(guī)劃算法

由幾何學(xué)的知識可知，兩點間直線距離最短。受此啟發(fā)，在實際城市道路網(wǎng)中對給定兩點進行路徑規(guī)劃時，從起始點S到目標(biāo)點G的連線方向基本上代表了最短路徑的大致走向。也就是說，最終的最短路徑基本是在兩節(jié)點連線的兩側(cè)，而且通常在其附近，在兩節(jié)點間存在一條邊的情況下，邊本身就是最短路徑[2]。

由于實際城市道路網(wǎng)絡(luò)結(jié)構(gòu)相對比較規(guī)則(特別是經(jīng)過規(guī)劃的現(xiàn)代大都市，如西安市)[2，5]，可以將搜索區(qū)域限制在以起始點S和目標(biāo)點G的連線為對角線的矩形區(qū)域中，如圖1中小的矩形。對于道路網(wǎng)絡(luò)結(jié)構(gòu)相對比較規(guī)則的最短路徑一般都會落入這個小的矩形區(qū)域中。

應(yīng)該注意的是，在靠近兩節(jié)點的附近，有時可能會出現(xiàn)短距離的反向路徑(所謂反向路徑，是指在線段SG的兩端點外，沿SG或GS延長線方向的路徑。反映在實際系統(tǒng)中，通常代表車輛為轉(zhuǎn)入合適車道行駛所走過的路徑)[2]。此時最短路徑顯然不會落在以起始點S和目標(biāo)點G的連線為對角線的矩形區(qū)域中。這時就以橢圓的最小包含矩形作為限制搜索區(qū)域來進行搜索，進而實現(xiàn)動態(tài)限制搜索區(qū)域。

動態(tài)限制搜索區(qū)域的最短路徑規(guī)劃算法描述如下：

輸入：采用鄰接表數(shù)據(jù)結(jié)構(gòu)存儲的矢量化城市道路網(wǎng)絡(luò)，起始點S、目標(biāo)點G為道路網(wǎng)絡(luò)中任意給定的兩個節(jié)點。

輸出：S和G之間的一條最短路徑。

（1）初始化，主要完成路網(wǎng)數(shù)據(jù)加載及程序運行環(huán)境的設(shè)置。

（2）將搜索區(qū)域限制在以S和G的連線為對角線的矩形區(qū)域中，在限制搜索區(qū)域中。根據(jù)給定的S和G調(diào)用Dijkstra算法子程序進行最短路徑計算，若成功，轉(zhuǎn)而執(zhí)行（4）；否則執(zhí)行（3）。

（3）將搜索區(qū)域限制在以S和G為兩個焦點的橢圓的最小包含矩形區(qū)域中，在限制搜索區(qū)域中，根據(jù)給定的S和G，調(diào)用Dijkstra算法子程序進行最短路徑計算。

（4）輸出S和G之間一條距離最短的路徑。

1．6幾種限制搜索區(qū)域的最短路徑規(guī)劃算法的比較

如果路網(wǎng)中的節(jié)點在整個路網(wǎng)平面內(nèi)均勻分布(即節(jié)點數(shù)與其所占區(qū)域的面積成正比，即使局部節(jié)點的分布不均勻，大范圍內(nèi)平均是均勻的)，那么搜索過程中實際所需訪問的節(jié)點數(shù)就可用搜索掃過區(qū)域的面積S表示，進而搜索的時間復(fù)雜度也就可表示為O(S2)[2]。

通常情況下，將搜索區(qū)域限制在以起始點S和目標(biāo)點G的連線為對角線的矩形區(qū)域中，少數(shù)情況下搜索區(qū)域會擴展到限制橢圓的最小包含矩形中，所以對于實際城市道路網(wǎng)絡(luò)結(jié)構(gòu)相對比較規(guī)則的最短路徑規(guī)劃，動態(tài)限制搜索區(qū)域的最短路徑規(guī)劃算法相對于橢圓限制搜索區(qū)域算法，無須進行大量的乘積與開方計算，而且極大地降低了算法的搜索規(guī)模。相對于經(jīng)典Dijkstra算法和矩形限制搜索區(qū)域算法，極大地降低了算法的搜索規(guī)模。因此，動態(tài)限制搜索區(qū)域的最短路徑規(guī)劃算法理論上可以提高最短路徑規(guī)劃的效率。

2算法效率分析

為了驗證動態(tài)限制搜索區(qū)域的最短路徑規(guī)劃算法的效率，用包含4 525個節(jié)點和6 616條道路的西安市地圖數(shù)據(jù)進行實驗。工具采用Visual C++ 8．0，數(shù)據(jù)庫采用Oracle 9i，數(shù)據(jù)庫連接技術(shù)采用OO4O (Oracle Object for OLE)，數(shù)據(jù)結(jié)構(gòu)采用鄰接表；硬件采用Pentium 4 CPU 3．00 GHz、512 MB內(nèi)存。矩形限制算法在絕大多數(shù)情況下優(yōu)于橢圓限制算法[3]，因此只對經(jīng)典Dijkstra算法、矩形限制搜索區(qū)域算法、動態(tài)限制搜索區(qū)域的最短路徑規(guī)劃算法進行比較。由于篇幅所限，只列出部分實驗數(shù)據(jù)，如表2所示。其中：T1表示從數(shù)據(jù)庫中提取空間數(shù)據(jù)并構(gòu)造鄰接表所需時間；T2表示在鄰接表基礎(chǔ)上搜索最短路徑所需時間；T3表示算法總的執(zhí)行時間。

由表2可以看出，由于縮小了搜索的規(guī)模，動態(tài)限制搜索區(qū)域的最短路徑規(guī)劃算法在從數(shù)據(jù)庫中提取空間數(shù)據(jù)并構(gòu)造鄰接表所需時間和在鄰接表基礎(chǔ)上搜索最短路徑所需時間兩方面減少了所需的代價，從而縮短了算法總的執(zhí)行時間，極大地提高了算法執(zhí)行的效率。

3結(jié)束語

本文提出了一種動態(tài)限制搜索區(qū)域的最短路徑規(guī)劃算法。試圖根據(jù)實際道路網(wǎng)絡(luò)的空間分布特性，設(shè)計針對實際路網(wǎng)的特殊路徑規(guī)劃算法，動態(tài)限制搜索區(qū)域以降低算法的搜索規(guī)模，降低了算法的時間復(fù)雜度和空間復(fù)雜度，提高了算法的運行效率。

參考文獻：

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

[2]付夢印，李杰，鄧志紅.限制搜索區(qū)域的距離最短路徑規(guī)劃算法[J].北京理工大學(xué)學(xué)報，2004，24(10):881－884.

[3]陸鋒，盧冬梅，崔偉宏.道路網(wǎng)絡(luò)限制搜索區(qū)域時間最短路徑算法[J].中國圖象圖形學(xué)報，1999，4(10):849－853.

[4]陸鋒.最短路徑算法:分類體系與研究進展[J].測繪學(xué)報，2001，30(3):269－275.

[5]嚴(yán)寒冰，劉迎春.基于GIS的城市道路網(wǎng)最短路徑算法探討[J].計算機學(xué)報，2000，23(2):210－215.

[6]陸錫明，王祥，朱洪.綜合交通規(guī)劃[M].上海:同濟大學(xué)出版社，2003:130－131.

[7]樂陽，龔健雅. Dijkstra最短路徑算法的一種高效率實現(xiàn)[J].武漢測繪科技大學(xué)學(xué)報，1999，24(3):209－212.

[8]NORDBECK S， RYSTEDT B. Computer Cartography Shortest Route Programs[M]. Sweden:The Royal University of Lund，1969.

[9]王曉麗，楊兆升，呂旭濤，等.平行四邊形限制最短路徑算法及其在道路網(wǎng)絡(luò)中的應(yīng)用[J].吉林大學(xué)學(xué)報，2006，36(1):123－127.

注：“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文”