Travelling Salesman

About

A salesperson must visit every city once and return home. Which order is shortest? The travelling salesman problem (TSP) is easy to state and famously hard to solve: the number of possible tours through n cities is (n−1)!/2. For 10 cities that is 181,440 tours. For 40 cities it is about 10⁴⁶, more than any computer could ever enumerate.

So practical solvers stop asking for the perfect answer and start asking for a good one fast. This lab lets you race the classic families of ideas: build a tour greedily, improve it locally, escape local optima with randomness, or evolve a population. Brute force is there too, for small maps, so you can see what "optimal" really costs.

The same ideas plan delivery routes, drill paths for circuit boards, telescope observation schedules and the order a genome assembler stitches fragments. They also power local search across AI, from scheduling to neural architecture search. The Search and Optimization lesson explains the theory, and the Pathfinding lab shows the other side: problems where exact search is affordable.

How the algorithms work

Nearest neighbour: build greedily

Start at the home city (the one with a ring). Repeatedly travel to the closest city not yet visited, then return home. It is fast, O(n²), and usually lands within about 25% of optimal on random maps. Its weakness shows at the end: the last few cities are whatever was left over, joined by long, crossing edges.

2-opt: fix crossings until none are left

Take any tour and scan every pair of edges. If swapping them (the move on the right) shortens the tour, do it. Repeat until a full pass finds nothing. The result is a local optimum: no single 2-opt move helps, though a better tour may still exist. It has no crossings, because a crossing can always be removed by a 2-opt move.

Simulated annealing: sometimes accept worse

Propose a random 2-opt move. If it helps, take it. If it makes the tour longer by Δ, take it anyway with probability e^(−Δ/T). The temperature T starts high, so almost anything goes, and shrinks geometrically, so the search settles. Early randomness lets it climb out of local optima that trap plain 2-opt. The idea borrows from metallurgy, where slow cooling lets atoms find a low-energy crystal.

Genetic algorithm: breed tours

Keep a population of tours. Each generation, pick parents by tournament (the shorter of a few random tours wins), combine them with order crossover (copy a slice of one parent, fill the rest in the other parent's order, so every city appears once), occasionally reverse a random segment as mutation, and carry the two best tours over unchanged. Watch the gap between the population mean and the best: when it closes, the population has converged.

Brute force: check everything

Fix the home city and enumerate every ordering of the rest, skipping each tour's mirror image. That leaves (n−1)!/2 tours, all checked. Exact, and hopeless beyond a dozen or so cities.

Why it is hard

The TSP is NP-hard: nobody knows an algorithm that always finds the optimum in time polynomial in n, and finding one would settle the P versus NP question. Yet the problem is far from hopeless in practice. Exact solvers based on linear programming and branch-and-cut, such as Concorde, have proved optimal tours for instances with tens of thousands of cities, and heuristics such as Lin-Kernighan routinely get within a few percent of optimal on millions.

That gap between worst-case theory and everyday practice is the core lesson of optimisation in AI. Most real problems are huge but structured. Good heuristics exploit that structure, and good engineers measure how far from optimal they are rather than assuming.

Compare the numbers the lab gives you. On a 40-city random map, nearest neighbour typically sits noticeably above what 2-opt or a well-cooled annealer reaches. The genetic algorithm, run without any local search, is usually the weakest of the four: pure crossover struggles to preserve good sub-routes. Serious evolutionary TSP solvers combine crossover with 2-opt or Lin-Kernighan.

Try this

1. 01Watch greed go wrongRun nearest neighbour on 60 random cities. Look at the last few edges it adds. Then run 2-opt and watch it remove exactly those crossings first.
2. 02Brute force for realChoose 8 or 9 cities and run brute force. When it finishes, the tour is proven optimal. Then run the heuristics on the same map and read their gaps in the runs table.
3. 03Cool too fastSet annealing steps to the minimum and run twice; then to the maximum. Compare the temperature chart with the length chart: most improvement happens in a narrow temperature band.
4. 04Clusters change the gameTry the clustered preset. Good tours visit each cluster once. Nearest neighbour often leaves a cluster and has to come back later.
5. 05Evolution needs timeRun the genetic algorithm with mutation at 0 and then at 0.4. Without mutation the population mean collapses onto the best tour and progress stalls.
6. 06Circles are easyUse the circle preset with 80 cities. The optimum is known because the cities are in convex position. Does 2-opt always reach it?