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, CORAL 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)
Pages: 20 pages
Date: 2004-04-25
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.hha.dk/afl/wp/log/L_2004_01.pdf (application/pdf)
Our link check indicates that this URL is bad, the error code is: 500 Can't connect to www.hha.dk:80 (No such host is known. )

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:hhb:aarbls:2004-001

Access Statistics for this paper

More papers in CORAL Working Papers from University of Aarhus, Aarhus School of Business, Department of Business Studies The Aarhus School of Business, Fuglesangs Allé 4, DK-8210 Aarhus V, Denmark. Contact information at EDIRC.
Bibliographic data for series maintained by Helle Vinbaek Stenholt ( this e-mail address is bad, please contact ).