Abstract: The auction algorithm is a new and simple algorithm for finding shortest paths in a directed graph proposed by Prof．Bertsekas and has been extended and applied to a variety of linear network flow problems． rhe auction algorithm for shortest paths was introduced and its characteristics were analyzed．The auction algorithm was compared with other algorithms widely used such as label-setting algorithm and label-correcting algorithm．The auction algorithm is suitable for the parallel implementation and the solution of the large-scale sparse network．These fulfill the properties of actual road network and the requirements of the traffic assignment． The algorithm is easy to realize by procedures．Through a variety of measures to improve and speed up the basic algorithm，the computation speed can increase several times．The auction algorithm can be well suitable for kinds of traffic assignment methods．It can be used efficiently in the case of multiple origins and a single destination，and a single origin and multiple destinations．Different origin set and destination set are determined in accordance with the requirement of the traffic assignment．It is not required to find the shortest paths connecting any node pairs，so a lot of computation amount can be avoided and computing time can be reduced by the use of the auction algorithm in the traffic assignment．Auction algorithms can be broadly applied in the transportation fields．

Key words: auction algorithm, shortest path, traffic assignment

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

关键词: 拍卖算法, 最短路, 交通分配