摘要：針對(duì)現(xiàn)有大區(qū)域范圍路徑規(guī)劃算法存在的一些問題，提出一種限制搜索區(qū)域的多比例尺最優(yōu)路徑規(guī)劃算法。該算法在進(jìn)行路徑規(guī)劃時(shí)，一方面根據(jù)路網(wǎng)的多比例尺信息對(duì)路網(wǎng)進(jìn)行分級(jí)，另一方面對(duì)搜索區(qū)域進(jìn)行合理限制。測(cè)試實(shí)驗(yàn)表明此算法可以提高路徑規(guī)劃的效率。

關(guān)鍵詞：限制搜索區(qū)域；多比例尺；最優(yōu)路徑規(guī)劃算法；Dijkstra算法

為了提高大區(qū)域路網(wǎng)路徑規(guī)劃的效率,國內(nèi)外很多專家學(xué)者做了大量的研究工作，提出了一些新的算法。這些算法大多數(shù)采用路網(wǎng)分級(jí)技術(shù)或分解技術(shù)來減少大規(guī)模路網(wǎng)的存儲(chǔ)需求和計(jì)算的開銷，如文獻(xiàn)[1~3]中提出的算法。然而現(xiàn)有的路網(wǎng)分級(jí)分解技術(shù)存在著一些問題,主要表現(xiàn)在[4]:路網(wǎng)分解沒有統(tǒng)一的標(biāo)準(zhǔn)；路網(wǎng)分級(jí)處理時(shí),大多按照道路的屬性,如主干道、次干道等,對(duì)路網(wǎng)進(jìn)行分級(jí),要求屬性信息非常完整,否則無法分級(jí)；若提取出的每一級(jí)路網(wǎng)不連通時(shí)將無法處理；在涉及到幾百甚至幾千幅地圖時(shí),從每幅地圖中提取主干道、次干道路網(wǎng)再拼接成多級(jí)路網(wǎng),其工作量巨大,可行性不強(qiáng)；等等。針對(duì)以上問題，本文提出一種限制搜索區(qū)域的多比例尺最優(yōu)路徑規(guī)劃算法（multi�瞫caleoptimalrouteplanningalgorithmwithinrestrictedsearchingarea，MORPARSA）。

1MORPARSA

1．1路網(wǎng)的空間分布特性

與普通的平面網(wǎng)絡(luò)圖相比,描述實(shí)際城市路網(wǎng)的拓?fù)鋱D通常具有以下特點(diǎn)[5,6]：每個(gè)節(jié)點(diǎn)相連的路段數(shù)一般不超過5，多為2、3或4；網(wǎng)絡(luò)結(jié)構(gòu)相對(duì)比較規(guī)則(特別是經(jīng)過規(guī)劃的現(xiàn)代化都市)；網(wǎng)絡(luò)中有表示供車輛調(diào)頭的專門換向節(jié)點(diǎn),而且一般距當(dāng)前路口500m左右。

1．2區(qū)域限制的思想

Dijkstra算法求解的是某個(gè)源點(diǎn)到其余各節(jié)點(diǎn)的最短路徑，它按節(jié)點(diǎn)距起始點(diǎn)距離遞增的順序產(chǎn)生最短路徑，因此該算法在最短路徑的搜索過程中具有很大的盲目性，隨時(shí)都準(zhǔn)備向四面八方展開[5]。該算法搜索的區(qū)域是整個(gè)路網(wǎng)平面，時(shí)間復(fù)雜度為�玂(n��2)。其中n�珵槁肪W(wǎng)中的節(jié)點(diǎn)數(shù)。

