A modified auction algorithm for the shortest path problem
作者:
R. Cerulli,
R. De Leone,
G. Piacente,
期刊:
Optimization Methods and Software
(Taylor Available online 1994)
卷期:
Volume 4,
issue 3
页码: 209-224
ISSN:1055-6788
年代: 1994
DOI:10.1080/10556789408805588
出版商: Gordon and Breach Science Publishers
关键词: Auction algorithm, shortest path
数据来源: Taylor
摘要:
A modified auction algorithm for solving the shortest path problem is presented and convergence is established. The proposed method differs from the standard auction algorithm in the way dual variables are updated. By relaxing the dual feasibility requirement we were able to reduce the total number of iterations required by the auction algorithm to compute the shortest path. Computational results show the advantage of this new approach, especially when the number of intermediate nodes in the shortest path from the origin to the destination is large.
点击下载:
PDF (498KB)
返 回