Travelling Salesman: Algorithms in Competition

NP-hard in practice — three heuristics head to head

Try it

Interactive Demo

Your task
Visit every city exactly once and return to the star on the shortest possible path.
Click on the field to place cities
Focus:Choose which strategy is highlighted. "All" lets Greedy, Simulated Annealing and the Genetic Algorithm race side by side.
Leaderboard
Press Start — the three algorithms race here.
Relative distance, no fixed scale.
Place at least 3 cities to start.

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
Run
How fast the search runs — purely visual. Slow to watch, fast to fast-forward; the result stays the same.
YouClick the cities one after another to draw your own tour. Only once you've visited all of them does your length count — and you race the algorithms.

Click cities to also draw your own route and race the algorithms. Clicking empty space places a new city.

Cities
Tip: drag to pan the map, scroll to zoom.
Display
Advanced parameters
How adventurous Simulated Annealing starts out. Higher = it accepts more detours early on to escape local valleys.
How fast the temperature drops. Closer to 1 = slower cooling, a more thorough search, but it needs more patience.
How many routes the Genetic Algorithm keeps in the race at once. More = a more diverse search, but slower per generation.
How often a route is randomly altered. Some mutation adds diversity; too much destroys good solutions.

Definition

What is the Travelling Salesman Problem?

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.

Note

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.

Possible tours
181,440
for 10 cities — (n-1)! / 2
Trying every tour would be done here in under a second — with this few cities, brute force is not yet a problem.
The explosion in numbers (at one billion tours per second)
CitiesPossible toursBrute-force time
512a fraction of a second
10181,440a fraction of a second
154.4 × 10^1044 seconds
206.1 × 10^162 years
253.1 × 10^239.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.

Three very different ways of thinking compete against each other. Watch how they behave in the demo:

Greedy

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

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.

Genetic Algorithm

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.

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.

Logistics & supply chains Route planning for parcel services, waste collection and field sales — billions saved by tours that are just a few percent shorter.
Chip design Wiring microchips means routing millions of connections as short as possible — the same optimisation problem in a different guise.
Genome sequencing Assembling DNA fragments into the correct order can be formulated as a TSP variant.
Machine learning Hyperparameter search, feature selection and training neural networks are all searches for the optimum in huge spaces — the very same metaheuristics apply.

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.

TheoryHistoryPseudocodeStep by StepFlow Diagram

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.

Note

Key takeaways

  1. NP-hard: Already at 20 cities there are over 10^17 possible tours — exhaustive search is hopeless even for a supercomputer.
  2. Heuristics, not the optimum: Greedy, Simulated Annealing and Genetic Algorithms find very good routes in seconds — without guaranteeing it's the shortest.
  3. 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.
  4. Everywhere in AI: the same combinatorial optimisation underlies logistics, chip design, genome sequencing and the hyperparameter search of neural networks.

Check

Test your knowledge

Why can't we solve TSP for many cities by simply trying out all tours?

Select one answer

Answer Key: 1) A · 2) A · 3) A · 4) A
Fascinated by Genetic Algorithms?
See in the evolution demo how solutions develop over generations through mutation and selection.

Plain Language

This preview is in Plain Language. The whole portal is also available in Plain Language. You can change the language at the top. Or use the button below. Our Plain Language texts are AI-assisted and editorially reviewed. They follow the core principles of easy-to-read language, but they are not certified Easy Read: a review panel of people with learning difficulties does not test them.

Preview: The Shortest Round Trip Through Cities

What does the demo show?

A delivery driver has to visit many cities. At the end, the driver comes back to the start. Which order is the shortest? Even with 20 cities, there are a huge number of routes. No computer can try them all.

How to use the demo

Place cities on the map. Then draw your own route. After that, three calculation methods compete against you. One always takes the nearest city. One copies cooling metal. One copies evolution.

What you learn

These methods are called heuristics. A heuristic is a smart rule of thumb. It quickly finds a very good route. But it doesn't promise the best route. Rules of thumb like these help with many hard tasks.