Journal article

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

Vicky Mak, Natashia Boland

DISCRETE APPLIED MATHEMATICS | ELSEVIER SCIENCE BV | Published : 2007

Abstract

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 findin..

View full abstract

University of Melbourne Researchers