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 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.