Toolgeist › Math & Unit

Travelling Salesman Solver — Shortest Route Through Points, Visualised

Click stops onto the map and see the shortest round trip through them, drawn live. The tool runs nearest neighbour and cheapest insertion, improves each with 2-opt, and — up to 15 stops — computes the provably shortest route with the Held–Karp algorithm, so every other method’s distance is shown as an exact percentage above optimal. Beyond 15 stops it computes a 1-tree lower bound that no route can beat, which turns the percentage into a guaranteed ceiling on how far from optimal the route can be. On random 12-stop problems we tested, nearest neighbour averaged 13% longer than the best route, while adding 2-opt brought that to about 1%.

How to use Travelling Salesman Solver — Shortest Route Through Points

  1. Click the map to add stops, or load random points or a circle.
  2. Compare the lengths of the five methods in the table.
  3. Click a row to draw that method’s route.
  4. Add more than 15 stops to see the lower bound take over from the exact answer.

Frequently asked questions

What is the travelling salesman problem?
Find the shortest route that visits every stop exactly once and returns to the start. It is easy to state and famously hard to solve exactly: the number of possible routes grows factorially, and no known algorithm solves every case quickly.
Why is "always go to the nearest stop" not good enough?
Nearest neighbour is greedy: it makes good local choices, then leaves stops stranded far apart and forces a long trip back. On random 12-stop problems we tested it averaged 13% longer than the optimum; cheapest insertion averaged about 5%.
What does 2-opt do?
It takes two legs of the route and reconnects them the other way round whenever that is shorter, and repeats until nothing improves. Any route that crosses itself can be shortened this way, so the result never crosses. In our tests it brought the average to about 1% above optimal and found the exact best route roughly two times in three.
Why does exact solving stop at 15 stops?
The Held–Karp algorithm’s work roughly doubles with every extra stop. In our browser tests, 16 stops already took a fifth to a third of a second to recompute, enough to make every click on the map lag, so exact solving stops at 15 and the guaranteed lower bound takes over beyond that.
What is the lower bound?
A 1-tree: the minimum spanning tree over all stops but one, plus the two shortest connections to that stop, maximised over which stop is left out. Every possible round trip is at least this long, so "at most X% over optimal" is a guarantee, not an estimate.
Can I use it for real delivery or road trips?
Only as a model. It uses straight-line distances; real driving distances, one-way streets, traffic and time windows change the answer.

Related Math & Unit tools

Also searched for: travelling salesman solver online · tsp solver · shortest route through multiple points · 2-opt algorithm visualization · held karp algorithm

Browse all 738 free tools on Toolgeist →