loading...
running...
How to use
Choose a layout and the number of cities, pick an algorithm and watch the tour improve. Click the map to add a city, shift-click to remove one, drag a city to move it and see how the solver reacts. Solve exact runs dynamic programming for 13 cities or fewer. Compare Annealing with 2-opt on clustered towns, change the cooling factor and see the trade-off between speed and quality.
Experiments: (1) run 2-opt from a random start and from nearest neighbour; (2) on the circle layout every sensible solver should reach the polygon perimeter; (3) use the grid layout: many different tours have the same optimal length; (4) slow the annealing cooling and watch the gap shrink.
The relief map with rivers, forests and mountains, the towns, the depot warehouse and the delivery truck (with spinning wheels) were modelled in Blender 5.2 with baked PBR textures and exported as a Draco GLB. The route, the truck's position and the city markers are driven by the same solver as the 2D page.
The science
The travelling salesman problem asks for the shortest closed route that visits every city once. With n cities there are (n-1)!/2 distinct tours, so exhaustive search is hopeless beyond about a dozen cities; practical solvers trade optimality for speed.
Nearest neighbour always drives to the closest unvisited city: fast, typically 20 to 25 % above optimal. 2-opt repeatedly picks two edges (a,b) and (d,e) and replaces them by (a,d) and (b,e) if that shortens the tour; the gain is
gain = d(a,b) + d(d,e) - d(a,d) - d(b,e)
and the tour is 2-opt optimal when no pair has a positive gain. Simulated annealing proposes random 2-opt reversals and accepts a worsening of length Δ with the Metropolis probability exp(-Δ / T), while the temperature T falls by a factor each move; early on it escapes local minima, at the end it behaves like greedy 2-opt. The genetic algorithm keeps a population of tours, selects parents by tournament, builds children by order crossover (a slice of one parent plus the remaining cities in the other parent's order) and occasionally reverses a segment.
How good is a tour? Two reference numbers are shown. The 1-tree lower bound removes one city, takes the minimum spanning tree of the rest and adds the two shortest edges at the removed city; every tour is at least that long, so the gap above it is an upper limit on how far from optimal you are. For uniformly random cities in an area A the optimal length approaches 0.7124 sqrt(n A) (Beardwood-Halton-Hammersley), a useful sanity check. For up to 13 cities the page can run the exact Held-Karp dynamic programme, O(2^n n^2), and report the true gap.
Simplifications. Distances are straight-line (Euclidean) in a 100 km square; there are no roads, one-way streets, time windows, vehicle capacities or terrain costs. In the 3D page the relief map is for looks and for the truck's height: the cost model is the same planar distance as in the 2D page, so both pages give identical numbers.
In-page checks. (1) Held-Karp equals brute force over all orderings for 9 cities. (2) The 1-tree bound lies between 80 and 100 % of the exact optimum. (3) 2-opt on cities in convex position reaches the polygon perimeter 2nR sin(pi/n). (4) A converged tour has no improving 2-opt move. (5) The incrementally updated length agrees with a full recomputation. (6) Annealing beats nearest neighbour and respects the lower bound.