论文部分内容阅读
摘要：本文回顾了最短路径算法，通过比对 Dijkstra算法与作为交通分配模型的特殊算法的最短路径算法，从而分析最短路径重构算法在交通分配中的适用性
关键词：最短路径重构算法、最短路径树、交通分配
0引言
20世纪80年代初，我国开始了大规模的交通基础设施建设，但随着经济的发展、交通流量的剧增，交通拥堵现象频现，如何科学地利用智能交通科技手段，提升交通系统的管理水平和运行效率，是现今道路交通发展的重点。交通分配是智能交通的重要分析环节，最短路径问题是网络交通分配的热点，而交通建模则是其重要的应用领域。
本文首先介绍了Dijkstra算法，其次介绍了最短路径重构算法，最后分析最短路径重构算法在交通分配中的适用性，并与传统的Dijkstra算法在交通分配的应用中进行时间效率高低的比较。
1 最短路径问题的基本算法
1.1 基本概念
通常所说的最短路径问题是指在给定的网络中找出从源点r到终点s满足距离最短（的一条路径，这是最基本的问题类型，可称为单源单汇（one-to-one）问题，相应地给定G和r，若要找出r到其余所有节点的最短路径，可称为单源多汇（one-to-all）问题；若要找出r到部分节点的最短路径，可称为one-to-some问题；若要找出所有节点对之间的最短路径，称为多源多汇（all-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到该顶点的路径长度值中的较小者。此过程不断重复，直到集合T的顶点全部加入到S中为止，此过程不断重复，直到集合T的顶点全部加入到S中为止。
2最短路径的重构算法
最短路径重构算法的基本思路是，采用一定得再优化技术，更新前一次得到的最短路径树，获得源点或弧长改编后的新的最短路径树，因而该算法在时间效率上将有很大的提升空间。在Gallo观察源点改变的最短路径树的属性的基础上，Gallo和Pallottino提出了新的最短路径重构算法，这个算法跟其他算法相比，在交通网络的应用中显得更加适用。
该算法在运算过程中一直保持着费用标签 ，费用标签等于减少费用。从新的源点s开始，每一步，算法通过加入新的节点和弧，扩展新的最短路径树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 交通分配的基本概念
所谓交通分配就是将各种出行方式OD矩阵按照一定得规则符合实际地分配到交通网络中的各条道路上，求出各路段上的流量及先关的交通指标，从而为交通网络的设计、评价等提供依据。
交通分配可以归纳为问题形式：——已知：①交通网络的有向图表示形式；②路段特性函数；③）OD矩阵。求解：网络中个路段的交通量及阻抗值。一般的交通网络中，每一OD对之间有很多条路段，如何将OD量正确、合理地分配到这些路径上是交通问题的核心。
3.2 最短路径重构算法在交通分配中的适用性
关于交通建模中最短路径问题的研究应由寻求普遍适用的“最佳算法”转移到寻求面向问题的“特定算法”上，也就是抓住所要解决问题的特征，设计适合问题的特定数据结构，尽可能提高算法在实际问题上的运行效率。
在大型的交通网络中，需要解决一系列的最短路径问题，其数量是巨大的，在网络如仅加入一个点后就会产生（k+1）th与kth个最短路径问题的差别。而在交通建模中经常会有以下需要：多次甚至不断地搜索最短路径树，但相邻两次搜索的条件和要求差别不大，要么是源点改变而网络中所有弧的长度保持不变，要么是源点不变而网络中部分弧的长度发生了改变。如使用最短路径重构算法对大型网络而言通常更节省计算时间。
最短路径重构算法是采用一定的再优化技术，更新前一次得到的最短路径树，获得源点改变或者弧长改变中其中一种情况，或者两种情况结合后的最短路径树。在交通分配模型中，由于交通分配本身具有的多个OD点对需要被分配，并在交通分配方法中需要经常多次迭代计算得出新的路权值，显然在交通分配模型中，引用最短路径重构算法在提高时间效率上具有很大的潜力。
3.3 分析在交通分配模型中最短路径重构算法的优缺点
交通分配算法在本质上是网络加载过程的收敛序列，次网络加载中需要搜索基于不同源点的最短路径树，这就可以实施源点改变、弧长不变的最短路径重构算法；一次网络加载后，并非所有的路段阻抗都会发生变化，下一次加载就可以实施源点不变、部分弧长改变的最短路径重构算法；同时还可以对上述过程进行组合，探索源点和弧长均变的最短路径重构算法。
总的来说，最短路径重构算法在交通分配模型中具有一定得潜力，但其中也存在一些问题，包括设计适合问题的特定数据结构、算法效率的影响因素、与基本算法的关系等。需要更深入的研究才能更有的放矢地将其应用于交通分配算法中，最大限度地发挥最短路径重构算法的优势。
4结束语
交通分配问题和最短路径问题都是国内外备受关注的课题，在交通模型更趋复杂化和集成化的前提下，最短路径重构算法作为具有一定特性交通分配模型的“特定算法”显然具有很大的发展潜力，对其进行深入的研究不但具有极高的理论价值，同时也具有重要的现实意义。本文介绍了常用的变源点最短路径重构算法的基本概念与流程，并与Dijkstra算法进行流程的比较，但仅限于原理。日后可考虑通过实际算例，考证最短路径重构算法。
参考文献：
[1]Pallottino S， Scutella M. A new algorithm for reoptimizing shortest paths when the arc costs change [J]. Operations Research Letters，2003，31：149-160.
[2]Dijkstra E W. A note on two problems in connexion with graphs [J]. Numeriche Matematik， 1959， 1： 269-271.
关键词：最短路径重构算法、最短路径树、交通分配
0引言
20世纪80年代初，我国开始了大规模的交通基础设施建设，但随着经济的发展、交通流量的剧增，交通拥堵现象频现，如何科学地利用智能交通科技手段，提升交通系统的管理水平和运行效率，是现今道路交通发展的重点。交通分配是智能交通的重要分析环节，最短路径问题是网络交通分配的热点，而交通建模则是其重要的应用领域。
本文首先介绍了Dijkstra算法，其次介绍了最短路径重构算法，最后分析最短路径重构算法在交通分配中的适用性，并与传统的Dijkstra算法在交通分配的应用中进行时间效率高低的比较。
1 最短路径问题的基本算法
1.1 基本概念
通常所说的最短路径问题是指在给定的网络中找出从源点r到终点s满足距离最短（的一条路径，这是最基本的问题类型，可称为单源单汇（one-to-one）问题，相应地给定G和r，若要找出r到其余所有节点的最短路径，可称为单源多汇（one-to-all）问题；若要找出r到部分节点的最短路径，可称为one-to-some问题；若要找出所有节点对之间的最短路径，称为多源多汇（all-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到该顶点的路径长度值中的较小者。此过程不断重复，直到集合T的顶点全部加入到S中为止，此过程不断重复，直到集合T的顶点全部加入到S中为止。
2最短路径的重构算法
最短路径重构算法的基本思路是，采用一定得再优化技术，更新前一次得到的最短路径树，获得源点或弧长改编后的新的最短路径树，因而该算法在时间效率上将有很大的提升空间。在Gallo观察源点改变的最短路径树的属性的基础上，Gallo和Pallottino提出了新的最短路径重构算法，这个算法跟其他算法相比，在交通网络的应用中显得更加适用。
该算法在运算过程中一直保持着费用标签 ，费用标签等于减少费用。从新的源点s开始，每一步，算法通过加入新的节点和弧，扩展新的最短路径树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 交通分配的基本概念
所谓交通分配就是将各种出行方式OD矩阵按照一定得规则符合实际地分配到交通网络中的各条道路上，求出各路段上的流量及先关的交通指标，从而为交通网络的设计、评价等提供依据。
交通分配可以归纳为问题形式：——已知：①交通网络的有向图表示形式；②路段特性函数；③）OD矩阵。求解：网络中个路段的交通量及阻抗值。一般的交通网络中，每一OD对之间有很多条路段，如何将OD量正确、合理地分配到这些路径上是交通问题的核心。
3.2 最短路径重构算法在交通分配中的适用性
关于交通建模中最短路径问题的研究应由寻求普遍适用的“最佳算法”转移到寻求面向问题的“特定算法”上，也就是抓住所要解决问题的特征，设计适合问题的特定数据结构，尽可能提高算法在实际问题上的运行效率。
在大型的交通网络中，需要解决一系列的最短路径问题，其数量是巨大的，在网络如仅加入一个点后就会产生（k+1）th与kth个最短路径问题的差别。而在交通建模中经常会有以下需要：多次甚至不断地搜索最短路径树，但相邻两次搜索的条件和要求差别不大，要么是源点改变而网络中所有弧的长度保持不变，要么是源点不变而网络中部分弧的长度发生了改变。如使用最短路径重构算法对大型网络而言通常更节省计算时间。
最短路径重构算法是采用一定的再优化技术，更新前一次得到的最短路径树，获得源点改变或者弧长改变中其中一种情况，或者两种情况结合后的最短路径树。在交通分配模型中，由于交通分配本身具有的多个OD点对需要被分配，并在交通分配方法中需要经常多次迭代计算得出新的路权值，显然在交通分配模型中，引用最短路径重构算法在提高时间效率上具有很大的潜力。
3.3 分析在交通分配模型中最短路径重构算法的优缺点
交通分配算法在本质上是网络加载过程的收敛序列，次网络加载中需要搜索基于不同源点的最短路径树，这就可以实施源点改变、弧长不变的最短路径重构算法；一次网络加载后，并非所有的路段阻抗都会发生变化，下一次加载就可以实施源点不变、部分弧长改变的最短路径重构算法；同时还可以对上述过程进行组合，探索源点和弧长均变的最短路径重构算法。
总的来说，最短路径重构算法在交通分配模型中具有一定得潜力，但其中也存在一些问题，包括设计适合问题的特定数据结构、算法效率的影响因素、与基本算法的关系等。需要更深入的研究才能更有的放矢地将其应用于交通分配算法中，最大限度地发挥最短路径重构算法的优势。
4结束语
交通分配问题和最短路径问题都是国内外备受关注的课题，在交通模型更趋复杂化和集成化的前提下，最短路径重构算法作为具有一定特性交通分配模型的“特定算法”显然具有很大的发展潜力，对其进行深入的研究不但具有极高的理论价值，同时也具有重要的现实意义。本文介绍了常用的变源点最短路径重构算法的基本概念与流程，并与Dijkstra算法进行流程的比较，但仅限于原理。日后可考虑通过实际算例，考证最短路径重构算法。
参考文献：
[1]Pallottino S， Scutella M. A new algorithm for reoptimizing shortest paths when the arc costs change [J]. Operations Research Letters，2003，31：149-160.
[2]Dijkstra E W. A note on two problems in connexion with graphs [J]. Numeriche Matematik， 1959， 1： 269-271.