交通系统工程论文

《交通系统工程论文》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、动态路径优算方法摘要：在实时动态路网中求解最佳路径是车辆导航领域面临的关键问题。现在流行的最短路径算法有Dijkstra算法、A*算法，它们都建立在信息完全准确、静态路网的前提下。本文介绍一种新的动态最佳路径算法，初始时建立好最佳路径，当环境变化时，充分利用先前计算结果，降低吋间复杂度，从而较迅速做出新的最佳路径选择。关键词：动态最桂路径；改进A*算法正文用于静态路网的Dijkstra算法和A*算法简介传统Dijkstra算法是求解最短路径问题的经典算法，Dijkstm算法是建立在抽象的网络模型上，把路线抽象

2、为网络中的边，以边的权值來表示道路的相关的参数，算法确定了赋权网络屮从某点到所有其他节点的具有最小权值的路，Dijkstra算法主要特点是以起始节点S为中心向外层层扩展，直到扩展到目标节点为止。它忽略了网络模型的个体特性,因此它的吋间复杂度较高，在城市道路M的路径寻优问题中，网络模型。具有如下特点：(1)网络模型中有海量弧段节点。(2)交通网络既具有随机性又具有时间依赖性。因此，虽然传统1)ijkstra算法理论上是可行的，但是考虑到计算机硬件水平等其他限制，如果直接使用到实际中，基本不能满足要求。虽然随着算

3、法的不断改进，出现了众多的Dijkstra改进算法，常用的有：数据结构采用二进制堆的方法，从起始点和目标点同吋搜索的方法，分层搜索等。算法的时间复杂程度己明显减小。Dijkstm算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。A*算法[6],作为启发式算法中很重要的一种，被广泛应用在最优路径求解和一些策略设计的问题中。而作为这种启发式的搜索，它与深度优先搜索(DFS)和广度优先搜索(BFS)这类盲目型搜索最大的不同，就在于当前搜索结点往下选择下一步结点时，可以通过一个启发函数来进行选择，选

4、择代价最少的结点作为下一步搜索结点而跳转其上。一个经过仔细设计的启发函数，往往在很短的时间内就可得到一个搜索问题的最优解。A*算法最为核心的部分，就在于它的一个估价函数的设计上式中：f(x)一一整个过程的估价值；g(x)一一从源点xO到节点x己经付出的实际代价：h(x)一一启发函数，是从当前节点X到目标节点xg的最优路径的估计代价，它体现了问题的启发性信息，其形式要根据问题的特性确定。A*算法作为应用较多的启发式搜索算法，它对搜索过程限制如下：(1)在存储节点的Open表中，节点按照佔价函数f(x)=g(x)

5、+h(x)的值从小到大进行排序;(2)g(x)是对g*(x)的估计，g(x)>0；(3)h(x)是h*(x)的下界，即对所有x均有h(x)

6、'^过的节点。算法在运行过程屮会根据估价函数的大小对open表进行重新排序，这样做的目的是使每一步只需要考虑ope

7、n表中状态最好的节点。具体搜索过程如下[7]:(1)建立并初始化open表和closed表，同时将源点(BP第一个节点)加入到open表中;(2)若open表为空，则没有可供查询的节点，程序返回并发出失败信号；(3)从open表中取出第一个节点n放入closed表中，同时从open表中删除节点、n;(4)若节点n就是目标节点，则返回并发出成功信号；(5)否则，对节点n进行扩展，若失败，则跳转到(2);若可以扩展，则对节点n的所有后继节点t进行扩展，这吋要对每个子节点进行如下的具体操作；①若节点t在open表和

8、closed表巾都不存在，则把节点t更新到open表巾；②若节点t在open表中，这时要先计算节点t的代价函数f(t)，如果代价值比表中的代价函数值小，就将表中的代价函数值更新为当前值；③若节点t在closed表屮，同样计算代价函数f(t)，如果比表屮的代价函数值小，也将表中的代价函数值更新为当前值，并把该节点从表中删除，同时在open表中加入该节点。(6)根据代价函数值的大小以升序对open表进行排序，并转到(2)。动态最佳路径规划算法动态路咧屮求解最佳路径的难点在于路段权值实时刷新，先前的求解结果会随着路

9、段权值的实吋刷新而作废。如果在离散的吋间段内重复调用静态路网的算法，理论上是可以求解动态最佳路径的，但是即使采川相对效率较高的A*算法，每次更新权值后把整个路网重新计算，效率也是非常低下。笔者通过优化A*算法提出一种高效的动态最桂路径算法，只有在一部分影响最终结果的路段权值更新时才重新计算，而且最大限度地利用先前的求解结果，具有更低的时间复杂度。动态最桂路径的变化来自以下3个方面：(1)当车辆位置发