Given a set of cities, and the cost of traveling between each pair of them, the Traveling Salesman Problem, TSP for short, calls for finding a unique tour visiting all cities at minimum cost. Besides being for sure the best known combinatorial optimization problem, the TSP has many applications, not only in Operations Research/Management Science (especially in transportation and logistics), but also in many other fields, such as genome sequencing or drilling of printed circuits boards. We review some of the TSP ancestors, including the famous Hamiltonian cycle problem, of which the TSP is the weighted version. We examine the most famous formulations for both symmetric and asymmetric TSP, and the main combinatorial approaches for its solution.

Combinatorial Traveling Salesman Problem Algorithms

D'AMBROSIO, CLAUDIA;LODI, ANDREA;MARTELLO, SILVANO
2011

Abstract

Given a set of cities, and the cost of traveling between each pair of them, the Traveling Salesman Problem, TSP for short, calls for finding a unique tour visiting all cities at minimum cost. Besides being for sure the best known combinatorial optimization problem, the TSP has many applications, not only in Operations Research/Management Science (especially in transportation and logistics), but also in many other fields, such as genome sequencing or drilling of printed circuits boards. We review some of the TSP ancestors, including the famous Hamiltonian cycle problem, of which the TSP is the weighted version. We examine the most famous formulations for both symmetric and asymmetric TSP, and the main combinatorial approaches for its solution.
Wiley Encyclopedia of Operations Research and Management Science, 8 volume-set
738
747
C. D'Ambrosio; A. Lodi; S. Martello
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11585/85425
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact