The problem
A courier has to stop at every point once and finish where they started, driving as little as possible. That is the travelling salesman problem. It sounds small until you count the routes: 10 points allow about 181,000 distinct loops, 20 allow about 6 × 1016, and 120 allow roughly 10196.
Nobody checks them all. Exact solvers prune the search cleverly, but when you want a good tour right now you build one with a heuristic and accept that it might be a little longer than the best possible loop.
How the tour grows
The tour starts as the convex hull: the rubber-band loop around the outside of the points. Everything else has to be pulled in. Instead of visiting points in some fixed order, the algorithm lets points and edges negotiate.
- Every candidate looks at every edge of the tour and picks the one it would stretch least. A candidate is a single point or an arc: a chain of up to a few nearby points.
- Every edge looks at every candidate and picks the one that would stretch it least.
- A pair is allowed only when the choices agree. The cheapest allowed pair is adopted: the edge breaks and the candidate is spliced in.
- Repeat until every point is in the tour.
There are no crossing tests, no inside-the-polygon tests and no area calculations anywhere. The only geometry is the starting hull. Every decision comes from one cost function, so changing what “cheap” means changes the whole behaviour. Arcs are compared per point, which lets a tidy chain of three points beat a lone point that merely fits.
Second thoughts
After each adoption, points and arcs adopted in earlier steps can be lifted back out and re-adopted into a different edge, in either direction, as long as the real tour gets shorter. A point moves at most once per step and hull points never move. When everything is adopted the same loop keeps running as a polish until nothing improves.
On screen, the edges an arc leaves behind flash purple and the arc itself turns orchid.
The final search
Once every point is in, the tour gets a short finishing search: 2-opt (swap two edges and reverse the stretch between them) and Or-opt (move a short run of points elsewhere), each limited to a point’s ten nearest neighbours. On its own that finds nothing. I checked 48 finished tours exhaustively and none had a single improving 2-opt move, because adoption and re-adoption already leave tours that are 2-opt-optimal.
What pays is a nudge. The search cuts two neighbouring stretches of the tour and swaps them at random, repairs the damage with 2-opt and Or-opt, and keeps the result only if the tour got shorter. It makes four nudges per point, which takes 10 to 50 milliseconds. Each kept improvement is a step in the animation: the edges that leave flash purple and the new ones glow.
Change what “cheap” means
The cost function is the only thing the construction cares about. Swap it under Algorithm, or start from one of these:
- Compressed detour, 60 points
- No re-adoption, 60 points
- Single points only
- 120 points in clusters
- The 12-point messy set
How it compares
I gave OR-Tools the same random instances: a path-cheapest-arc start, then guided local search for 3 + n/5 seconds, the settings from the original script. The table uses 8 instances per size (seeds 21 to 28) that I generated after the method was fixed, with the page’s default arc sizes.
| Points | Adoption only vs OR-Tools | With final search vs OR-Tools | Final search: shorter / equal | Time with final search | OR-Tools time |
|---|---|---|---|---|---|
| 30 | +0.40% | 0.00% | 0 / 8 of 8 | about 25 ms | 9 s |
| 60 | +0.54% | −0.58% | 3 / 5 of 8 | about 45 ms | 15 s |
| 120 | −0.15% | −2.71% | 8 / 0 of 8 | about 190 ms | 27 s |
With the final search the tour was never longer than OR-Tools’ on any of these 24 instances. It matched OR-Tools exactly at 30 points and was shorter on all 8 instances at 120 points, by 2.7% on average, in about a fifth of a second. This is one run per instance on one machine, not a rigorous study, and OR-Tools’ answer is not guaranteed optimal either.
The reference inside the visualiser is a stand-in. OR-Tools can’t run in a browser, so the page runs the same kind of search from a nearest-neighbour tour for a second or two. The finishing step uses the same method, so the gap shown beside the tour is small and can go either way.
Run it yourself
Everything is static files: index.html, a stylesheet and four modules in js/, with no build step. Serve the folder with python3 -m http.server and open localhost:8000. The original Python script, with its matplotlib animation and OR-Tools comparison, lives in tests/ next to the scripts that check the JavaScript port against it and produced the table above.