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:
  https://doi.org/10.1007/s13676-012-0010-0
• 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