由于實(shí)際城市路網(wǎng)結(jié)構(gòu)相對(duì)比較規(guī)則(特別是經(jīng)過規(guī)劃的現(xiàn)代化都市，如西安市)[5~7]中，��最短路徑一般都會(huì)落入以起始點(diǎn)S和目標(biāo)點(diǎn)D的連線為對(duì)角線的矩形區(qū)域中，如圖1中的小矩形。應(yīng)該說明的是，在靠近兩節(jié)點(diǎn)的附近，有時(shí)可能會(huì)出現(xiàn)短距離的反向路徑(指在線段SD的兩端點(diǎn)外，沿SD或DS延長線方向的路徑，反映在實(shí)際系統(tǒng)中，通常代表車輛為轉(zhuǎn)入合適車道行駛所走過的路徑)[5]，此時(shí)最短路徑顯然不會(huì)落在以S和D的連線為對(duì)角線的矩形區(qū)域中，因此將以S和D的連線為對(duì)角線的矩形四邊向外各擴(kuò)展��500m，形成一個(gè)更大的矩形作為限制區(qū)域，如圖1所示。

如果路網(wǎng)中的節(jié)點(diǎn)在整個(gè)路網(wǎng)平面內(nèi)均勻分布(即節(jié)點(diǎn)數(shù)與其所占區(qū)域的面積成正比，即使局部節(jié)點(diǎn)的分布不均勻)，那么搜索過程中實(shí)際所需訪問的節(jié)點(diǎn)數(shù)就可用搜索掃過區(qū)域的面積�獵表示，進(jìn)而搜索的時(shí)間復(fù)雜度可表示為�㎡(C��2)[5]。假設(shè)圖1中整個(gè)路網(wǎng)平面的面積為C��1，大矩形的面積為C��2。由于�〤��2＜＜C��1,��合理限制搜索區(qū)域理論上可以提高路徑規(guī)劃的效率。

1．3多比例尺路網(wǎng)數(shù)據(jù)模型

人們習(xí)慣于用比例尺的概念來描述地圖對(duì)現(xiàn)實(shí)世界不同詳盡程度的表達(dá)，比例尺越大，對(duì)現(xiàn)實(shí)世界的描述就越詳細(xì)，對(duì)空間對(duì)象幾何形的描述也越詳細(xì)�？梢杂帽壤�尺來描述不同重要程度的道路，如圖2所示。

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

多比例尺信息的這種分級(jí)特性與道路的屬性信息相關(guān)，主要道路存在于小比例尺地圖中，次要道路存在于大比例尺地圖中，而且大比例尺地圖中包含了小比例尺地圖中的道路，顯示了更為詳細(xì)的道路信息。因此，可以采用多比例尺數(shù)據(jù)構(gòu)建多級(jí)路網(wǎng)結(jié)構(gòu)處理大區(qū)域的路徑搜索問題[4,8],如圖3所示。

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

1．4算法描述

設(shè)多級(jí)路網(wǎng)一共有�玏級(jí)(W≥1)。

輸入：多比例尺路網(wǎng)數(shù)據(jù)，起始點(diǎn)S、目標(biāo)點(diǎn)D為路網(wǎng)中任意指定的兩個(gè)節(jié)點(diǎn)。

輸出：S和D之間的一條最優(yōu)路徑。��

3結(jié)束語

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

參考文獻(xiàn)：

[1]彭飛,柳重堪,張其善.車輛定位與導(dǎo)航系統(tǒng)中的快速路徑規(guī)劃算法[J].北京航空航天大學(xué)學(xué)報(bào),2002,28(1):70-73.

[2]陳則王,袁信.基于分層分解的一種實(shí)時(shí)車輛路徑規(guī)劃算法[J].南京航空航天大學(xué)學(xué)報(bào),2003,35(2):193��197.

[3]JAGADEESHGR,SRIKANTHANT.Heuristictechniquesfor�゛c�勃ヽeleratinghierarchicalroutingonroadnetworks[J].IEEETransonIntelligentTransportationSystems,2002,3(4):301-309.

[4]陳玉敏,龔健雅,史文中.多級(jí)道路網(wǎng)的最優(yōu)路徑算法研究[J].武漢大學(xué)學(xué)報(bào),2006,31(1):70-73.

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

[6]嚴(yán)寒冰,劉迎春.基于GIS的城市道路網(wǎng)最短路徑算法探討[J].計(jì)算機(jī)學(xué)報(bào),2000,23(2):210-215.

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

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

[9]OracleCorporation.Oraclespatialuser’sguideandreferencerelease9.0.1[EB/OL].[2006-09].