aldus.nexus
travelling salesman

Travelling salesman

Picking a city

Visit every stop once and come home on real streets. Five solvers race; then draw your own tour and see how you rank.

Loading
Reading the list of city maps.

Drag to pan, scroll or pinch to zoom. Place stops or draw your own tour from the controls above.

The numbers

tour length against moves weighedlog scale
annealing: cooling% of start
ant colony: pheromoneper round
finish line-

Draw your own tour

?no tour yet

Start at the home stop (the diamond), tap every other stop in order and the van drives you home. Undo with Z.

    Your best on these stops: none yet.

    Tune the racers

    Changes rerun the solvers on the same stops; the street distances are kept.

    How it works

    A salesman has to call at every stop once and come home, by the shortest drive. Easy to say, and one of the most famous hard problems in computing: there is no known way to find the best tour that does not, in the worst case, blow up exponentially with the number of stops. With n stops there are (n - 1)! / 2 different round trips (each loop can start anywhere and run either way), so 12 stops already give about 20 million and 40 stops about 10⁴⁶. The decision version (is there a tour shorter than L?) is NP-complete, which is why real delivery software leans on clever heuristics rather than certainty.

    Distances here are real. For each stop the page runs Dijkstra's algorithm over the city's street graph, stopping once every other stop is settled, and keeps both the distance and the streets it used, exactly as on shortest path (and the pathfinding playground races the same searches). That gives an n × n matrix, and every leg is drawn along the streets it really follows. On the driving network one-way streets make it lopsided: from A to B is often not the same as from B to A. That is the asymmetric travelling salesman problem, with (n - 1)! directed tours rather than half that, and every solver here weighs legs in the direction it drives them. Walking streets go both ways, so walking tours are symmetric. The trip planner strings walks between pinned places in the order you give it; this page finds the order.

    The racers

    Nearest neighbour is pure greed: from wherever you are, drive to the closest stop not yet visited. It is quick and usually within 15 to 25% of the best, but it paints itself into corners and pays for a long drive home.

    2-opt starts from a random tour and looks at every pair of legs: remove both, reconnect the two pieces the other way round (which reverses the stretch between them) and keep it if the tour gets shorter. On a map that is exactly uncrossing an X. It always takes the best swap available and stops when no swap helps, at a local optimum.

    Or-opt polishes the greedy tour instead: lift a run of one, two or three stops out and slot it into another gap, keeping their order, whenever that saves distance. Because nothing is reversed it is natural for one-way streets.

    Simulated annealing borrows from metal cooling. It proposes random reversals and relocations; better tours are always kept, and worse ones are kept with chance e^(-Δ/T). Hot, it wanders freely and escapes local optima; as T falls geometrically it settles. The yellow flashes on its map are accepted uphill moves.

    Ant colony optimisation sends out a swarm of virtual ants. Each builds a tour stop by stop, choosing the next stop with probability that grows with the pheromone already on that leg and with how short it is. After each round the trails evaporate a little and every ant lays pheromone in proportion to how good its tour was, so short legs glow brighter and the colony converges.

    For 15 stops or fewer the page also runs the Held-Karp dynamic programme, which is exact: the shortest path that starts at home, visits a set S of stops and ends at j, built up from smaller sets. It costs about 2ⁿ n² steps instead of n!, fine for 15 stops (a few million) and hopeless for 40 (over 10¹⁵). That is the dashed white tour, and every gap is measured against it; above 15 stops gaps are against the best tour found.

    The race is run once in a Web Worker and replayed. Its clock counts moves weighed (candidate legs or swaps looked at) on a log scale, so greedy finishes early, 2-opt and or-opt next, and the annealer and the ants keep searching longest.

    A problem a child can state and nobody can solve fast, and yet a few lines of greed, swapping, cooling and pheromone get within a whisker of perfect.

    tours = (n - 1)! / 2symmetric round trips through n stops; (n - 1)! when one-way streets make A→B ≠ B→A
    Δ = d(a,c) + d(b,d) - d(a,b) - d(c,d)2-opt gain test: swap legs a→b and c→d for a→c and b→d; on one-way streets add the change from driving b…c backwards
    P(accept) = min(1, e^(-Δ/T))Metropolis rule for annealing: Δ is the change in tour length (m), T the temperature (m), cooled each proposal by T ← c·T with c just under 1
    p(i→j) = τᵢⱼ^α ηᵢⱼ^β / Σₖ τᵢₖ^α ηᵢₖ^βant colony choice over unvisited k: τ pheromone, η = 1 / d(i, j), α and β weigh trail against distance
    τᵢⱼ ← (1 - ρ) τᵢⱼ + Σ Q / Lₐevaporate by ρ, then each ant a lays Q / Lₐ on the legs of its tour of length Lₐ
    C(S, j) = min over i ∈ S of C(S - j, i) + d(i, j)Held-Karp: shortest route from home through set S ending at j; O(2ⁿ n²) time