最短路径重构算法和其在路网交通分配中应用

《最短路径重构算法和其在路网交通分配中应用》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、最短路径重构算法和其在路网交通分配中应用摘要：本文回顾了最短路径算法，通过比对Dijkstra算法与作为交通分配模型的特殊算法的最短路径算法，从而分析最短路径重构算法在交通分配中的适用性关键词：最短路径重构算法、最短路径树、交通分配0引言20世纪80年代初，我国开始了大规模的交通基础设施建设，但随着经济的发展、交通流量的剧增，交通拥堵现象频现，如何科学地利用智能交通科技手段，提升交通系统的管理水平和运行效率，是现今道路交通发展的重点。交通分配是智能交通的重要分析环节，最短路径问题是网络交通分配的热点，而交通建模则是其重要的应用领域。本文首先介绍了Dijkst

2、ra算法，其次介绍了最短路径重构算法，最后分析最短路径重构算法在交通分配中的适用性，并与传统的Dijkstra算法在交通分配的应用中进行时间效率高低的比较。1最短路径问题的基本算法1.1基本概念通常所说的最短路径问题是指在给定的网络中找出从源点r到终点s满足距离最短（的一条路径，这是最基本的问题类型，可称为单源单汇(one-to-one)问题，相应地给定G和r,若要找出r到其余所有节点的最短路径，可称为单源多汇(one-to-all)问题；若要找出r到部分节点的最短路径，可称为one-to-some问题；若要找出所有节点对之间的最短路径，称为多源多汇(all

3、-to-all)问题。1.2经典最短路算法Dijstra算法Dijstra提出一个按最短路径长度递增的次序产生的最短路径的算法，即先求得只有1条边的最短路径，再求得由2条边组成的最短路径，由3条边组成的最短路径。该算法的基本思想是：设置两个顶点的集合S和T(S+T二Vn),集合S中存放已经找到的最短路径的顶点。初始状态时，集合S中只包含源点Vn,然后不断地从集合T中选取路径长度最短的顶点vj加入到集合S中，集合S每加入一个新的顶点vj,都要检测T中各顶点新的最短路径长度值为原来所保存的最短路径长度值与从源点vm到顶点vj的最短路径长度值加上从vj到该顶点的路

4、径长度值中的较小者。此过程不断重复,直到集合T的顶点全部加入到S中为止，此过程不断重复，直到集合T的顶点全部加入到S中为止。2最短路径的重构算法最短路径重构算法的基本思路是，采用一定得再优化技术，更新前一次得到的最短路径树，获得源点或弧长改编后的新的最短路径树，因而该算法在时间效率上将有很大的提升空间。在Gallo观察源点改变的最短路径树的属性的基础上，Gallo和Pallottino提出了新的最短路径重构算法，这个算法跟其他算法相比，在交通网络的应用中显得更加适用。该算法在运算过程中一直保持着费用标签，费用标签等于减少费用。从新的源点s开始，每一步，算法通

5、过加入新的节点和弧，扩展新的最短路径树T*,直至T*超出有向图G。准确地说，算法认为边界弧分割T*跟剩余的节点，若边界弧（u,v）,u属于T*且v具有最小的费用标签，则把弧（u,v）加入到T*中，此外，若（u,V）加入T*中后，在Tr中以节点v为跟点的子树的所有节点因为其更新费用都为0,也就是说，这些节点的费用标签跟节点v的费用标签相同，则以在Tr中以节点v为根点的子树完全转移到T*中。通过重复执行以上的操作，可以使所有的节点转移到T*中，从而得出新的以s为源点的完整最短路径树。3最短路径重构算法在交通分配中的应用3.1交通分配的基本概念所谓交通分配就是将各

6、种出行方式0D矩阵按照一定得规则符合实际地分配到交通网络中的各条道路上，求出各路段上的流量及先关的交通指标，从而为交通网络的设计、评价等提供依据。交通分配可以归纳为问题形式：一一已知：①交通网络的有向图表示形式；②路段特性函数；③)0D矩阵。求解：网络中个路段的交通量及阻抗值。一般的交通网络中，每一0D对之间有很多条路段，如何将0D量正确、合理地分配到这些路径上是交通问题的核心。3.2最短路径重构算法在交通分配中的适用性关于交通建模中最短路径问题的研究应由寻求普遍适用的“最佳算法”转移到寻求面向问题的“特定算法”上，也就是抓住所要解决问题的特征，设计适合问题

7、的特定数据结构，尽可能提高算法在实际问题上的运行效率。在大型的交通网络中，需要解决一系列的最短路径问题，其数量是巨大的，在网络如仅加入一个点后就会产生(k+1)th与kth个最短路径问题的差别。而在交通建模中经常会有以下需要：多次甚至不断地搜索最短路径树，但相邻两次搜索的条件和要求差别不大，要么是源点改变而网络中所有弧的长度保持不变，要么是源点不变而网络中部分弧的长度发生了改变。如使用最短路径重构算法对大型网络而言通常更节省计算时间。最短路径重构算法是采用一定的再优化技术，更新前一次得到的最短路径树，获得源点改变或者弧长改变中其中一种情况，或者两种情况结合后

8、的最短路径树。在交通分配模型中，由于交通分配本身具有