Lagrangian Relaxation and Enumeration for Solving Constrained Shortest-Path Problems
Abstract
The constrained shortest-path problem (CSPP) generalizes the standard shortest-path problem by adding one or more path-weight side constraints. We present a new algorithm for CSPP that Lagrangianizes those constraints, optimizes the resulting Lagrangian function, identifies a feasible solution, and then closes any optimality gap by enumerating nearshortest paths, measured with respect to the Lagrangianized length. "Near-shortest" implies epsilon-optimal, with a varying epsilon that equals the current optimality gap. The algorithm exploits a new path-enumeration method, aggregate constraints, preprocessing to eliminate edges that cannot form part of an optimal solution, "reprocessing" that reapplies preprocessing steps as improved solutions are found and, when needed, a "phase-I procedure" to identify a feasible solution before searching for an optimal one. The new algorithm is often an order of magnitude faster than a state-of-the-art labelsetting algorithm on singly constrained randomly-generated grid networks. On multi-constrained grid networks, road networks, and networks for aircraft routing the advantage varies, but, overall, the new algorithm is competitive with the label-setting algorithm.
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 15, 2007
- Accession Number
- ADA486693
Entities
People
- Johannes Ø. Røyset
- R. Kevin Wood
- W. M. Carlyle
Organizations
- Naval Postgraduate School