Polyhedral results and exact algorithms for the asymmetric travelling salesman problem with replenishment arcs

Mak, Vicky and Boland, Natashia 2007, Polyhedral results and exact algorithms for the asymmetric travelling salesman problem with replenishment arcs, Discrete applied mathematics, vol. 155, no. 16, pp. 2093-2110.

Attached Files
Name Description MIMEType Size Downloads

Title Polyhedral results and exact algorithms for the asymmetric travelling salesman problem with replenishment arcs
Author(s) Mak, Vicky
Boland, Natashia
Journal name Discrete applied mathematics
Volume number 155
Issue number 16
Start page 2093
End page 2110
Publisher Elsevier B.V.
Place of publication Amsterdam, Netherlands
Publication date 2007-10-01
ISSN 0166-218X
1872-6771
Keyword(s) combinatorial optimisation
branch-and-bound method
lagrangean relaxation
polyhedral analysis
travelling salesman
Summary The asymmetric travelling salesman problem with replenishment arcs (RATSP), arising from work related to aircraft routing, is a generalisation of the well-known ATSP. In this paper, we introduce a polynomial size mixed-integer linear programming (MILP) formulation for the RATSP, and improve an existing exponential size ILP formulation of Zhu [The aircraft rotation problem, Ph.D. Thesis, Georgia Institute of Technology, Atlanta, 1994] by proposing two classes of stronger cuts. We present results that under certain conditions, these two classes of stronger cuts are facet-defining for the RATS polytope, and that ATSP facets can be lifted, to give RATSP facets. We implement our polyhedral findings and develop a Lagrangean relaxation (LR)-based branch-and-bound (BNB) algorithm for the RATSP, and compare this method with solving the polynomial size formulation using ILOG Cplex 9.0, using both randomly generated problems and aircraft routing problems. Finally we compare our methods with the existing method of Boland et al. [The asymmetric traveling salesman problem with replenishment arcs, European J. Oper. Res. 123 (2000) 408–427]. It turns out that both of our methods are much faster than that of Boland et al. [The asymmetric traveling salesman problem with replenishment arcs, European J. Oper. Res. 123 (2000) 408–427], and that the LR-based BNB method is more efficient for problems that resemble the aircraft rotation problems.
Language eng
Field of Research 010206 Operations Research
HERDC Research category C1 Refereed article in a scholarly journal
Copyright notice ©2007, Elsevier B.V.
Persistent URL http://hdl.handle.net/10536/DRO/DU:30007547

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 2 times in TR Web of Science
Scopus Citation Count Cited 3 times in Scopus
Google Scholar Search Google Scholar
Access Statistics: 397 Abstract Views, 0 File Downloads  -  Detailed Statistics
Created: Mon, 29 Sep 2008, 08:53:22 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.