Paper Info
Title
Tolerance based contract-or-patch heuristic for the asymmetric TSP
Abstract
In this paper we improve the quality of a recently suggested class of construction heuristics for the Asymmetric Traveling Salesman Problem (ATSP), namely the Contract-or-Patch heuristic. Our improvement is based on replacing the selection of each path to be contracted after deleting a heaviest arc from each short cycle in an Optimal Assignment Problem Solution (OAPS) by contracting a single arc from a short cycle in an OAPS with the largest upper tolerance with respect to one of the relaxed ATSP. The improved algorithm produces higher-quality tours than all previous COP versions and is clearly outperforming all other construction heuristics on robustness.
Year
DOI
Venue
2006
10.1007/11922377_8
CAAN
Keywords
Field
DocType
single arc,short cycle,contract-or-patch heuristic,improved algorithm,asymmetric tsp,higher-quality tour,optimal assignment problem solution,heaviest arc,largest upper tolerance,salesman problem,construction heuristics,traveling salesman problem,discrete mathematics
Mathematical optimization,Heuristic,Arc (geometry),Computer science,Algorithm,Robustness (computer science),Travelling salesman problem,Assignment problem,Heuristics
Conference
Volume
ISSN
ISBN
4235
0302-9743
3-540-48822-7
Citations 
PageRank 
References 
10
0.55
12
Authors
3
Name
Order
Citations
PageRank
Boris Goldengorin118217.58
Gerold Jäger211314.66
P. Molitor321118.50