Models and algorithms for the Asymmetric Traveling Salesman Problem: an experimental comparison
This study surveys the most effective mathematical models and 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 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. Finally, the considered algorithms and formulations are experimentally compared on a set of benchmark instances.
- Record URL:
-
Availability:
- Find a library where document is available. Order URL: http://worldcat.org/issn/21924376
-
Authors:
- Roberti, Roberto
- Toth, Paolo
- Publication Date: 2012-6
Language
- English
Media Info
- Media Type: Digital/other
- Features: Figures; References; Tables;
- Pagination: pp 113-133
-
Serial:
- EURO Journal on Transportation and Logistics
- Volume: 1
- Issue Number: 1-2
- Publisher: SPRINGER VERLAG HEIDELBERG
- ISSN: 2192-4376
- EISSN: 2192-4384
- Serial URL: http://www.springerlink.com/content/2192-4376/
Subject/Index Terms
- TRT Terms: Algorithms; Branch and bound algorithms; Linear programming; Mathematical models; Traveling salesman problem
- Uncontrolled Terms: Branch and cut algorithms
- Subject Areas: Data and Information Technology; Planning and Forecasting; Transportation (General); I72: Traffic and Transport Planning;
Filing Info
- Accession Number: 01447632
- Record Type: Publication
- Files: TRIS
- Created Date: Sep 28 2012 9:13AM