The Travelling Salesman Problem: NP-Hard, in Practice

A problem that sounds simple and is not

The travelling salesman problem asks for the shortest route that visits every city exactly once and returns to the start. For n cities there are (n−1)!/2 distinct possible tours (dividing by 2 for direction, by convention fixing a start city), which grows so explosively that checking every tour by brute force is only realistic for a dozen or so cities — 15 cities already means over 43 billion tours. TSP is NP-hard: no algorithm is known that solves every instance to guaranteed optimality in time that scales polynomially with n, and most complexity theorists believe none exists. That does not mean the problem is hopeless in practice — it means exact answers become expensive, so real solvers trade a small amount of optimality for a huge amount of speed.

Nearest Neighbour: fast, greedy, and provably imperfect

The simplest heuristic starts at any city and repeatedly travels to the nearest unvisited city until none remain, then returns to the start. It runs in O(n²) time and is trivial to implement, but it is short-sighted: an early greedy choice can strand the tour far from cities it still has to visit late, and it can be proven that nearest neighbour tours can be arbitrarily worse than optimal in the worst case. In practice on typical city layouts it lands 20–30% above the optimal tour length — a usable starting point, not a final answer.

2-opt: untangling crossed edges

2-opt takes any tour and repeatedly looks for two edges that cross or that could be swapped to shorten the total length: remove two edges, reconnect the two resulting path segments the other possible way, and keep the change if it shortens the tour.

for each pair of edges (i, i+1) and (j, j+1) in the tour, i < j:
  newLength = length with segment [i+1 .. j] reversed
  if newLength < currentLength: apply the reversal
repeat until no improving swap exists (a local optimum)

Applied on top of a nearest-neighbour start, 2-opt typically closes most of that 20–30% gap, often landing within a few percent of optimal on moderate-size instances. Its weakness is that it is a local search: it stops at the first tour where no single 2-opt swap helps, which is not necessarily the global optimum — it can be stuck in a local minimum surrounded by worse tours in every 2-opt-reachable direction.

Simulated Annealing: escaping local optima on purpose

Simulated Annealing (Kirkpatrick, Gelatt & Vecchi, 1983) borrows its acceptance rule from statistical mechanics: at each step, propose a random small change to the tour (like a 2-opt swap), and accept it if it improves the tour — but also accept it with some probability even if it makes the tour worse, where that probability depends on how much worse the move is and on a temperature parameter that decreases over the course of the run.

T = T0
while T > Tmin:
  candidate = randomSwap(currentTour)
  delta = length(candidate) - length(currentTour)
  if delta < 0 or random() < exp(-delta / T):
    currentTour = candidate      // accept, sometimes even if worse
  T *= coolingRate               // e.g. 0.995 per step

Early on, when T is high, the algorithm accepts many worsening moves and effectively explores broadly, jumping out of local optima that would trap 2-opt alone; as T cools, it accepts fewer and fewer worsening moves and settles into refinement, behaving more and more like plain 2-opt near the end of the run. Given a slow enough cooling schedule, simulated annealing is guaranteed to converge to the global optimum in the limit — a guarantee that is more theoretical than practical, since a slow enough schedule can take longer than brute force, but at practical cooling rates it reliably outperforms 2-opt alone on the same instance.

What this site's live race is actually showing

Watching the three run on the same city set makes their trade-offs visible directly: nearest neighbour finishes first and worst, 2-opt finishes second and settles into a visibly untangled but static tour, and simulated annealing keeps visibly perturbing its tour even after 2-opt has gone still — that continued wandering, occasionally making a tour briefly longer, is exactly the mechanism that lets it find shorter tours than 2-opt reaches alone.

Frequently asked questions

Try it live

Everything above runs in your browser — open Travelling Salesman and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.