Finding Multi-Constrained Multiple Shortest Paths

Numerous algorithms have been proposed for the well-known multi-constrained shortest path (MCSP) problem, but very few have good practical performance in case of two or more constraints. In this paper, we propose a new Lagrangian relaxation algorithm to solve a generalized version of the MCSP problem where we search for multiple shortest paths subject to multiple constraints. As in some related work, our algorithm first identifies the lower and upper bounds, and then tries to close the gap with a path enumeration procedure. However, our algorithm is based on the recognition that the Lagrange multipliers found by existing methods usually do not give the best search direction for minimizing path enumerations even though they can provide near-optimized lower bounds. We provide a solution to meet both of these goals, and incorporate feasibility checks into a state-of-the-art K-shortest paths algorithm to further reduce path enumerations. Through experiments on various networks including the most challenging benchmark instances, we show that our algorithm can solve a significantly larger number of instances to optimality with less computational cost, often by one or two orders of magnitude, when compared with the best known algorithm in the literature.