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

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