New cutting-planes for the time-and/or precedence-constrained ATSP and directed VRP

Mak, Vicky and Ernst, Andreas T. 2007, New cutting-planes for the time-and/or precedence-constrained ATSP and directed VRP, Mathematical methods of operations research, vol. 66, no. 1, pp. 69-98, doi: 10.1007/s00186-006-0141-x.

Attached Files
Name Description MIMEType Size Downloads

Title New cutting-planes for the time-and/or precedence-constrained ATSP and directed VRP
Author(s) Mak, VickyORCID iD for Mak, Vicky
Ernst, Andreas T.
Journal name Mathematical methods of operations research
Volume number 66
Issue number 1
Start page 69
End page 98
Publisher Physica-Verlag GmbH und Co.
Place of publication Heidelberg, Germany
Publication date 2007-08
ISSN 1432-2994
Keyword(s) integer programming
facets of polyhedra
Summary In this paper, we introduce five classes of new valid cutting planes for the precedence-constrained (PC) and/or time-window-constrained (TW) Asymmetric Travelling Salesman Problems (ATSPs) and directed Vehicle Routing Problems (VRPs). We show that all five classes of new inequalities are facet-defining for the directed VRP-TW, under reasonable conditions and the assumption that vehicles are identical. Similar proofs can be developed for the VRP-PC. As ATSP-TW and PC-ATSP can be formulated as directed identical-vehicle VRP-TW and PC-VRP, respectively, this provides a link to study the polyhedral combinatorics for the ATSP-TW and PC-ATSP. The first four classes of these new cutting planes are cycle-breaking inequalities that are lifted from the well-known D-k and D+k inequalities (see Grötschel and Padberg in Polyhedral theory. The traveling salesman problem: a guided tour of combinatorial optimization, Wiley, New York, 1985). The last class of new cutting planes, the TW 2 inequalities, are infeasible-path elimination inequalities. Separation of these constraints will also be discussed. We also present prelimanry numerical results to demonstrate the strengh of these new cutting planes.
Language eng
DOI 10.1007/s00186-006-0141-x
Field of Research 010206 Operations Research
HERDC Research category C1 Refereed article in a scholarly journal
Copyright notice ©2007, Springer-Verlag
Persistent URL

Connect to link resolver
Unless expressly stated otherwise, the copyright for items in DRO is owned by the author, with all rights reserved.

Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 7 times in TR Web of Science
Scopus Citation Count Cited 4 times in Scopus
Google Scholar Search Google Scholar
Access Statistics: 833 Abstract Views, 0 File Downloads  -  Detailed Statistics
Created: Mon, 29 Sep 2008, 08:55:26 EST

Every reasonable effort has been made to ensure that permission has been obtained for items included in DRO. If you believe that your rights have been infringed by this repository, please contact