动态路径优算方法
摘要：在实时动态路网中求解最佳路径是车辆导航领域面临的关键问题。现在流行的最短路径算法有Dijkstra 算法、A* 算法, 它们都建立在信息完全准确、静态路网的前提下。本文介绍一种新的动态最佳路径算法, 初始时建立好最佳路径, 当环境变化时, 充分利用先前计算结果, 降低时间复杂度, 从而较迅速做出新的最佳路径选择。
关键词: 动态最佳路径; 改进A* 算法
正文
用于静态路网的D ijkstra算法和A* 算法简介
传统D ijkstra算法是求解最短路径问题的经典算法, D ijkstra算法是建立在抽象的网络模型上, 把路线抽象为网络中的边, 以边的权值来表示道路的相关的参数, 算法确定了赋权网络中从某点到所有其他节点的具有最小权值的路, D ijkstra算法主要特点是以起始节点S为中心向外层层扩展, 直到扩展到目标节点为止。它忽略了网络模型的个体特性, 因此它的时间复杂度较高, 在城市道路网的路径寻优问题中, 网络模型。具有如下特点: ( 1)网络模型中有海量弧段节点。
( 2)交通网络既具有随机性又具有时间依赖性。
因此, 虽然传统D ijkstra算法理论上是可行的, 但是考虑到计算机硬件水平等其他限制, 如果直接使用到实际中, 基本不能满足要求。虽然随着算法的不断改进, 出现了众多的D ijkstra改进算法, 常用的有: 数据结构采用二进制堆的方法, 从起始点和目标点同时搜索的方法, 分层搜索等。算法的时间复杂程度已明显减小。D ijkstra算法能得出最短路径的最优解, 但由于它遍历计算的节点很多, 所以效率低。
A*算法[6]，作为启发式算法中很重要的一种，被广泛应用在最优路径求解和一些策略设计的问题中。而作为这种启发式的搜索，它与深度优先搜索(DFS)和广度优先搜索(BFS)这类盲目型搜索最大的不同，就在于当前搜索结点往下选择下一步结点时，可以通过一个启发函数来进行选择，选择代价最少的结点作为下一步搜索结点而跳转其上。一个经过仔细设计的启发函数，往往在很短的时间内就可得到一个搜索问题的最优解。
A*算法最为核心的部分，就在于它的一个估价函数的设计上式中：
f(x)——整个过程的估价值；g(x)——从源点x0 到节点x已经付出的实际代价；h(x)——启发函数，是从当前节点x 到目标节点xg 的最优路径的估计代价，它体现了问题的启发性信息，其形式要根据问题的特性确定。A*算法作为应用较多的启发式搜索算法，它对搜索过程限制如下：
(1)在存储节点的Open 表中，节点按照估价函数f(x) = g(x)+h(x)的值从小到大进行排序；
(2)g(x)是对g*(x)的估计，g(x)>0；
(3)h(x)是h*(x)的下界，即对所有x 均有h(x)≤h*(x)；
其中g*(x)是从初始节点或源点到节点x 的最小代价，h*(x)是从节点x 到下一目标节点的最小代价。A*算法在整个搜索过程中通常设置两个表来储存节点信息：open 表和closed 表。open 表保存所有已存在且未被考察的节点，closed 表中储存被访问过的节点。
算法在运行过程中会根据估价函数的大小对open 表进行重新排序，这样做的目的是使每一步只需要考虑open 表中状态最好的节点。具体搜索过程如下[7]：
(1)建立并初始化open 表和closed 表，同时将源点(即第一个节点)加入到open 表中；
(2) 若open 表为空，则没有可供查询的节点，程序返回并发出失败信号；
(3)从open 表中取出第一个节点n 放入closed 表中，同时从open 表中删除节点n；
(4)若节点n 就是目标节点，则返回并发出成功信号；
(5) 否则，对节点n 进行扩展，若失败，则跳转到(2)；若可以扩展，则对节点n 的所有后继节点t 进行扩展，这时要对每个子节点进行如下的具体操作；①若节点t 在open 表和closed表中都不存在，则把节点t 更新到open表中；②若节点t在open表中，这时要先计算节点t 的代价函数f(t)，如果代价值比表中的代价函数值小，就将表中的代价函数值更新为当前值；③若节点t 在closed 表中，同样计算代价函数f(t)，如果比表中的代价函数值小，也将表中的代价函数值更新为当前值，并把该节点从表中删除，同时在open 表中加入该节点。
(6)根据代价函数值的大小以升序对open 表进行排序，并转到(2)。
动态最佳路径规划算法
动态路网中求解最佳路径的难点在于路段权值实时刷新, 先前的求解结果会随着路段权值的实时刷新而作废。如果在离散的时间段内重复调用静态路网的算法, 理论上是可以求解动态最佳路径的, 但是即使采用相对效率较高的A* 算法, 每次更新权值后把整个路网重新计算, 效率也是非常低下。笔者通过优化A* 算法提出一种高效的动态最佳路径算法, 只有在一部分影响最终结果的路段权值更新时才重新计算, 而且最大限度地利用先前的求解结果, 具有更低的时间复杂度。动态最佳路径的变化来自以下3个方面:
( 1) 当车辆位置发生异常时。依据已计算出的最佳路径, 当车辆因转向错误等原因而没有在其上时, 则需要重新计算道路的最佳路径。系统应能自动识别车辆位置相对于已确定的最佳路径发生的异常情况, 并及时自动地重新组织数据, 进行最佳路径的重新计算。
( 2) 当最佳路径的终点是动态时。最佳路径会因目标的不确定性运动而随时发生变化, 系统应按目标的位置或时间间隔, 不断寻求车辆当前位置到目标位置的最佳路径。
( 3) 在动态交通条件下求解时。交通道路网是一个动态平衡的网络系统。真正意义上的实时动态最佳路径应是在动态交通条件下, 应用实时动态路段阻抗计算出来的。
此时的最佳路径不再只是图中的简单的最短路径问题, 而是一个复杂的动态网络计算问题。笔者认为, 在大多数情况下司机选择一趟出行时终点是静态的, 最佳路径的变化是在车辆不断靠近终点运动并且路段权值不断更新的过程中。通过分析上述运动过程, 提出两点对A* 算法的优化思路:
( 1)在规划好一条最佳路径后, 将一部分会影响最终计算结果的路段ID存储, 在A* 算法中, 每个节点都是由前继节点方向优先搜索得到的, 所以我们将先前规划好的最佳路径中所有节点的邻接弧段的ID存储, 只有在这些路段的权值更新时才重新计算最佳路径。
( 2)在车辆不断向终点靠近的过程中, 采用终点向车辆当前位置搜索的方法, 由于终点是静态的, 那么靠近终点附近的路段就可以不用重复计算。
具体实现如下:
首先根据需要计算的最佳路径的类型确定估价函数h ( n ), 它决定了搜索的效率和可采纳性。计算路程最短时可以取两点间的欧氏距离作为估价值:
计算时间最短时可以将上述估价函数除以路段平均速度:
