Deakin University
Browse
mak-poluhedralresults-2007.pdf (240.71 kB)

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

Download (240.71 kB)
journal contribution
posted on 2007-10-01, 00:00 authored by Vicky MakVicky Mak, N Boland
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.

History

Journal

Discrete applied mathematics

Volume

155

Pagination

2093 - 2110

Location

Amsterdam, Netherlands

Open access

  • Yes

ISSN

0166-218X

eISSN

1872-6771

Language

eng

Publication classification

C1 Refereed article in a scholarly journal

Copyright notice

2007, Elsevier B.V.