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.