Dynamic Programming Algorithms for the (Elementary) Resource Constrained Shortest Path Problem
André Linhares – ENSTA ParisTech, France
The Resource Constrained Shortest Path Problem (RCSPP) often arises as a subproblem when decomposition techniques are applied to solve optimization problems, notably those of routing and scheduling. In this talk, we present some of the state-of-the-art dynamic programming algorithms for solving the RCSPP in a unified manner, and we propose variants thereof. We assess their efficiency through computational experiments.