一種限制搜索區域的多比例尺最優路徑規劃算法

摘要：針對現有大區域范圍路徑規劃算法存在的一些問題，提出一種限制搜索區域的多比例尺最優路徑規劃算法。該算法在進行路徑規劃時，一方面根據路網的多比例尺信息對路網進行分級，另一方面對搜索區域進行合理限制。測試實驗表明此算法可以提高路徑規劃的效率。

關鍵詞：限制搜索區域； 多比例尺； 最優路徑規劃算法； Dijkstra算法

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

文章編號：1001-3695(2007)12-0066-02

為了提高大區域路網路徑規劃的效率，國內外很多專家學者做了大量的研究工作，提出了一些新的算法。這些算法大多數采用路網分級技術或分解技術來減少大規模路網的存儲需求和計算的開銷，如文獻[1~3]中提出的算法。然而現有的路網分級分解技術存在著一些問題，主要表現在^[4]:路網分解沒有統一的標準；路網分級處理時，大多按照道路的屬性，如主干道、次干道等，對路網進行分級，要求屬性信息非常完整，否則無法分級；若提取出的每一級路網不連通時將無法處理；在涉及到幾百甚至幾千幅地圖時，從每幅地圖中提取主干道、次干道路網再拼接成多級路網，其工作量巨大，可行性不強；等等。針對以上問題，本文提出一種限制搜索區域的多比例尺最優路徑規劃算法（multiscale optimal route planning algorithm within restricted searching area，MORPARSA）。

1MORPARSA

1．1路網的空間分布特性

與普通的平面網絡圖相比，描述實際城市路網的拓撲圖通常具有以下特點^[5，6]：每個節點相連的路段數一般不超過5，多為2、3或4；網絡結構相對比較規則(特別是經過規劃的現代化都市)；網絡中有表示供車輛調頭的專門換向節點，而且一般距當前路口500 m左右。

1．2區域限制的思想

Dijkstra算法求解的是某個源點到其余各節點的最短路徑，它按節點距起始點距離遞增的順序產生最短路徑，因此該算法在最短路徑的搜索過程中具有很大的盲目性，隨時都準備向四面八方展開^[5]。該算法搜索的區域是整個路網平面，時間復雜度為O(n2)。其中n為路網中的節點數。

由于實際城市路網結構相對比較規則(特別是經過規劃的現代化都市，如西安市)^[5~7]中，最短路徑一般都會落入以起始點S和目標點D的連線為對角線的矩形區域中，如圖1中的小矩形。應該說明的是，在靠近兩節點的附近，有時可能會出現短距離的反向路徑(指在線段SD的兩端點外，沿SD或DS延長線方向的路徑，反映在實際系統中，通常代表車輛為轉入合適車道行駛所走過的路徑)^[5]，此時最短路徑顯然不會落在以S和D的連線為對角線的矩形區域中，因此將以S和D的連線為對角線的矩形四邊向外各擴展500 m，形成一個更大的矩形作為限制區域，如圖1所示。

如果路網中的節點在整個路網平面內均勻分布(即節點數與其所占區域的面積成正比，即使局部節點的分布不均勻)，那么搜索過程中實際所需訪問的節點數就可用搜索掃過區域的面積C表示，進而搜索的時間復雜度可表示為O(C2)^[5]。假設圖1中整個路網平面的面積為C1，大矩形的面積為C2。由于C2＜＜C1，合理限制搜索區域理論上可以提高路徑規劃的效率。

1．3多比例尺路網數據模型

人們習慣于用比例尺的概念來描述地圖對現實世界不同詳盡程度的表達，比例尺越大，對現實世界的描述就越詳細，對空間對象幾何形的描述也越詳細?？梢杂帽壤邅砻枋霾煌匾潭鹊牡缆罚鐖D2所示。

我國基礎地理信息的比例尺系列包括1∶100萬、1∶50萬、1∶25萬、1∶10萬、1∶5萬、1∶1萬等，多比例尺自然就起到了分級的作用。

多比例尺信息的這種分級特性與道路的屬性信息相關，主要道路存在于小比例尺地圖中，次要道路存在于大比例尺地圖中，而且大比例尺地圖中包含了小比例尺地圖中的道路，顯示了更為詳細的道路信息。因此，可以采用多比例尺數據構建多級路網結構處理大區域的路徑搜索問題^[4，8]，如圖3所示。

基于多比例尺數據構建的多級路網模型解決了原有的分級分解算法中存在的一些問題，主要改進的問題如下^[4，8]:根據道路屬性對道路進行分級時，需要作一些處理，很難保證提取的同一級路網是連通的，采用多比例尺數據構建的多級路網，多比例尺本身起到了分級的作用，在每一比例尺下，路網數據具有連通性。現有的分級分解算法一般按照道路的屬性對路網進行分級，因而在道路屬性信息不完整的情況下無法處理；在大區域范圍內，即使屬性信息齊全，提取構建多級路網工作量繁重、不易實施。在全國基本比例尺地形圖庫已經建立的情況下，采用多比例尺數據構建多級路網顯然是可行的。

1．4算法描述

設多級路網一共有W級(W≥1)。

輸入：多比例尺路網數據，起始點S、目標點D為路網中任意指定的兩個節點。

輸出：S和D之間的一條最優路徑。

3結束語

本文提出的MORPARSA可以提高路徑規劃的效率。多級路網中，低級網絡一般為主要干道，符合駕駛者首先選擇行駛在主干道的愿望，避開了交通不方便的次要道路，合理性較高。

參考文獻：

[1]彭飛，柳重堪，張其善.車輛定位與導航系統中的快速路徑規劃算法[J].北京航空航天大學學報，2002，28(1):70-73.

[2]陳則王，袁信.基于分層分解的一種實時車輛路徑規劃算法[J].南京航空航天大學學報，2003，35(2):193197.

[3]JAGADEESH G R， SRIKANTHAN T. Heuristic techniques for accelerating hierarchical routing on road networks[J]. IEEE Trans on Intelligent Transportation Systems， 2002，3(4):301-309.

[4]陳玉敏，龔健雅，史文中.多級道路網的最優路徑算法研究[J].武漢大學學報，2006，31(1):70-73.

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

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

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

[8]王晏民，李德仁，龔健雅.一種多比例尺GIS方案及其數據模型[J].武漢大學學報，2003，28(4):458-462.

[9]Oracle Corporation. Oracle spatial user’s guide and reference release 9.0.1[EB/OL].[2006-09].http://www.oracle.com/technology/documentation/spatial.html.

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