The Travelling Salesman problem (\(\mu\))

Combinatorics
Algorithms
Discrete maths
Optimisation

In the image below you can see a route that starts at Analemma and ends at this stop. Suppose you wanted to identify the route that goes through the same set of stops but minimises the total distance travelled.

This is the Travelling Salesman Problem (TSP) – one of the most famous problems in mathematics and computer science. It sounds simple: just try every order of stops and keep the shortest. With 5 stops there are only 12 distinct routes to check. With 10 stops there are already 181,440. With 20 stops there are over 60 quadrillion – so many that a computer checking a billion routes every single second would still need about two years to get through them all. Trying every option, which works fine for a handful of stops, becomes hopeless almost immediately – and no computer, however fast, escapes that by brute force alone.

Real versions of this problem sit behind delivery route planning, circuit board drilling, and DNA sequencing.

The app below shows nine of the trail stops: √ Analemma (fixed as your start) and μ Travelling Salesman (fixed as your end), plus seven stops in between – Ω Tree Height, ≤ Königsberg, ≥ Curvature, Σ Bird Song, ≠ Symmetry, φ Fibonacci and ∅ Helicopter Seeds. Tap those seven, in whichever order you think gives the shortest route from start to end, then use the toggle in the sidebar to compare:

With seven stops to order there are 5040 possible routes in total – still few enough for a computer to check every single one in an instant, which is exactly what the app does for the optimal route. Switch between the two and see how close your guess got.

Plan the middle leg
Your route always starts at √ and ends at μ Travelling Salesman. Tap the seven stops in between (Ω, ≤, ≥, Σ, ≠, φ, ∅), in whatever order you think gives the shortest route.
Figure 12.1: Tap the seven middle stops on the map above to build your route, then switch the sidebar toggle to compare it with the optimal one.