A heuristic approach to hard constrained shortest path problems (Q1063522)

Constrained shortest path problems have many applications in areas like network routing, investments planning and project evaluation as well as in some classical combinatorial problems with high duality gaps where even obtaining feasible solutions is a difficult task in general. We present in this paper a systematic method for obtaining good feasible solutions to hard (doubly constrained) shortest path problems. The algorithm is based essentially on the concept of efficient solutions which can be obtained via parametric shortest path calculations. The computational results obtained show that the approach proposed here leads to optimal or very good near optimal solutions for all the problems studied. From a theoretical point of view, the most important contribution of the paper is the statement of a pseudopolynomial algorithm for generating the efficient solutions and, more generally, for solving the parametric shortest path problem.