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

G-2004-11

Shortest Path Problems with Resource Constraints

et

In most vehicle routing and crew scheduling applications solved by column generation, the subproblem corresponds to a shortest path problem with resource constraints (SPPRC) or one of its variants. This paper proposes a classification and a generic formulation for the SPPRCs, briefly discusses complex modeling issues involving resources, and presents the most commonly used SPPRC solution methods. First and foremost, it provides a comprehensive survey on the subject.

, 30 pages

Ce cahier a été révisé en juillet 2004