第三章 路径规划的分析及设计 21 2.限制搜索区域的确定方法
利用方向搜索策略合理限制算法的搜索区域是设计本算法的关键。 我们将此算法简称3-1算法，如图3.6所示在给定相同的路径规划起始点S和目标点D时，为搜索到从S到D的最短路径，算法RP0所需的搜索区域理论上是一个以S为圆心，以D为半径的圆；而算法3-1所需搜索区域则是如下一个区域：先以S和D的连线为对角线形成一个矩形R1（当S与D的连线水平或垂直时，R1退化为一条线段），然后将R1的各边想外扩展一个阈值T2，形成一个更大的矩形R2，最后通过R2被与线段SD平行、距SD距离为阈值T1的左右（或上下）两条直线L1和L2切割形成搜索区域。
图3.6 限制搜索区域的确定方法
3.算法实现
算法3-1的实现步骤如下：
输入：采用邻接节点数据结构存储的矢量化城市道路网络，路径规划的起点S，终点D，阈值T1和T2。
输出：节点S和节点D之间的一条距离最短路径。
步骤一，初始化，完成道路网络数据加载及程序运行环境设置等。 步骤二，根据阈值T1和T2构造限制搜索区域。
步骤三，在限制搜索区域内，根据给定的起点S和目标点D，调用算法RP0的实现程序进行最短路径计算。
步骤四，输出S和D之间的一条距离最短路径。
以上四步的关键是合理设定阈值T1和T2，构造合适的限制搜索区域。设计中
22 GPS车载导航仪的路径规划研究 主要依据是前面提到的换向距离500m和矢量化道路网络中边的平均长度，本算法中阈值T1和T2分别设为500m和1500m。 3.3.3 基于分层道路网络的分层路径规划算法
前面介绍的限制搜索区域的最短路径规划算法，有效地降低了算法的搜索空间，提高了算法的搜索效率。然而，桐多数路径规划算法一样，限制搜索区域的路径规划算法所解算出的最短路径，仍然只是数学意义上的最短路径，而非意义上的最优路径。所谓行车意义上的最优路径是指多数驾驶员所期望的行车路径。
事实上，最短路径无论距离最短还是时间最短，都不一定是行车意义上的最短路径。因为除了形式距离或形式时间外，最优路径的选择还需要考虑很多无法预期或定量化的因素。本节利用实际城市道路网络中路段的不同等级特性，构造了不同于方向搜索策略的另一种启发式搜索策略，即分层搜索策略，给出了利用该搜索策略设计分层道路网络和基于分层道路网络设计分层路径规划算法的具体方法。
1.算法原理
分层路径规划算法（简称算法3-2）的基本思想是：根据道路网络中路段的不同等级特性，将整个道路网络分为不同的层次，每一层包含道路网络不同级别的细节。高层道路网络是其相邻低层道路网络的抽象和浓缩，低层则是其相邻高层道路网络的具体扩展。换言之，任一高层道路网络内的路段和节点都包含于其相邻的低层道路网络内，而任意一个低层道路网络除了包含其相邻高层道路网络内的路段和节点外，还包含更多的其他路段和节点。这样，在进行路径规划是，我们便可以先在高层空间进行搜索，然后在搜索高层空间获得的结果基础上再添上低层空间的细节，得到问题的最终解。
2.分层道路网络设计
（1）城市道路网络中路段的分等级特性
多数城市道路网络存在的一个事实是其中的路段具有不同等级特性。这些不同的道路等级一般又都对应着不同的行车环境，如道路的行车时速限制、道路上红绿灯的设置间距、道路的宽度及路面质量等多种与行车密切相关的因素。
（2）道路网络的分层方法
将分层思想引入到道路网络的设计中，即根据道路网路中路段的不同等级特
第三章 路径规划的分析及设计 23 性，将整个道路网络RN分为不同的层。
（3）分层道路网络的表示
分层道路网络的表示是指分层道路网络如何在计算机中表示和存储，它是算法3-2的基础。设计中，首先采用Arc-Node模型将整个道路网络表示为：G=(N,A,B)，这里N={N1，N2，?,Nn}是道路网络中节点的集合，A={aij|1≤i≤n,1≤j≤MaxNum，其中MaxNum是RN的最大邻接节点数}是RN中各节点间邻接关系的集合，aij表示第j个与节点i邻接的节点，而且认为两节点间的边是双向的，B={bij|1≤i≤n,1≤j≤MaxNum ，其中MaxNum 是RN的最大邻接节点数}是RN中各邻接节点间连接边的权值合集，bij表示节点i与节点aij之间的边的权值，而且认为两节点间的边是双向的，另外，每条路段都有一个非负的权值和它关联，每条道路则是由一系列首尾相连的路段构成，它的权值是组成它的所有路段的权值之和。然后，为了将RN分为HRN和LRN，定义一个标记数组Mark1来标记RN中的节点属于哪些HRN，若Mark1(i)=1，则表示节点i不仅属于LRN，而且同时属于HRN，这样便将RN从逻辑上分成了高低两层。
3.算法实现
输入：具有拓扑结构矢量化道路网络RN及其对应分层道路网络HRN和LRN，起点S、终点D为道路网络中任意指定的两个节点。
输出：节点S和节点D之间的一条最优路径。
步骤一，初始化，完成路网数据加载及程序运行环境设置。
步骤二，判断节点S和D所在的路网层次，若节点S和D都已经在HRN中，则算法3-2直接转入步骤三；否则，若节点S不在HRN中，则算法必须先在S附近的小区域内调用算法RP0的实现程序进行结算，由它进入高层路网的最短路径L1及相应的位于高层路网上的节点S′，对节点D作类似的处理，求出相应的最短路径L2及相应的位于高层路网上的节点D′。
步骤三，在HRN中对节点S（或对应节点S′）和D（或对应节点D′）调用算法RP0的实现程序解算其最短路径L0。
步骤四，综合L0、L1及L2为L，将L作为节点S和D之间的一条最优路径输出。
3.3.4 限制搜索区域的分层路径规划算法
24 GPS车载导航仪的路径规划研究 由于方向搜索策略和分层搜索策略是从两个不同的角度降低算法搜索空间的，因此可以考虑将二者有机结合，以便同时从不同角度缩小算法的搜索空间，设计更为合理的路径规划算法。本节从这一设计思路出发，将前面的算法3-1和算法3-2进行有机结合，利用方向和分层搜索相结合策略，提出了新的算法3-3.
1.算法原理
算法3-3的基本思想是：先进行分层路径规划，然后再对高层网络中的两个相应节点进行路径规划时，采用限制搜索区域的路径规划算法。与算法3-2不同的是，算法3-3在HRN中搜索时，只对落入限制区域范围内的HRN进行搜索，而不是在整个HRN中进行搜索，因此它只保证搜索结果与算法3-2相同的同时，搜索效率却比算法3-1和算法3-2都高。
2.算法实现
输入：具有拓扑结构的矢量化道路网络RN，RN对应的分层道路网络HRN和LRN，路径规划的起点S和终点D，阈值T1和T2。
输出：节点S和节点D之间的一条行车最优路径。
步骤一，初始化，完成路网数据加载及程序运行环境设置。
步骤二，判断节点S和D所在的路网层次，若节点S和D都已在HRN中，则算法直接转入步骤三；否则，若节点S不在HRN中，则算法现在S附近小区域内调用算法RP0子程序搜索由它进入HRN的最短路径L1及相应的位于HRN上的节点S′，然后，对节点D作同样的处理，求得相应的最短路径L2及相应的位于HRN上的节点D′。
步骤三，根据阈值T1和T2，在HRN中对节点S（或对应的节点S′）和D（或对应的节点D′）构造限制搜索区域，然后调用算法RP0的子程序解算最优路径L0。
步骤四，综合L0、L1及L2为L，将L作为节点S和D之间的最优路径输出。
相关推荐：
loading