The Traveling Salesman Problem

A delivery driver must visit twenty addresses and return to the depot, driving as few miles as possible. A welding robot must touch 500 points on a circuit board and come back to rest. A telescope must slew between hundreds of stars in the least total time. Strip away the story and each is the same question: given a set of places and the distance between every pair, find the shortest closed route that visits every place exactly once. This is the Traveling Salesman Problem (TSP) — the most famous hard problem in all of operations research, and a benchmark against which optimisation methods are still measured today.

A tour, and how many there are

A valid route that visits every city once and returns to the start is called a tour (a Hamiltonian cycle). Counting them is where the terror begins. Fix a starting city; there are (n-1)! orderings of the rest, and since a tour and its reverse have the same length, the number of distinct tours is:

\frac{(n-1)!}{2}.

For n = 5 cities that is a mere 12 tours — you could check them by hand. For n = 10 it is 181{,}440. For n = 20 it is about 6 \times 10^{16} — more tours than seconds since the dinosaurs. Factorials outrun every computer almost immediately: this combinatorial explosion is why brute force is hopeless and why the TSP is NP-hard.

The integer-programming formulation

We can still write the TSP exactly. Let c_{ij} be the distance from city i to city j, and let the binary variable x_{ij} = 1 mean "the tour uses the edge between i and j". Then:

Minimise the total length \displaystyle \sum_{i < j} c_{ij}\,x_{ij}.
Degree constraints — every city touches exactly two tour edges (one in, one out): \displaystyle \sum_{j} x_{ij} = 2 for every city i.
Subtour-elimination constraints — for every proper subset S of the cities, \displaystyle \sum_{i,j \in S} x_{ij} \le |S| - 1, which forbids the solution from breaking into several small disconnected loops.

The degree constraints alone would let the solver return, say, two separate triangles instead of one big loop — technically "two edges per city", but not a tour. The subtour-elimination constraints outlaw exactly that. There is a catch: there are 2^n subsets S, so there are exponentially many such constraints. Real solvers add them lazily — only when a solution actually contains a subtour — inside branch and bound.

Heuristics: good tours, fast

Because exact solving is expensive, practitioners lean on heuristics — methods that find a good tour quickly without proving it optimal. They come in two families.

Construction heuristics build a tour from scratch. The simplest is nearest neighbour: start somewhere, repeatedly hop to the closest city you have not yet visited, then close the loop. Improvement heuristics take an existing tour and polish it. The classic is 2-opt: find two edges that cross, delete them, and reconnect the two resulting paths the other way — which always un-crosses the tour and shortens it. Watch both in action on five cities:

Nearest neighbour, greedily hopping, produced the route A\!\to\!B\!\to\!D\!\to\!C\!\to\!E\!\to\!A of length \approx 21.6 — notice how edges B\text{–}D and C\text{–}E cross in the middle. One 2-opt move swaps that crossing pair for B\text{–}C and D\text{–}E, giving the tidy convex loop A\!\to\!B\!\to\!C\!\to\!D\!\to\!E\!\to\!A of length \approx 17.4 — a 19% saving from one swap. A crossing in a tour is always wasteful; 2-opt exists to hunt crossings down.

Lower bounds: how far from optimal are we?

A heuristic gives an upper bound on the optimal length (an actual tour). To know how good it is we also want a lower bound — a value the optimum cannot beat. Two classics:

Lower bound	Idea
Assignment relaxation	Drop the subtour constraints. What remains is the easy assignment problem; its optimum is a lower bound on the TSP.
MST / 1-tree bound	Deleting one edge from any tour leaves a spanning path, so a tour's length is at least the minimum-spanning-tree length; the sharper "1-tree" bound refines this.

If a nearest-neighbour tour measures 17.4 and a lower bound proves the optimum is at least 16.9, you know your tour is within about 3% of best — often good enough to ship without ever finding the true optimum. Squeezing the gap between a good tour (upper bound) and a good relaxation (lower bound) is the whole game of exact TSP solving.

Astonishingly big. Although the TSP is NP-hard, decades of work on cutting planes and branch-and-bound (the Concorde solver) have cracked instances that sound impossible: an 85,900-city chip-design problem was solved to proven optimality, and a tour of all 49,687 pubs in the UK was found and certified. NP-hard means the worst case blows up — it does not mean every large instance is unsolvable. Clever bounds routinely tame structured real-world instances that a naive factorial count says should take longer than the age of the universe.

Nearest neighbour is seductive because it is so simple and usually "looks" reasonable — but it can be arbitrarily bad. Greedily grabbing the closest city again and again leaves scattered far-flung cities stranded, forcing one or two enormous edges at the very end to mop them up. In the worst case a nearest-neighbour tour can be a logarithmic factor longer than optimal, and even on ordinary instances it is commonly 20–25% over. Treat it as a starting point to be improved by 2-opt or better — not as an answer. And never confuse a tour that "has no obvious crossings" with a proven optimum: 2-opt can get stuck in a local minimum that no single swap can escape.