A Polyhedral Study of the Elementary Shortest Path Problem with Resource Constraints

The elementary shortest path problems with resource constraints (ESPPRC) in graphs with negative cycles appear as subproblems in column-generation solution approaches for the well-known vehicle routing problem with time windows (VRPTW). ESPPRC is \(\mathcal {NP}\)-hard in the strong sense [8]. Most previous approaches alternatively address a relaxed version of the problem where the path does not have to be elementary, and pseudo-polynomial time algorithms based on dynamic programming are successfully applied. However, this method has a significant disadvantage which is a weakening of the lower bound and may induce a malfunction of the algorithm in some applications [9]. Additionally, previous computational studies on variants of VRPs show that labeling algorithms do not outperform polyhedral approaches when the time windows are wide [13] and may not even be applied in some situations [7]. Furthermore, an integer programming approach is more flexible that allows one to easily incorporate general branching decisions or valid inequalities that would change the structure of the pricing subproblem.