收藏本站 | 联系我们 | 设为首页 | English
当前位置:主页>计算机论文>
一种限制搜索区域的多比例尺最优路径规划算法
来源:  作者:本站

  摘要:针对现有大区域范围路径规划算法存在的一些问题,提出一种限制搜索区域的多比例尺最优路径规划算法。该算法在进行路径规划时,一方面根据路网的多比例尺信息对路网进行分级,另一方面对搜索区域进行合理限制。测试实验表明此算法可以提高路径规划的效率。
  关键词:限制搜索区域; 多比例尺; 最优路径规划算法; Dijkstra算法

  为了提高大区域路网路径规划的效率,国内外很多专家学者做了大量的研究工作,提出了一些新的算法。这些算法大多数采用路网分级技术或分解技术来减少大规模路网的存储需求和计算的开销,如文献[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所示。
上一页12 下一页

关于本站 | 会员服务 | 隐私保护 | 法律声明 | 站点地图 | RSS订阅 | 友情链接
免责声明:凡本站注明来源为xx所属媒体的作品,均转载自其它媒体转载目的在于传递更多信息,并不代表本站赞同其观点和对其真实性负责。