《最优路径规划算法一种限制搜索区域的多比例尺》由会员分享，可在线阅读，更多相关《最优路径规划算法一种限制搜索区域的多比例尺（3页珍藏版）》请在金锄头文库上搜索。
1、1最优路径规划算法一种限制搜索区域的 多比例尺摘要：针对现有大区域范围路径规划算法存在的一些问题，提出一种限制搜索区域的多比例尺最优路径规划算法。该算法在进行路径规划时，一方面根据路网的多比例尺信息对路网进行分级，另一方面对搜索区域进行合理限制。测试实验表明此算法可以提高路径规划的效率。 关键词：限制搜索区域；多比例尺；最优路径规划算法；Dijkstra 算法 为了提高大区域路网路径规划的效率,国内外很多专家学者做了大量的研究工作，提出了一些新的算法。这些算法大多数采用路网分级技术或分解技术来减少大规模路网的存储需求和计算的开销，如文献13中提出的算法。然而现有的路网分级分解技术存在着一些问题
2、,主要表现在4:路网分解没有统一的标准；路网分级处理时,大多按照道路的属性,如主干道、次干道等,对路网进行分级,要求属性信息非常完整,否则无法分级；若提取出的每一级路网不连通时将无法处理；在涉及到几百甚至几千幅地图时,从每幅地图中提取主干道、次干道路网再拼接成多级路网,其工作量巨大,可行性不强；等等。针对以上问题，本文提出一种限制搜索区域的多比例尺最优路径规划算法（multi scaleoptimalrouteplanningalgorithmwithinrestrictedsearchingarea，MORPAR SA）。 1MORPARSA 11 路网的空间分布特性 与普通的平面网络图相比
3、,描述实际城市路网的拓扑图通常具有以下特点5,6：每个节点相连的路段数一般不超过 5，多为 2、3 或 4；网络结构相对比较规则(特2别是经过规划的现代化都市)；网络中有表示供车辆调头的专门换向节点,而且一般距当前路口 500m 左右。 12 区域限制的思想 Dijkstra 算法求解的是某个源点到其余各节点的最短路径，它按节点距起始点距离递增的顺序产生最短路径，因此该算法在最短路径的搜索过程中具有很大的盲目性，随时都准备向四面八方展开5。该算法搜索的区域是整个路网平面，时间复杂度为 O(n 2)。其中 n 为路网中的节点数。 由于实际城市路网结构相对比较规则(特别是经过规划的现代化都市，如西
4、安市)57中， 最短路径一般都会落入以起始点 S 和目标点 D 的连线为对角线的矩形区域中，如图 1 中的小矩形。应该说明的是，在靠近两节点的附近，有时可能会出现短距离的反向路径(指在线段 SD 的两端点外，沿 SD 或 DS 延长线方向的路径，反映在实际系统中，通常代表车辆为转入合适车道行驶所走过的路径)5，此时最短路径显然不会落在以 S 和 D 的连线为对角线的矩形区域中，因此将以 S和 D 的连线为对角线的矩形四边向外各扩展 500m，形成一个更大的矩形作为限制区域，如图 1 所示。 如果路网中的节点在整个路网平面内均匀分布(即节点数与其所占区域的面积成正比，即使局部节点的分布不均匀)，
5、那么搜索过程中实际所需访问的节点数就可用搜索扫过区域的面积 C 表示，进而搜索的时间复杂度可表示为 O(C 2)5。假设图 1 中整个路网平面的面积为 C 1，大矩形的面积为 C 2。由于C 2C 1, 合理限制搜索区域理论上可以提高路径规划的效率。 13 多比例尺路网数据模型 人们习惯于用比例尺的概念来描述地图对现实世界不同详尽程度的表达，比例尺越大，对现实世界的描述就越详细，对空间对象几何形的描述也越详细。可以用比例尺来描述不同重要程度的道路，如图 2 所示。 3我国基础地理信息的比例尺系列包括 1100 万、 150 万、 125 万、 110万、 15 万、 11 万等，多比例尺自然就
6、起到了分级的作用。 多比例尺信息的这种分级特性与道路的属性信息相关，主要道路存在于小比例尺地图中，次要道路存在于大比例尺地图中，而且大比例尺地图中包含了小比例尺地图中的道路，显示了更为详细的道路信息。因此，可以采用多比例尺数据构建多级路网结构处理大区域的路径搜索问题4,8,如图 3 所示。 基于多比例尺数据构建的多级路网模型解决了原有的分级分解算法中存在的一些问题,主要改进的问题如下4,8:根据道路属性对道路进行分级时，需要作一些处理,很难保证提取的同一级路网是连通的，采用多比例尺数据构建的多级路网,多比例尺本身起到了分级的作用，在每一比例尺下,路网数据具有连通性。现有的分级分解算法一般按照道
7、路的属性对路网进行分级,因而在道路属性信息不完整的情况下无法处理；在大区域范围内,即使属性信息齐全,提取构建多级路网工作量繁重、不易实施。在全国基本比例尺地形图库已经建立的情况下,采用多比例尺数据构建多级路网显然是可行的。 14 算法描述 设多级路网一共有 W 级(W1)。 输入：多比例尺路网数据，起始点 S、目标点 D 为路网中任意指定的两个节点。输出：S 和 D 之间的一条最优路径。 3 结束语 本文提出的 MORPARSA 可以提高路径规划的效率。多级路网中,低级网络一般为主要干道,符合驾驶者首先选择行驶在主干道的愿望,避开了交通不方便的次4要道路,合理性较高。 参考文献： 1彭飞,柳重
8、堪,张其善.车辆定位与导航系统中的快速路径规划算法J.北京航空航天大学学报,2002,28(1):70-73. 2陈则王,袁信.基于分层分解的一种实时车辆路径规划算法J.南京航空航天大学学报,2003,35(2):193 197. 3JAGADEESH G R, SRIKANTHAN T. Heuristic techniques for ac celerating hierarchical routing on road networksJ. IEEE Trans on Intelligent Transportation Systems, 2002,3(4):301-309. 4陈玉敏,龚
9、健雅,史文中.多级道路网的最优路径算法研究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. 9Oracle Corporation. Oracle spatial users guide and reference release 9.0.1EB/OL.2006- 09.http:/
