Traveling Salesman Problem

Back to Combinatorial Optimization

Introduction

Perhaps the most famous combinatorial optimization problem is the Traveling Salesman Problem (TSP). Given a complete graph on \(n\) vertices and a weight function defined on the edges, the objective of the TSP is to construct a tour (a circuit that passes through each vertex exactly once) of minimum total weight. The TSP is an example of a hard combinatorial optimization problem; the decision version of the problem is \(\mathcal{NP}\)-complete.

Integer Programming Formulation
The TSP can be formulated as an integer linear programming problem. Let \(N\) be the set of vertices (cities) and let \(c_{ij}\) be the weight of the edge connecting vertex \(i\) and vertex \(j\). Let decision variable \(x_{ij}\) take the value 1 if the tour includes the edge connecting \(i\) and \(j\) and the value 0 otherwise.

Minimize \( \sum_{i \in N} \sum_{j \in N} c_{ij} x_{ij}\)

subject to: must enter each vertex exactly once
\(\sum_{i \in N} x_{ij} = 1, \quad \forall j \in N\)

subject to: must exit each vertex exactly once
\(\sum_{j \in N} x_{ij} = 1, \quad \forall i\in N\)

subject to: subtour elimination constraints
\(\sum_{i, j \in S} x_{ij} \leq |S| - 1, \quad \forall S \subset N\)

subject to: integrality constraints
\(x_{ij}\) integer

Software Resources

  • A NEOS version of the Concorde solver is available for users to solve TSP instances online.
  • Stephan Mertens's TSP Algorithms in Action uses Java applets to illustrate some simple heuristics and compare them to optimal solutions on 10-25 node problems.
  • Onno Waalewijn has constructed Java TSP applets exhibiting the behavior of different methods for heuristic and exhaustive search on various test problems.
  • The TSP Package for R provides infrastructure for specifying instances of a TSP and its (possibly optimal) solution as well as several heuristics to find good solutions. It also provides an interface to the Concorde solver.
  • TSP Solver for Google Maps API is a component for Google Maps API developers to compute the fastest route that visits a given set of locations.

For practical purposes, the traveling salesman problem is only the simplest case of what are generally known as vehicle-routing problems. Commercial software packages for vehicle routing, or more generally for supply chain management, may have TSP routines. OR/MS Today periodically publishes a vehicle routing software survey. The most recent survey appeared in the February 2014 issue.

Online Resources

  • The Traveling Salesman Problem website provides information on the history, applications, and current research on the TSP as well as information about the Concorde solver.
  • Travelling Salesman Problem on Wikipedia provides some information on the history, solution approaches, and related problems.
  • TSPLIB provides a library of sample instances for the TSP and related problems.

References

  • Applegate, D. L., Bixby, R. E., Chvátal, V., and Cook, W. J. 2006. The Traveling Salesman Problem: A Computational Study. Princeton University Press, Princeton, NJ.
  • Cook, W. J. 2011. In Pursuit of the Travelling Salesman: Mathematics at the Limits of Computation. Princeton University Press, Princeton, NJ.
  • Lawler, E. L., Lenstra, J. K., Rinnooy Kan, A. H. G., and Shmoys, D. B. 1985. The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. John Wiley and Sons, New York.
  • Reinelt, G. 1994. The Traveling Salesman: Computational Solutions for TSP Applications. Springer-Verlag, Heidelberg.