Facets of the polytope of the asymmetric travelling salesman problem with replenishment arcs

Mak, Vicky and Boland, Natashia 2006, Facets of the polytope of the asymmetric travelling salesman problem with replenishment arcs, Discrete optimization, vol. 3, no. 1, pp. 33-49, doi: 10.1016/j.disopt.2005.10.003.

Attached Files
Name Description MIMEType Size Downloads

Title Facets of the polytope of the asymmetric travelling salesman problem with replenishment arcs
Author(s) Mak, VickyORCID iD for Mak, Vicky orcid.org/0000-0002-9306-5780
Boland, Natashia
Journal name Discrete optimization
Volume number 3
Issue number 1
Start page 33
End page 49
Publisher Elsevier BV
Place of publication Amsterdam, Netherlands
Publication date 2006
ISSN 1572-5286
Keyword(s) combinatorial optimisation
travelling salesman
polyhedral combinatorics
Summary The Asymmetric Travelling Salesman Problem with Replenishment Arcs (RATSP) is a new class of problems arising from work related to aircraft routing. Given a digraph with cost on the arcs, a solution of the RATSP, like that of the Asymmetric Travelling Salesman Problem, induces a directed tour in the graph which minimises total cost. However the tour must satisfy additional constraints: the arc set is partitioned into replenishment arcs and ordinary arcs, each node has a non-negative weight associated with it, and the tour cannot accumulate more than some weight limit before a replenishment arc must be used. To enforce this requirement, constraints are needed. We refer to these as replenishment constraints.

In this paper, we review previous polyhedral results for the RATSP and related problems, then prove that two classes of constraints developed in V. Mak and N. Boland [Polyhedral results and exact algorithms for the asymmetric travelling salesman problem with replenishment arcs, Technical Report TR M05/03, School of Information Technology, Deakin University, 2005] are, under appropriate conditions, facet-defining for the RATS polytope.
Language eng
DOI 10.1016/j.disopt.2005.10.003
Field of Research 010206 Operations Research
HERDC Research category C1 Refereed article in a scholarly journal
Copyright notice ©2005, Elsevier BV
Persistent URL http://hdl.handle.net/10536/DRO/DU:30003867

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.

Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 5 times in TR Web of Science
Scopus Citation Count Cited 4 times in Scopus
Google Scholar Search Google Scholar
Access Statistics: 598 Abstract Views, 0 File Downloads  -  Detailed Statistics
Created: Mon, 07 Jul 2008, 09:05:27 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.