Reachability cuts for the vehicle routing problem with time windows

Jens Lysgaard ()
Additional contact information
Jens Lysgaard: Department of Business Studies, Postal: The Aarhus School of Business, Fuglesangs Allé 4, 8210 Aarhus V, Denmark, http://www.asb.dk/staff/bs/lys.aspx?page=%7B803EFF10-69F7-4C0F-AEE3-F7F410E4B6F2%7D

No L-2004-01, Logistics/SCM Research Group Working Papers from University of Aarhus, Aarhus School of Business, Department of Business Studies

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.

Keywords: Routing; time windows; precedence constraints (search for similar items in EconPapers)
Date: 2004-04-25
View list of references

Downloads: (external link)
http://www.hha.dk/afl/wp/log/L_2004_01.pdf (application/pdf)

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

Access Statistics for this paper

More papers in Logistics/SCM Research Group Working Papers from University of Aarhus, Aarhus School of Business, Department of Business Studies
Address: The Aarhus School of Business, Fuglesangs Allé 4, DK-8210 Aarhus V, Denmark
Contact information at EDIRC.
Series data maintained by Helle Vinbaek Stenholt ().