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.


Title New cutting-planes for the time-and/or precedence-constrained ATSP and directed VRP
Author(s) 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
1432-5217
Keyword(s) integer programming
VRP-TW
PC-ATSP
ATSP-TW
PC-VRP
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
Field of Research 010206 Operations Research
HERDC Research category C1 Refereed article in a scholarly journal
Copyright notice ©2007, Springer-Verlag
Persistent URL http://hdl.handle.net/10536/DRO/DU:30007727

Document type: Journal Article
Collection: School of Engineering and Information Technology
Connect to link resolver
 
Unless expressly stated otherwise, the copyright for items in DRO is owned by the author, with all rights reserved.

Versions
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 1 times in TR Web of Science
Scopus Citation Count Cited 1 times in Scopus
Google Scholar Search Google Scholar
Access Statistics: 396 Abstract Views  -  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 drosupport@deakin.edu.au.