NOTE ON THE COMPLEXITY OF THE SHORTEST-PATH MODELS FOR COLUMN GENERATION IN VRPTW
成果类型：
Note
署名作者：
DROR, M
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.42.5.977
发表日期：
1994
页码：
977-978
关键词：
摘要：
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.