Models and algorithms for the Asymmetric Traveling Salesman Problem: an experimental comparison

Roberto Roberti, Paolo Toth

Research output: Contribution to journalJournal articleResearchpeer-review

982 Downloads (Pure)

Abstract

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.
Original languageEnglish
JournalEURO Journal on Transportation and Logistics
Volume1
Issue number1-2
Pages (from-to)113-133
Number of pages21
ISSN2192-4376
DOIs
Publication statusPublished - 2012
Externally publishedYes

Keywords

  • Asymmetric Traveling Salesman Problem
  • Integer Linear Programming models
  • Branch-and-bound algorithms
  • Branch-and-cut algorithms
  • Experimental comparison

Fingerprint

Dive into the research topics of 'Models and algorithms for the Asymmetric Traveling Salesman Problem: an experimental comparison'. Together they form a unique fingerprint.

Cite this