Note on the Complexity of the Shortest Path Models for Column Generation in VRPTW

Moshe Dror
Additional contact information
Moshe Dror: University of Arizona, Tucson, Arizona

Operations Research, 1994, vol. 42, issue 5, 977-978

Abstract: 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.

Keywords: dynamic programming/optimal control: complexity of shortest path time windows; transportation: complexity of shortest path time windows (search for similar items in EconPapers)
Date: 1994
References: Add references at CitEc
Citations: View citations in EconPapers (73)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.42.5.977 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:42:y:1994:i:5:p:977-978

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().