This simulation tackles the Travelling Salesman Problem (TSP): finding the shortest closed tour that visits every city exactly once and returns to the start. Cities are points on the canvas, and a tour's cost is the sum of Euclidean distances between consecutive stops. You can pit three classic heuristics against one another on the same layout: Nearest Neighbour (greedy), 2-opt local search, and Simulated Annealing.
The Cities slider (4 to 80) and New Cities button generate random layouts, while clicking adds a city, dragging moves one, and right-clicking deletes it. Choose an algorithm, set the Speed (steps per frame), and press Run; for Simulated Annealing the Start temp and Cooling sliders tune the search. TSP underpins logistics, vehicle routing, circuit-board drilling and DNA sequencing.
What is the Travelling Salesman Problem?
It asks for the shortest possible route that visits a given set of cities exactly once and returns to the origin. Here the cities are points on screen and distance is straight-line (Euclidean), so the goal is to minimise total tour length. It is one of the most studied problems in combinatorial optimisation.
Why is TSP considered hard?
TSP is NP-hard: no known algorithm solves it in polynomial time for the general case. The number of distinct tours grows as (n-1)!/2, so with 20 cities there are roughly 1.2 x 10^18 routes. Exhaustively checking every tour quickly becomes impossible, which is why heuristics are used.
What do the three algorithms do?
Nearest Neighbour builds a tour by always hopping to the closest unvisited city. 2-opt repeatedly reverses tour segments to remove crossings and shorten the route. Simulated Annealing swaps cities at random and sometimes accepts worse tours, gradually cooling so it settles into a good solution.
For each random swap it computes the change in tour length, delta. If delta is negative the move is always accepted. If delta is positive it is accepted with probability exp(-delta / T), where T is the current temperature. As T cools, uphill moves become rarer, so the search narrows from exploration to refinement.
Start temp sets the initial temperature T0 (the slider value times 500), governing how willing the search is to accept worse tours early on. Cooling sets the per-step multiplier alpha between roughly 0.9995 and 0.99995; values closer to 1 cool more slowly, giving a longer, more thorough search before the temperature drops near zero.
2-opt is a pure local search: it only accepts improving swaps, so it converges fast but can become trapped in a local optimum it cannot escape. Simulated Annealing accepts the occasional worse move, letting it jump out of such traps. On some layouts 2-opt's determinism wins; on others annealing's randomness finds a shorter tour.
Tour length is the current route's total distance; Best found is the shortest tour seen so far, drawn faintly in green. Iterations counts algorithm steps, Temperature shows the live annealing value of T, and Improvements counts how many moves actually reduced the tour length.
Speed selects how many algorithm steps run per animation frame, from 1 up to 20,000 at the highest setting, so you can watch slowly or converge quickly. The Step button advances exactly one iteration at a time, which is useful for studying how a single swap or reversal changes the tour.
No. All three methods are heuristics that aim for near-optimal tours, not provably shortest ones. Nearest Neighbour can be 25 percent or more above optimal; 2-opt and Simulated Annealing usually do much better but offer no guarantee. Finding the exact optimum for many cities requires far heavier exact-solver techniques.
TSP and its variants appear in parcel and delivery routing, drilling holes in printed circuit boards, scheduling telescope observations, planning DNA sequencing, and tool-path optimisation in manufacturing. The same swap-and-improve ideas shown here scale, with refinements, to industrial routing software handling thousands of stops.
Three algorithms compete on the same city set: Nearest Neighbour (greedy), 2-opt (local search) and Simulated Annealing (probabilistic). Drag cities or click to add new ones and watch routes optimise.
TSP asks: what's the shortest route visiting all cities exactly once? It's NP-hard — no known polynomial-time algorithm exists, but heuristics find near-optimal solutions.
Click to add cities. Drag to reposition them. Run all three algorithms and compare tour lengths. Watch Simulated Annealing escape local optima that trap 2-opt.
With just 20 cities, there are 20!/2 ≈ 1.2 × 10¹⁸ possible routes. The record exact solution for real TSP is 85,900 cities, computed in 2006 by Applegate, Bixby, Chvátal and Cook.