最优路径规划算法一种限制搜索区域的多比例尺.doc

最优路径规划算法一种限制搜索区域的多比例尺 .doc最优路径规划算法一种限制搜索区域的多比例尺
摘要:针对现有大区域范围路径规划算法存在的一些问题,提出一种限制搜索区域的多比例尺最优路径规划算法。该算法在进行路径规划时,一方面根据路网的多比例尺信息对路网进行分级,另一方面对搜索区域进行合理限制。测试实验表明此算法可以提高路径规划的效率。
关键词:限制搜索区域;多比例尺;最优路径规划算法;Dijkstra算法
为了提高大区域路网路径规划的效率,国内外很多专家学者做了大量的研究工作,提出了一些新的算法。这些算法大多数采用路网分级技术或分解技术来减少大规模路网的存储需求和计算的开销,如文献[1~3]中提出的算法。然而现有的路网分级分解技术存在着一些问题,主要表现在[4]:路网分解没有统一的标准;路网分级处理时,大多按照道路的属性,如主干道、次干道等,对路网进行分级,要求属性信息非常完整,否则无法分级;若提取出的每一级路网不连通时将无法处理;在涉及到几百甚至几千幅地图时,从每幅地图中提取主干道、次干道路网再拼接成多级路网,其工作量巨大,可行性不强;等等。针对以上问题,本文提出一种限制搜索区域的多比例尺最优路径规划算法(multiscaleoptimalrouteplanningalgorithm左右。

Dijkstra算法求解的是某个源点到其余各节点的最短路径,它按节点距起始点距离递增的顺序产生最短路径,因此该算法在最短路径的搜索过程中具有很大的盲目性,随时都准备向四面八方展开[5]。该算法搜索的区域是整个路网平面,时间复杂度为O(n2)。其中n为路网中的节点数。
由于实际城市路网结构相对比较规则(特别是经过规划的现代化都市,如西安市)[5~7]中,最短路径一般都会落入以起始点S和目标点D的连线为对角线的矩形区域中,如图1中的小矩形。应该说明的是,在靠近两节点的附近,有时可能会出现短距离的反向路径(指在线段SD的两端点外,沿SD或DS延长线方向的路径,反映在实际系统中,通常代表车辆为转入合适车道行驶所走过的路径)[5],此时最短路径显然不会落在以S和D的连线为对角线的矩形区域中,因此将以S和D的连线为对角线的矩形四边向外各扩展500m,形成一个更大的矩形作为限制区域,如图1所示。
如果路网中的节点在整个路网平面内均匀分布(即节点数与其所占区域的面积成正比,即使局部节点的分布不均匀),那么搜索过程中实际所需访问的节点数就可用搜索扫过区域的面积
C表示,进而搜索的时间复杂度可表示为O(C2)[5]。假设图1中整个路网平面的面积为C1,大矩形的面积为C2。由于C2<<C1,合理限制搜索区域理论上可以提高路径规划的效率。

人们****惯于用比例尺的概念来描述地图对现实世界不同详尽程度的表达,比例尺越大,对现实世界的描述就越详细,对空间对象几何形的描述也越详细。可以用比例尺来描述不同重要程度的道路,如图2所示。