@inproceedings{8baa7a106a2c40ef9dfb0004839d04c3,
title = "The asymmetric traveling salesman problem: Algorithms, instance generators, and tests",
abstract = "The purpose of this paper is to provide a preliminary report on the first broad-based experimental comparison of modern heuristics for the asymmetric traveling salesmen problem (ATSP). There are currently three general classes of such heuristics: classical tour construction heuristics such as Nearest Neighbor and the Greedy algorithm, local search algorithms based on re-arranging segments of the tour, as exemplified by the Kanellakis-Papadimitriou algorithm [KP80], and algorithms based on patching together the cycles in a minimum cycle cover, the best of which are variants on an algorithm proposed by Zhang [Zha93]. We test implementations of the main contenders from each class on a variety of instance types, introducing a variety of new random instance generators modeled on real-world applications of the ATSP. Among the many tentative conclusions we reach is that no single algorithm is dominant over all instance classes, although for each class the best tours are found either by Zhang{\textquoteright}s algorithm or an iterated variant on Kanellakis- Papadimitriou.",
author = "Jill Cirasella and Johnson, {David S.} and McGeoch, {Lyle A.} and Weixiong Zhang",
note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2001.; 3rd International Workshop on Algorithm Engineering and Experimentation, ALENEX 2001 ; Conference date: 05-01-2001 Through 06-01-2001",
year = "2001",
doi = "10.1007/3-540-44808-x_3",
language = "English",
isbn = "3540425608",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "32--59",
editor = "Buchsbaum, {Adam L.} and Jack Snoeyink",
booktitle = "Algorithm Engineering and Experimentation - 3rd International Workshop, ALENEX 2001, Revised Papers",
}