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

拍卖算法是由Bertsekas教授提出的一种求解有向网络图最短路径的新算法,并已经发展成为求解线性网络流问题的综合算法.本文首先介绍了拍卖算法,分析了其特点,并将其与常用的标号设定算法和标号修正算法进行了对比.深入分析了交通路网的特点和交通分配中最短路求解的特性.研究结果表明,最短路拍卖算法特别适合于并行计算和大规模稀疏网络的求解,符合现实路网的特点和交通分配的要求.最短路拍卖算法应用于交通分配能避免大量不必要的计算,大大节省计算时间,在交通领域具有广阔的应用前景.

Application of Auction Algorithm for the Shortest Paths in Traffic Flow Assignment

Auction algorithm is a new and simple algorithm for finding the shortest paths inadirectedgraphproposedby Prof. Bertsekas and has been extended and applied to avariety of linear network flow problems. The auction algorithm for the shortest paths was introduced and its characteristics were analyzed. The auction algorithm is compared with other widely used algorithms such as label-setting algorithm and label-correcting algorithm. The properties of the urban street network and the peculiarities of finding the shortest paths during traffic assignment were analyzed profoundly. The study results show that the auction algorithm is suitable to the parallel implementation and solving the large-scale sparse network. These fulfill the properties of actual road network and the requirements of the traffic assignment. A lot of computation amount can be avoided and the computing time can be reduced by the use of the auction algorithm in traffic assignment. Auction algorithm can be broadly applied in transportation fields.