Groupe d’études et de recherche en analyse des décisions

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.