Improved preprocessing, labeling and scaling algorithms for the Weight‐Constrained Shortest Path Problem

Abstract

Much has been written on shortest path problems with weight, or resource, constraints. However, relatively little of it has provided systematic computational comparisons for a representative selection of algorithms. Furthermore, there has been almost no work showing numerical performance of scaling algorithms, although worst‐case complexity guarantees for these are well known, nor has the effectiveness of simple preprocessing techniques been fully demonstrated. Here, we provide a computational comparison of three scaling techniques and a standard label‐setting method. We also describe preprocessing techniques which take full advantage of cost and upper‐bound information that can be obtained from simple shortest path information. We show that integrating information obtained in preprocessing within the label‐setting method can lead to very substantial improvements in both memory required and run time, in some cases, by orders of magnitude. Finally, we show how the performance of the label‐setting method can be further improved by making use of all Lagrange multiplier information collected in a Lagrangean relaxation first step. © 2003 Wiley Periodicals, Inc.