Journal article
Models and algorithms for the Asymmetric Traveling Salesman Problem: an experimental comparison
This paper surveys the most effective mathematical models and exact algorithms proposed for finding the optimal solution of the well-known Asymmetric Traveling Salesman Problem (ATSP). The fundamental Integer Linear Programming (ILP) model proposed by Dantzig, Fulkerson and Johnson is first presented, its classical (assignment, shortest spanning r-arborescence, linear programming) relaxations are derived, and the most effective branch-and-bound and branch-and-cut algorithms are described.
The polynomial ILP formulations proposed for the ATSP are then presented and analyzed. The considered algorithms and formulations are finally experimentally compared on a set of benchmark instances.
Language: | English |
---|---|
Publisher: | Springer-Verlag |
Year: | 2012 |
Pages: | 113-133 |
ISSN: | 21924384 and 21924376 |
Types: | Journal article |
DOI: | 10.1007/s13676-012-0010-0 |
Asymmetric Traveling Salesman Problem Branch-and-bound algorithms Branch-and-cut algorithms Economics / Management Science Experimental comparison Integer Linear Programming models Operations Research, Management Science Operations Research/Decision Theory Optimization Production/Logistics/Supply Chain