限制搜索區(qū)域的路徑規(guī)劃算法透析

前言：本站為你精心整理了限制搜索區(qū)域的路徑規(guī)劃算法透析范文，希望能為你的創(chuàng)作提供參考價值，我們的客服老師可以幫助你提供個性化的參考范文，歡迎咨詢。

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

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

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

1MORPARSA

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

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

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

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

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

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

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

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

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

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

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

1．4算法描述

設(shè)多級路網(wǎng)一共有W級(W≥1)。

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

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

3結(jié)束語

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

參考文獻：

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

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

[3]JAGADEESHGR,SRIKANTHANT.Heuristictechniquesforacceleratinghierarchicalroutingonroadnetworks[J].IEEETransonIntelligentTransportationSystems,2002,3(4):301-309.

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

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

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

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

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

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