Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
482346 | European Journal of Operational Research | 2006 | 14 Pages |
Abstract
This paper introduces a class of cuts, called reachability cuts, for the Vehicle Routing Problem with Time Windows (VRPTW). Reachability cuts are closely related to cuts derived from precedence constraints in the Asymmetric Traveling Salesman Problem with Time Windows and to k-path cuts for the VRPTW. In particular, any reachability cut dominates one or more k-path cuts. The paper presents separation procedures for reachability cuts and reports computational experiments on well-known VRPTW instances. The computational results suggest that reachability cuts can be highly useful as cutting planes for certain VRPTW instances.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Jens Lysgaard,