Deakin University
Browse

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

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

History

Journal

Discrete optimization

Volume

3

Pagination

33 - 49

Location

Amsterdam, Netherlands

Open access

  • Yes

ISSN

1572-5286

eISSN

1873-636X

Language

eng

Publication classification

C1 Refereed article in a scholarly journal

Copyright notice

2005, Elsevier BV