NOTE ON THE COMPLEXITY OF THE SHORTEST-PATH MODELS FOR COLUMN GENERATION IN VRPTW

In this note we prove that the relaxation approach in designing the subproblem of pricing out only the feasible routes for the set partition formulation of the VRPTW is justified on complexity grounds. That is, the first dynamic programming model presented in M. Desrochers, J. Desrosiers and M. Solomon (1992), that is able to price out all feasible routes, is NP-hard in the strong sense.