Constrained shortest paths and related problems
Mark Ziegelmann · 2001
The classical shortest path problem, to find a path of minimal cost between two nodes in a graph, is efficiently solvable in polynomial time. However, in many applications we also have additional budget or resource constraints on a path. This problem is known as constrained shortest path problem and unfortunately belongs to the class of ``hard'' problems for which no polynomial time algorithm is known. In this thesis, we propose a 2-step method for the constrained shortest path problem. We first solve a relaxation to get upper and lower bounds and then close the gap with clever path ranking to obtain the exact solution. We compare different old and new methods both theoretically and experimentally. The 2-step method also works for a more general class of constrained network optimization problems. We illustrate the generic approach using several examples. We have also developed a software package {\sc Cnop} that provides this generic 2-step approach as well as all state of the art algorithms for constrained shortest paths.