Answers are grounded in this paper and cite their sources.
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.
No takes yet. Share an insight, caveat, or question.
Handler et al. (1980) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: