计算机科学
布线(电子设计自动化)
路径(计算)
最短路径快速算法
Dijkstra算法
延氏算法
作者
Dominique Feillet,Pierre Dejax,Michel Gendreau,Cyrille Gueguen
出处
期刊:Networks
[Wiley]
日期:2004-10-01
卷期号:44 (3): 216-229
被引量:511
摘要
In this article, we propose a solution procedure for the Elementary Shortest Path Problem with Resource Constraints (ESPPRC). A relaxed version of this problem in which the path does not have to be elementary has been the backbone of a number of solution procedures based on column generation for several important problems, such as vehicle routing and crew pairing. In many cases relaxing the restriction of an elementary path resulted in optimal solutions in a reasonable computation time. However, for a number of other problems, the elementary path restriction has too much impact on the solution to be relaxed or might even be necessary. We propose an exact solution procedure for the ESPPRC, which extends the classical label correcting algorithm originally developed for the relaxed (nonelementary) path version of this problem. We present computational experiments of this algorithm for our specific problem and embedded in a column generation scheme for the classical Vehicle Routing Problem with Time Windows. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 44(3), 216–229 2004
科研通智能强力驱动
Strongly Powered by AbleSci AI