A dual algorithm for the constrained shortest path problem

TLDR

The constrained shortest path problem, which is NP‑hard and arises in integer linear programming and dynamic programming, seeks a minimum‑cost route subject to a knapsack‑type constraint such as total time. The authors aim to develop a Lagrangian relaxation algorithm that reduces the required number of k‑shortest paths needed to satisfy the constraint. They apply Lagrangian relaxation to the kth shortest path framework, terminating when the first feasible path is found and thereby lowering k. Experiments show that this method yields orders‑of‑magnitude savings on large networks, overcoming the impracticality of large k values.

Abstract

Abstract In this paper we develop a Lagrangian relaxation algorithm for the problem of finding a shortest path between two nodes in a network, subject to a knapsack‐type constraint. For example, we may wish to find a minimum cost route subject to a total time constraint in a multimode transportation network. Furthermore, the problem, which is shown to be at least as hard as NP‐complete problems, is generic to a class of problems that arise in the solution of integer linear programs and discrete state/stage deterministic dynamic programs. One approach to solving the problem is to utilize a k th shortest path algorithm, terminating with the first path that satisfies the constraint. This approach is impractical when the terminal value of k is large. Using Lagrangian relaxation we propose a method that is designed to reduce this value of k . Computational results indicate orders of magnitude savings when the approach is applied to large networks.