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

被引：213

作者：

DROR, M

机构：

来源：

OPERATIONS RESEARCH | 1994年 / 42卷 / 05期

关键词：

D O I：

10.1287/opre.42.5.977

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

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.

引用

页码：977 / 978

页数：2