Facets of the polytope of the asymmetric travelling salesman problem with replenishment arcs
Data(s) |
01/01/2006
|
---|---|
Resumo |
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.<br /><br />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.<br /> |
Identificador | |
Idioma(s) |
eng |
Publicador |
Elsevier BV |
Relação |
http://dro.deakin.edu.au/eserv/DU:30003867/n20061077.pdf http://dx.doi.org/10.1016/j.disopt.2005.10.003 |
Direitos |
2005, Elsevier BV |
Palavras-Chave | #combinatorial optimisation #travelling salesman #polyhedral combinatorics |
Tipo |
Journal Article |