首頁 > 文章中心 > 正文

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

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

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

      摘要:針對現(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)一的標(biāo)準(zhǔn);路網(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)的拓?fù)鋱D通常具有以下特點[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é)點,而且一般距當(dāng)前路口500m左右。

      1.2區(qū)域限制的思想

      Dijkstra算法求解的是某個源點到其余各節(jié)點的最短路徑,它按節(jié)點距起始點距離遞增的順序產(chǎn)生最短路徑,因此該算法在最短路徑的搜索過程中具有很大的盲目性,隨時都準(zhǔ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和目標(biāo)點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)實世界的描述就越詳細(xì),對空間對象幾何形的描述也越詳細(xì)。可以用比例尺來描述不同重要程度的道路,如圖2所示。

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

      多比例尺信息的這種分級特性與道路的屬性信息相關(guān),主要道路存在于小比例尺地圖中,次要道路存在于大比例尺地圖中,而且大比例尺地圖中包含了小比例尺地圖中的道路,顯示了更為詳細(xì)的道路信息。因此,可以采用多比例尺數(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、目標(biāo)點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]嚴(yán)寒冰,劉迎春.基于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].

      久久精品国产亚洲av高清漫画| 久久精品国产亚洲AV电影网| 亚洲色欲啪啪久久WWW综合网| 亚洲宅男永久在线| 亚洲精品国产成人片| 亚洲色一色噜一噜噜噜| 亚洲国产成人AV网站| 亚洲精品成a人在线观看夫| 亚洲日韩精品国产一区二区三区 | 亚洲精品二区国产综合野狼| 亚洲性在线看高清h片| 亚洲国产一区二区视频网站| 亚洲国产成人久久综合区| 亚洲国产综合精品中文字幕 | 亚洲综合丁香婷婷六月香| 亚洲一区无码中文字幕乱码| 亚洲专区一路线二| 亚洲国产精品综合久久20| 亚洲 日韩经典 中文字幕| 亚洲人成无码网站在线观看| 亚洲乱妇熟女爽到高潮的片| 337P日本欧洲亚洲大胆艺术图| 怡红院亚洲红怡院在线观看| 亚洲福利中文字幕在线网址| 亚洲人成色7777在线观看不卡| ZZIJZZIJ亚洲日本少妇JIZJIZ| 国产自偷亚洲精品页65页| 亚洲精品无码不卡在线播HE| 亚洲大尺度无码无码专区| 亚洲国产精品不卡在线电影| 亚洲综合久久1区2区3区| 亚洲人成人77777网站不卡 | 亚洲一区二区女搞男| 亚洲VA中文字幕不卡无码| 久久久久亚洲AV成人片| 亚洲中文字幕在线无码一区二区| 亚洲熟妇无码一区二区三区导航 | 亚洲人成在线影院| 亚洲国产午夜电影在线入口| 国产亚洲精品成人AA片| 国产成人高清亚洲一区久久|