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

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

0.00 Avg rating0 Votes
Article ID: iaor2007460
Country: Netherlands
Volume: 3
Issue: 1
Start Page Number: 33
End Page Number: 49
Publication Date: Mar 2006
Journal: Discrete Optimization
Authors: ,
Abstract:

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 by Mak and Boland are, under appropriate conditions, facet-defining for the RATS polytope.

Reviews

Required fields are marked *. Your email address will not be published.