最短路拍卖算法在交通分配中的应用

被引：4

作者：

王京元 ^{[1
]}

程琳 ^{[2
]}

机构：

[1] 深圳大学土木工程学院交通工程系

[2] 东南大学交通学院

来源：

交通运输系统工程与信息 | 2006年 / 06期

关键词：

拍卖算法; 最短路; 交通分配;

D O I：

10.16097/j.cnki.1009-6744.2006.06.011

中图分类号：

U491.123 [];

学科分类号：

082302 ; 082303 ;

摘要：

拍卖算法是由Bertsekas教授提出的一种求解有向网络图最短路径的新算法,已经发展成为求解线性网络流问题的综合算法.应用分析对比法进行研究.介绍了拍卖算法,分析了其特点,与常用的标号设定算法和标号修正算法进行了对比.最短路拍卖算法特别适合于并行计算和大规模稀疏网络的求解,符合现实路网的特点和交通分配的要求,并且便于程序化.通过各种途径对基本算法进行改进、加速,可使计算速度提高数倍.拍卖算法可以快速求出多个起点和一个终点以及一个起点和多个终点的情况,适应不同分配算法的需求.在交通分配中,只要根据需求选择不同的起点集和终点集即可,不必求得所有节点对之间的最短路,避免大量不必要的计算,大大节省计算时间,在交通领域具有广阔的应用前景.

引用

页码：79 / 82

页数：4