Traveling Salesman Heuristics Screensaver
The Traveling Salesman Heuristics screensaver builds a real nearest-neighbor tour through random cities, then improves it live with real 2-opt swaps, steadily shortening the route. It is free, runs in your browser, and ESC exits.
Live preview
Press ESC to leave fullscreen. Settings are saved in your browser only.
How the Traveling Salesman Heuristics screensaver works
The saver scatters a real random set of cities, then builds an initial tour with the real nearest-neighbor heuristic.
It then runs real 2-opt improvement, testing pairs of tour edges and reversing a segment whenever that shortens the total tour length.
Each accepted improvement is drawn live, so you watch the tour visibly untangle and shorten over time.
Once no further 2-opt improvement shortens the tour, it holds briefly, then a fresh random set of cities and tour begins.
A famously hard problem and its practical shortcuts
The traveling salesman problem asks for the shortest closed route that visits each of a set of cities exactly once. It is simple to state and notoriously hard: the number of possible tours grows factorially, and the problem is NP-hard, even for cities in the Euclidean plane. Exact solvers do exist; in 2006 an optimal tour of an 85,900-city instance was computed with the Concorde solver, at a cost of over 136 CPU-years.
For this reason practitioners use heuristics. The nearest-neighbour rule builds a tour by always moving to the closest unvisited city, which is quick but, for randomly placed cities, gives a path about 25% longer than the shortest possible on average. The 2-opt method then improves the result: it removes two edges and reconnects the tour the other way, and keeps the change if the total gets shorter. In the plane, a tour with crossing edges can always be shortened, so 2-opt works by removing crossings.
The method stops at a local optimum, a tour that no single 2-opt move can shorten. That tour is not guaranteed to be optimal. Stronger methods such as Or-opt and Lin-Kernighan search more widely.
A worked example
A crossing pair of tour edges gets uncrossed by a real 2-opt reversal, visibly shortening the route the moment the swap is applied.
Settings & tips
- Accent recolours the current tour path.
- The cities and starting tour are real and randomized every run.
- A fresh set of cities generates automatically once improvement stalls.
Frequently asked questions
- Does this find the perfect shortest route?
- No — the traveling salesman problem is real and famously hard; this uses real, practical heuristics that get close, not guaranteed-optimal.
- What is 2-opt?
- A real, classic local-search move that reverses a tour segment whenever doing so shortens the total route.
- Is a key needed?
- No — it is a pure local computation.
- Is it free?
- Yes — free, no download, in your browser.
- Why can't a computer just try every route?
- The number of routes grows factorially. Even a modest number of cities has more tours than could be checked in any practical time.
- Why do crossing edges mean a tour is not optimal?
- In a plane, uncrossing two edges that cross always shortens the total length, so a shortest tour can never contain a crossing.
- What is a local optimum?
- It is a solution that cannot be improved by any single allowed move, though a better solution may still exist elsewhere.