Travelling Salesman Problem
TSP · CANONICAL FORMULATION
Logistics · Transportation · OperationalThe Travelling Salesman Problem asks for the shortest Hamiltonian cycle visiting each of $n$ cities exactly once and returning to the origin. It is perhaps the most famous problem in combinatorial optimisation — introduced informally by Menger (1932), made computationally famous by Dantzig, Fulkerson & Johnson (1954) with their 49-city LP+cut-plane solution, and today a proving ground for every new exact or heuristic technique. This page gives the two classical integer-programming formulations (MTZ and DFJ), an interactive nearest-neighbour + 2-opt solver on a Euclidean instance, and cross-links to applied instances on this site.
Why TSP matters
A minor miracle of applied mathematics
Mathematical formulation
Two classical formulations · MTZ and DFJ
Notation
| Symbol | Meaning |
|---|---|
| $V = \{1,\ldots,n\}$ | set of cities |
| $c_{ij}$ | distance / cost from city $i$ to city $j$ (symmetric TSP: $c_{ij} = c_{ji}$) |
| $x_{ij} \in \{0,1\}$ | 1 if the tour travels directly from $i$ to $j$, 0 otherwise |
| $u_i$ | auxiliary MTZ position variable for city $i$, $i \ne 1$ |
Objective (shared by both formulations)
Shared degree constraints
MTZ subtour elimination (Miller-Tucker-Zemlin, 1960)
DFJ subtour elimination (Dantzig-Fulkerson-Johnson, 1954)
DFJ gives the tighter LP bound (the convex hull of tours is the TSP polytope) but requires separation procedures to generate violated cuts on demand — handled by modern cutting-plane solvers such as Concorde. MTZ is polynomial-size but weak in the LP; useful for small instances or educational purposes.
Special cases. Metric TSP (triangle inequality: $c_{ij} + c_{jk} \ge c_{ik}$) admits Christofides' 3/2-approximation (improved to $3/2 - \varepsilon$ by Karlin, Klein & Oveis Gharan 2021). Euclidean TSP admits a PTAS (Arora 1996; Mitchell 1999). The asymmetric TSP (ATSP) drops the symmetry and is, until recently, harder to approximate; Svensson-Tarnawski-Végh (2020) gave the first constant-factor approximation.
Real-world to OR mapping
Applied TSP instances across the site
| Real-world concept | OR role |
|---|---|
| Cities, locations, stops | nodes $V$ |
| Road / air distance or drive time | $c_{ij}$ |
| “Courier drives $i \to j$” | $x_{ij} = 1$ |
| Starting depot / warehouse | city 1 (WLOG) |
| Return requirement | Hamiltonian cycle (visit all, return to start) |
Interactive solver
Nearest-Neighbor construction + 2-opt improvement
Two of the most enduring TSP heuristics. Nearest Neighbor starts at city 1, repeatedly moves to the nearest unvisited city, and returns to the start: $O(n^2)$, typically within 25% of optimal. 2-opt (Croes 1958; Lin 1965) improves any tour by repeatedly reversing any segment whose reversal shortens the tour: the neighbourhood has size $\binom{n}{2}$ and 2-opt-optimal tours are usually within 5% of optimal.
Standard benchmarks
TSPLIB and beyond
- TSPLIB (Reinelt 1991) — the canonical library. ~110 symmetric TSP instances with 14–85,900 nodes; best-known solutions verified for decades. comopt.ifi.uni-heidelberg.de/TSPLIB95
- DIMACS Challenge (2002) — a systematic computational study of TSP heuristics on large random and clustered instances.
- VLSI & World TSP — the pla85900 (85,900 cities) and World TSP (~1.9 million cities) instances remain active frontiers.
The Concorde solver (Applegate, Bixby, Chvátal & Cook) holds the record for nearly all exact results. LKH (Helsgaun 2000) is the state-of-the-art heuristic.
Key references
DOIs & permanent URLs