一種動態限制搜索區域的最短路徑規劃算法

摘要：提出一種動態限制搜索區域的最短路徑規劃算法，它是根據實際道路網絡的空間分布特性，動態限制搜索區域，以降低算法的搜索規模，降低算法的時間復雜度和空間復雜度，提高算法的運行效率。實驗證明，對于實際城市道路網絡結構相對比較規則的最短路徑規劃，此算法極大地提高了規劃的效率。

關鍵詞：動態限制搜索區域； 最短路徑規劃算法； Dijkstra算法； 道路網絡

中圖分類號：TP301．6文獻標志碼：A

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

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

1算法原理

1．1道路網絡的拓撲結構

最短路徑算法設計與實現的基礎是具有拓撲結構的道路網絡[4]。在計算機中，具有拓撲結構的城市道路網絡由節點、邊及相應的拓撲關系構成。其中節點是道路的交叉點、端點，邊是兩節點間的一段道路。與普通的平面網絡圖相比，描述實際城市道路網絡的拓撲圖通常具有網絡結構相對比較規則(特別是經過規劃的現代大都市)的特點[2，5]。反映在實際道路網絡中，相對比較規則指的是政府職能部門在進行城市總體規劃時力圖使道路布局整齊，以提高行車質量和安全性[6]。

描述實際城市道路網絡的拓撲圖通常用鄰接矩陣、鄰接表、十字鏈表、鄰接多重表等來表示。這幾種圖的存儲結構比較如表1[7]所示。

1．2經典Dijkstra算法

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

1．3橢圓限制搜索區域算法

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

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

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

1．4矩形限制搜索區域算法

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

1．5動態限制搜索區域的最短路徑規劃算法

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

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

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

動態限制搜索區域的最短路徑規劃算法描述如下：

輸入：采用鄰接表數據結構存儲的矢量化城市道路網絡，起始點S、目標點G為道路網絡中任意給定的兩個節點。

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

（1）初始化，主要完成路網數據加載及程序運行環境的設置。

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

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

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

1．6幾種限制搜索區域的最短路徑規劃算法的比較

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

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

2算法效率分析

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

由表2可以看出，由于縮小了搜索的規模，動態限制搜索區域的最短路徑規劃算法在從數據庫中提取空間數據并構造鄰接表所需時間和在鄰接表基礎上搜索最短路徑所需時間兩方面減少了所需的代價，從而縮短了算法總的執行時間，極大地提高了算法執行的效率。

3結束語

本文提出了一種動態限制搜索區域的最短路徑規劃算法。試圖根據實際道路網絡的空間分布特性，設計針對實際路網的特殊路徑規劃算法，動態限制搜索區域以降低算法的搜索規模，降低了算法的時間復雜度和空間復雜度，提高了算法的運行效率。

參考文獻：

[1]趙亦林.車輛定位與導航系統[M].北京:電子工業出版社，1999:110－112.

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

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

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

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

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

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

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

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

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