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.

Language

  • English

Media Info

Subject/Index Terms

Filing Info

  • Accession Number: 01447632
  • Record Type: Publication
  • Files: TRIS
  • Created Date: Sep 28 2012 9:13AM