Travelling Salesman: Algorithms in Competition
NP-hard in practice — three heuristics head to head
What is the Travelling Salesman Problem?
Picture a delivery driver who has to visit 20 addresses in the morning and be back at the depot by evening. Which order saves the most fuel?
Sounds simple — but it isn't. Even with a handful of stops there are more possible routes than a human could ever try out. That is exactly the question the Travelling Salesman Problem (TSP) poses.
Analogy:
Picture a delivery driver who has to visit 20 addresses in the morning and be back at the depot by evening. Which order saves the most fuel?
Sounds simple — but it isn't. Even with a handful of stops there are more possible routes than a human could ever try out. That is exactly the question the Travelling Salesman Problem (TSP) poses.
Definition:
Formally: find the shortest closed tour that visits each of n cities exactly once and returns to the start. TSP is NP-hard — no method is known that is guaranteed to find the optimal solution for arbitrarily large instances in reasonable time.
The number of possible tours grows as (n-1)!/2. That is why in practice we rely on heuristics: methods that quickly find very good — though not provably perfect — solutions.
Why is this so hard?
The hard part of TSP is not computing the length of a tour — that is instant. The problem is the combinatorial explosion: the number of possible tours grows faster than our intuition can grasp.
| Cities | Possible tours | Brute-force time |
|---|---|---|
| 5 | 12 | a fraction of a second |
| 10 | 181.440 | a fraction of a second |
| 15 | 4.4 × 10^10 | 44 seconds |
| 20 | 6.1 × 10^16 | 2 years |
| 25 | 3.1 × 10^23 | 9.8 × 10^6 years |
This is exactly where heuristics come in: instead of trying everything, they search cleverly — and find near-optimal routes in seconds.
The three strategies
Three very different ways of thinking compete against each other. Watch how they behave in the demo:
Always picks the nearest unvisited city. Lightning fast and often usable — but easily paints itself into a corner because it never looks back. A pure one-shot solution.
Simulated Annealing mimics the slow cooling of metal: while it is hot, it occasionally accepts a worse route to escape local valleys. The cooler it gets, the pickier it becomes.
The Genetic Algorithm keeps an entire population of routes. The best ones are crossed and mutated — like in evolution, the shortest tours win out over generations.
Interactive Demo
What the map shows
Dots on a map, joined into one round trip. A tangled zigzag turns, step by step, into a short, smooth loop around every dot.
- What you see
- A map with scattered dots — the places. A faint web hints that every place could be linked to every other. On top lies the current round trip as a coloured line that joins all the dots into one closed loop.
- What happens
- At first the line darts back and forth across the map and crosses itself often. During optimisation the crossings come undone, the route grows smoother and settles almost neatly around every dot. Several methods run at once, each drawing its own coloured route.
- What you can do
- Pick a region or drop your own dots on the map. Start the methods, step forward one move at a time, or pause. Click dots to draw your own round trip and race the methods. Use the selector to show or hide single methods, and zoom or drag to move the map.
- What to watch for
- There are unimaginably many possible round trips — far too many to try them all. Watch how the methods still cleverly land on a short route: every crossing that disappears is a stretch of saved travel.
Controls
Click cities to also draw your own route and race the algorithms. Clicking empty space places a new city.
What does this have to do with AI?
TSP is the prototype of combinatorial optimisation — and that class of problems shows up everywhere in AI where the best option must be chosen from astronomically many possibilities.
The core idea stays the same: when exhaustive search is impossible, we search cleverly. Simulated Annealing and Genetic Algorithms are universal tools far beyond the TSP.
Traveling Salesman Problem — the algorithm
The most famous touring problem
A traveling salesman must visit every city exactly once and return to the start — on the shortest possible round trip. That sounds harmless, but it is one of the most studied problems in computer science. The same structure hides in parcel routes, in drilling circuit boards, in steering telescopes, and even in genome sequencing.
Why it is so hard
With n cities there are (n−1)!/2 distinct round trips. For 10 cities that is 181,440 — manageable. For 20 cities it is already around 6 × 10^16, more than any computer could sensibly check. Formally precise: the decision variant of the TSP (is there a tour shorter than L?) is NP-complete, and the optimization variant (find the shortest tour) is NP-hard. No algorithm is known that solves every instance exactly in polynomial time — and one exists exactly if P = NP.
Three strategies racing each other
The demo pits three fundamentally different heuristics against each other:
- Nearest Neighbor (greedy): Always go to the nearest unvisited city. Finished in a flash, but the last connections often turn out expensive — typically 10 to 25 percent above the optimum.
- Simulated Annealing: Starts with a random tour and changes it locally (2-opt: reverse a segment). Deteriorations are sometimes accepted at high temperature — this lets the search escape local minima. As the temperature drops, the tour freezes.
- Genetic Algorithm: A whole population of tours evolves across generations — tournament selection, order crossover, mutation. The best tour is guaranteed to survive (elitism).
- Held-Karp (reference): Exact optimum via dynamic programming in O(2^n · n²) — computable in the demo only up to 12 cities. That is exactly why you can see there how close the heuristics really get.
No guarantee — and still useful
All three methods are heuristics: they usually deliver good, but never guaranteed optimal, solutions. Simulated Annealing and the Genetic Algorithm are also stochastic — two runs can end differently. For the metric TSP there are approximation algorithms with a provable bound (Christofides 1976: at most 1.5 times the optimum), yet in practice good heuristics beat this guarantee by far.
Play with the demo! Push the city slider up and watch the number of tours explode. Let the methods race on a map with at most 12 cities — then the demo knows the exact optimum as the finish line. Turn up the cooling rate or turn down the mutation rate and watch who wins.
1832: A handbook for traveling salesmen
A German booklet titled Der Handlungsreisende — wie er sein soll und was er zu thun hat ("The Traveling Salesman — What He Should Be and What He Has to Do") already describes the problem in practical terms: anyone visiting customers in many cities should plan their route wisely. A mathematical treatment did not yet exist at the time.
1930s: The problem gets a name
The Viennese mathematician Karl Menger formulated the related messenger problem around 1930 and already noted that brute-force testing of all routes is practically impossible — and that the obvious nearest-neighbor rule does not always deliver the shortest tour. At Princeton University the name Traveling Salesman Problem spread during this period, among others through Hassler Whitney.
1954: Dantzig, Fulkerson and Johnson
George Dantzig, Ray Fulkerson and Selmer Johnson solved an instance with 49 US cities provably optimally — using linear programming and cleverly chosen cutting planes. Their method remains the foundation of every exact TSP solver to this day.
1962–1976: Theory sharpens
In 1962 Michael Held and Richard Karp (and independently Richard Bellman) showed the Held-Karp algorithm: exact optimum via dynamic programming in O(2^n · n²) — better than brute-force (n−1)!/2 checking, but still exponential. In 1972 Karp proved the NP-completeness of the Hamiltonian cycle problem, which also makes the TSP decision variant NP-complete. In 1976 Nicos Christofides delivered the famous approximation algorithm with a factor of 1.5 for the metric TSP.
Today: Concorde and millions of cities
The solver Concorde provably solved an instance with 85,900 points (a chip layout) optimally in 2006. For million-city instances, heuristics like Lin-Kernighan deliver tours that provably lie only a fraction of a percent above the known lower bound. The TSP remains the testbed against which new optimization ideas are measured.
1
# Traveling Salesman Problem — three strategies racing each other
2
# Wanted: shortest round trip through all cities, back to the start
3
# Careful: (n-1)!/2 possible tours — for 20 cities ~ 6 × 10^16
4
5
function tsp_race(cities):
6
# ---- Strategy 1: Nearest Neighbor (greedy) ----
7
tour = [start_city]
8
while there are unvisited cities:
9
last = last city of tour
10
nearest = unvisited city with smallest distance(last, city)
11
append nearest to tour
12
greedy_best = length(tour) # lightning fast — but rarely optimal
13
14
# ---- Strategy 2: Simulated Annealing ----
15
current = random tour; T = 100 # starting temperature
16
repeat while T > 0.001:
17
# neighbor tour: reverse a segment (2-opt) or swap two cities
18
candidate = two_opt(current)
19
delta = length(candidate) - length(current)
20
# always take an improvement — take a deterioration only with luck
21
if delta < 0 or random() < exp(-delta / T):
22
current = candidate
23
if length(current) < sa_best:
24
sa_best = length(current) # always remember the best tour
25
T = T * 0.995 # cool down slowly and freeze
26
27
# ---- Strategy 3: Genetic Algorithm ----
28
population = 50 random tours
29
repeat per generation:
30
# elitism: the best tour is guaranteed to survive
31
new_population = [best tour of population]
32
while new_population is not full:
33
parent1 = tournament_selection(population)
34
parent2 = tournament_selection(population)
35
child = mutate(crossover(parent1, parent2)) # order crossover
36
add child to new_population
37
population = new_population
38
if shortest tour of population < ga_best:
39
ga_best = shortest tour of population
40
41
# ---- Reference: exact optimum (only for small n) ----
42
if count(cities) <= 12:
43
optimum = held_karp(cities) # dynamic programming, O(2^n · n²)
44
# for large n the exact optimum is practically unreachable
45
46
return best tour found
47
# note: heuristics guarantee NO optimum — only good approximations
🧨 The combinatorial explosion
With n cities there are (n−1)!/2 distinct round trips. Ten cities: 181,440 tours — still testable. Twenty cities: around 6 × 10^16 — even a computer running a billion tours per second would need almost two years. Testing every tour is out of the question; we need smarter strategies.
# Traveling Salesman Problem — three strategies racing each other
# Wanted: shortest round trip through all cities, back to the start
# Careful: (n-1)!/2 possible tours — for 20 cities ~ 6 × 10^16
🗺️ Cities and tour space
n cities with distances — and (n−1)!/2 possible round trips. Exhaustive testing is already out of the question at medium n.
🏃 Greedy start
Nearest Neighbor immediately builds a first tour: always to the nearest unvisited city. Fast, but rarely optimal.
🌡️ Cooling down and improving
Simulated Annealing deforms the tour via 2-opt. Setbacks are allowed at first; as the temperature drops, the tour freezes.
🧬 Evolving the population
The Genetic Algorithm combines good tours through selection, crossover and mutation across many generations.
🏁 Best tour
The shortest tour found wins the race. Up to 12 cities, Held-Karp shows the exact optimum as a reference — the heuristics deliver no guarantee.
Key takeaways
- NP-hard: Already at 20 cities there are over 10^17 possible tours — exhaustive search is hopeless even for a supercomputer.
- Heuristics, not the optimum: Greedy, Simulated Annealing and Genetic Algorithms find very good routes in seconds — without guaranteeing it's the shortest.
- Each strategy thinks differently: Greedy greedily grabs the nearest point, Simulated Annealing initially accepts detours too, and the Genetic Algorithm breeds a whole population of routes.
- Everywhere in AI: the same combinatorial optimisation underlies logistics, chip design, genome sequencing and the hyperparameter search of neural networks.
Test your knowledge
Why can't we solve TSP for many cities by simply trying out all tours?
1. Why can't we solve TSP for many cities by simply trying out all tours?
- ☐ A) Because the number of possible tours explodes as (n-1)!/2
- ☐ B) Because computers can't compute distances
- ☐ C) Because the shortest route is always ambiguous
- ☐ D) Because there is no unique starting point
2. What does Simulated Annealing do while the temperature is high?
- ☐ A) It also accepts worse routes to leave local optima
- ☐ B) It only accepts improvements
- ☐ C) It keeps a population of solutions
- ☐ D) It always picks the nearest neighbour
3. What is the typical weakness of the Greedy strategy (nearest neighbour)?
- ☐ A) It never looks back and easily ends up in a dead end
- ☐ B) It is far too slow
- ☐ C) It needs a large population
- ☐ D) It only works for cities arranged in a circle
4. Do these heuristics guarantee the optimal solution?
- ☐ A) No — they quickly find very good, but not provably optimal tours
- ☐ B) Yes, always the mathematical optimum
- ☐ C) Only Greedy guarantees the optimum
- ☐ D) Only for fewer than 100 cities
Related Content
Article
The Path to the Valley: Gradient Descent
How gradient descent finds the lowest point in a landscape with millions of hills — most of the time.
Graph Search — The Beginnings
Graph search: the first thing AI could actually do — and still useful today.
Heuristics & Pathfinding: From Dijkstra to A*
How A* works — and why Dijkstra gets boring without a heuristic.
MinMax & Pruning
MinMax in practice: think backwards, assume the worst opponent, shortcut where possible.
What Is an Algorithm?
What Euclid, IKEA instructions, and Google search have in common — all three are algorithms.
Demo
Swarm Intelligence (Boids)
See how three simple local rules give rise to the complex behavior of a bird flock.
Evolution (Optimization)
Interactive demonstration of evolutionary optimization with mutation, selection, and crossover operators
Gradient Descent
Interactive demo to understand gradient descent: click a starting point on the loss landscape, watch the algorithm roll into the valley, and experiment with learning rate and optimizers.
MinMax (Game Theory)
Experience game theory hands-on: Play against an AI and watch how it calculates the optimal move.
Neuroevolution
Watch virtual cars learn to drive using neural networks and genetic algorithms - or take the wheel yourself and challenge the AI
Pathfinding (Graph Search)
Interactive visualization of pathfinding algorithms like A*, Dijkstra and more