最优路径规划算法一种限制搜索区域的多比例尺
发布时间：2015-07-04 09:17
摘要：针对现有大区域范围路径规划算法存在的一些问题，提出一种限制搜索区域的多比例尺最优路径规划算法。该算法在进行路径规划时，一方面根据路网的多比例尺信息对路网进行分级，另一方面对搜索区域进行合理限制。测试实验表明此算法可以提高路径规划的效率。
关键词：限制搜索区域；多比例尺；最优路径规划算法；dijkstra算法
为了提高大区域路网路径规划的效率,国内外很多专家学者做了大量的研究工作，提出了一些新的算法。这些算法大多数采用路网分级技术或分解技术来减少大规模路网的存储需求和计算的开销，如文献[1~3]中提出的算法。然而现有的路网分级分解技术存在着一些问题,主要表现在[4]:路网分解没有统一的标准；路网分级处理时,大多按照道路的属性,如主干道、次干道等,对路网进行分级,要求属性信息非常完整,否则无法分级；若提取出的每一级路网不连通时将无法处理；在涉及到几百甚至几千幅地图时,从每幅地图中提取主干道、次干道路网再拼接成多级路网,其工作量巨大,可行性不强；等等。针对以上问题，本文提出一种限制搜索区域的多比例尺最优路径规划算法（multiscaleoptimalrouteplanningalgorithmwithinrestrictedsearchingarea，morparsa）。
1morparsa
1．1路网的空间分布特性
与普通的平面网络图相比,描述实际城市路网的拓扑图通常具有以下特点[5,6]：每个节点相连的路段数一般不超过5，多为2、3或4；网络结构相对比较规则(特别是经过规划的现代化都市)；网络中有表示供车辆调头的专门换向节点,而且一般距当前路口500m左右。
1．2区域限制的思想
dijkstra算法求解的是某个源点到其余各节点的最短路径，它按节点距起始点距离递增的顺序产生最短路径，因此该算法在最短路径的搜索过程中具有很大的盲目性，随时都准备向四面八方展开[5]。该算法搜索的区域是整个路网平面，时间复杂度为o(n2)。其中n为路网中的节点数。
由于实际城市路网结构相对比较规则(特别是经过规划的现代化都市，如西安市)[5~7]中，最短路径一般都会落入以起始点s和目标点d的连线为对角线的矩形区域中，如图1中的小矩形。应该说明的是，在靠近两节点的附近，有时可能会出现短距离的反向路径(指在线段sd的两端点外，沿sd或ds延长线方向的路径，反映在实际系统中，通常代表车辆为转入合适车道行驶所走过的路径)[5]，此时最短路径显然不会落在以s和d的连线为对角线的矩形区域中，因此将以s和d的连线为对角线的矩形四边向外各扩展500m，形成一个更大的矩形作为限制区域，如图1所示。
如果路网中的节点在整个路网平面内均匀分布(即节点数与其所占区域的面积成正比，即使局部节点的分布不均匀)，那么搜索过程中实际所需访问的节点数就可用搜索扫过区域的面积c表示，进而搜索的时间复杂度可表示为o(c2)[5]。假设图1中整个路网平面的面积为c1，大矩形的面积为c2。由于c2＜＜c1,合理限制搜索区域理论上可以提高路径规划的效率。
1．3多比例尺路网数据模型
人们习惯于用比例尺的概念来描述地图对现实世界不同详尽程度的表达，比例尺越大，对现实世界的描述就越详细，对空间对象几何形的描述也越详细。可以用比例尺来描述不同重要程度的道路，如图2所示。
我国基础地理信息的比例尺系列包括1∶100万、1∶50万、1∶25万、1∶10万、1∶5万、1∶1万等，多比例尺自然就起到了分级的作用。
多比例尺信息的这种分级特性与道路的属性信息相关，主要道路存在于小比例尺地图中，次要道路存在于大比例尺地图中，而且大比例尺地图中包含了小比例尺地图中的道路，显示了更为详细的道路信息。因此，可以采用多比例尺数据构建多级路网结构处理大区域的路径搜索问题[4,8],如图3所示。
基于多比例尺数据构建的多级路网模型解决了原有的分级分解算法中存在的一些问题,主要改进的问题如下[4,8]:根据道路属性对道路进行分级时，需要作一些处理,很难保证提取的同一级路网是连通的，采用多比例尺数据构建的多级路网,多比例尺本身起到了分级的作用，在每一比例尺下,路网数据具有连通性。现有的分级分解算法一般按照道路的属性对路网进行分级,因而在道路属性信息不完整的情况下无法处理；在大区域范围内,即使属性信息齐全,提取构建多级路网工作量繁重、不易实施。在全国基本比例尺地形图库已经建立的情况下,采用多比例尺数据构建多级路网显然是可行的。
1．4算法描述
设多级路网一共有w级(w≥1)。
输入：多比例尺路网数据，起始点s、目标点d为路网中任意指定的两个节点。
输出：s和d之间的一条最优路径。
3结束语
本文提出的morparsa可以提高路径规划的效率。多级路网中,低级网络一般为主要干道,符合驾驶者首先选择行驶在主干道的愿望,避开了交通不方便的次要道路,合理性较高。
参考文献：
[1]彭飞,柳重堪,张其善.车辆定位与导航系统中的快速路径规划算法[j].北京航空航天大学学报,2002,28(1):70-73.
[2]陈则王,袁信.基于分层分解的一种实时车辆路径规划算法[j].南京航空航天大学学报,2003,35(2):193197.
[3]jagadeesh g r, srikanthan t. heuristic techniques for accelerating hierarchical routing on road networks[j]. ieee trans on intelligent transportation systems, 2002,3(4):301-309.
[4]陈玉敏,龚健雅,史文中.多级道路网的最优路径算法研究[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):123127.
[8]王晏民,李德仁,龚健雅.一种多比例尺gis方案及其数据模型[j].武汉大学学报,2003,28(4):458-462.
[9]oracle corporation. oracle spatial user’s guide and reference release 9.0.1[eb/ol].[2006-09]./.
关键词：限制搜索区域；多比例尺；最优路径规划算法；dijkstra算法
为了提高大区域路网路径规划的效率,国内外很多专家学者做了大量的研究工作，提出了一些新的算法。这些算法大多数采用路网分级技术或分解技术来减少大规模路网的存储需求和计算的开销，如文献[1~3]中提出的算法。然而现有的路网分级分解技术存在着一些问题,主要表现在[4]:路网分解没有统一的标准；路网分级处理时,大多按照道路的属性,如主干道、次干道等,对路网进行分级,要求属性信息非常完整,否则无法分级；若提取出的每一级路网不连通时将无法处理；在涉及到几百甚至几千幅地图时,从每幅地图中提取主干道、次干道路网再拼接成多级路网,其工作量巨大,可行性不强；等等。针对以上问题，本文提出一种限制搜索区域的多比例尺最优路径规划算法（multiscaleoptimalrouteplanningalgorithmwithinrestrictedsearchingarea，morparsa）。
1morparsa
1．1路网的空间分布特性
与普通的平面网络图相比,描述实际城市路网的拓扑图通常具有以下特点[5,6]：每个节点相连的路段数一般不超过5，多为2、3或4；网络结构相对比较规则(特别是经过规划的现代化都市)；网络中有表示供车辆调头的专门换向节点,而且一般距当前路口500m左右。
1．2区域限制的思想
dijkstra算法求解的是某个源点到其余各节点的最短路径，它按节点距起始点距离递增的顺序产生最短路径，因此该算法在最短路径的搜索过程中具有很大的盲目性，随时都准备向四面八方展开[5]。该算法搜索的区域是整个路网平面，时间复杂度为o(n2)。其中n为路网中的节点数。
由于实际城市路网结构相对比较规则(特别是经过规划的现代化都市，如西安市)[5~7]中，最短路径一般都会落入以起始点s和目标点d的连线为对角线的矩形区域中，如图1中的小矩形。应该说明的是，在靠近两节点的附近，有时可能会出现短距离的反向路径(指在线段sd的两端点外，沿sd或ds延长线方向的路径，反映在实际系统中，通常代表车辆为转入合适车道行驶所走过的路径)[5]，此时最短路径显然不会落在以s和d的连线为对角线的矩形区域中，因此将以s和d的连线为对角线的矩形四边向外各扩展500m，形成一个更大的矩形作为限制区域，如图1所示。
如果路网中的节点在整个路网平面内均匀分布(即节点数与其所占区域的面积成正比，即使局部节点的分布不均匀)，那么搜索过程中实际所需访问的节点数就可用搜索扫过区域的面积c表示，进而搜索的时间复杂度可表示为o(c2)[5]。假设图1中整个路网平面的面积为c1，大矩形的面积为c2。由于c2＜＜c1,合理限制搜索区域理论上可以提高路径规划的效率。
1．3多比例尺路网数据模型
人们习惯于用比例尺的概念来描述地图对现实世界不同详尽程度的表达，比例尺越大，对现实世界的描述就越详细，对空间对象几何形的描述也越详细。可以用比例尺来描述不同重要程度的道路，如图2所示。
我国基础地理信息的比例尺系列包括1∶100万、1∶50万、1∶25万、1∶10万、1∶5万、1∶1万等，多比例尺自然就起到了分级的作用。
多比例尺信息的这种分级特性与道路的属性信息相关，主要道路存在于小比例尺地图中，次要道路存在于大比例尺地图中，而且大比例尺地图中包含了小比例尺地图中的道路，显示了更为详细的道路信息。因此，可以采用多比例尺数据构建多级路网结构处理大区域的路径搜索问题[4,8],如图3所示。
基于多比例尺数据构建的多级路网模型解决了原有的分级分解算法中存在的一些问题,主要改进的问题如下[4,8]:根据道路属性对道路进行分级时，需要作一些处理,很难保证提取的同一级路网是连通的，采用多比例尺数据构建的多级路网,多比例尺本身起到了分级的作用，在每一比例尺下,路网数据具有连通性。现有的分级分解算法一般按照道路的属性对路网进行分级,因而在道路属性信息不完整的情况下无法处理；在大区域范围内,即使属性信息齐全,提取构建多级路网工作量繁重、不易实施。在全国基本比例尺地形图库已经建立的情况下,采用多比例尺数据构建多级路网显然是可行的。
1．4算法描述
设多级路网一共有w级(w≥1)。
输入：多比例尺路网数据，起始点s、目标点d为路网中任意指定的两个节点。
输出：s和d之间的一条最优路径。
3结束语
本文提出的morparsa可以提高路径规划的效率。多级路网中,低级网络一般为主要干道,符合驾驶者首先选择行驶在主干道的愿望,避开了交通不方便的次要道路,合理性较高。
参考文献：
[1]彭飞,柳重堪,张其善.车辆定位与导航系统中的快速路径规划算法[j].北京航空航天大学学报,2002,28(1):70-73.
[2]陈则王,袁信.基于分层分解的一种实时车辆路径规划算法[j].南京航空航天大学学报,2003,35(2):193197.
[3]jagadeesh g r, srikanthan t. heuristic techniques for accelerating hierarchical routing on road networks[j]. ieee trans on intelligent transportation systems, 2002,3(4):301-309.
[4]陈玉敏,龚健雅,史文中.多级道路网的最优路径算法研究[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):123127.
[8]王晏民,李德仁,龚健雅.一种多比例尺gis方案及其数据模型[j].武汉大学学报,2003,28(4):458-462.
[9]oracle corporation. oracle spatial user’s guide and reference release 9.0.1[eb/ol].[2006-09]./.