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

Authors
DROR M
Citation
M. Dror, NOTE ON THE COMPLEXITY OF THE SHORTEST-PATH MODELS FOR COLUMN GENERATION IN VRPTW, Operations research, 42(5), 1994, pp. 977-978
Citations number
2
Categorie Soggetti
Management,"Operatione Research & Management Science","Operatione Research & Management Science
Journal title
Operations research → ACNP
ISSN journal
0030364X
Volume
42
Issue
5
Year of publication
1994
Pages
977 - 978
Database
ISI
SICI code
0030-364X(1994)42:5<977:NOTCOT>2.0.ZU;2-X
Abstract
In this note we prove that the relaxation approach in designing the su bproblem 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. De srosiers and M. Solomon (1992), that is able to price out all feasible routes, is NP-hard in the strong sense.