TSP-Metaheuristiken live
About this app
Bis zu 500 Städte in der Ebene, im Raum oder auf dem Globus mit echten Weltstädten: neun Startverfahren vom Nächsten Nachbarn bis zur Hilbertkurve, 2-opt, Or-opt und 3-opt bis ins lokale Optimum, dann Simulated Annealing, Tabusuche, genetischer Algorithmus, Ameisenkolonie, iterierte lokale Suche, Zerstören & Reparieren und elastisches Netz. Jeder Zug ist sichtbar, der Verlauf misst die Tour an der Held-Karp-Schranke. Eigene Städte setzen und löschen.
With explain mode: an AI tutor walks you through the app, points out what matters in the scene and answers your questions.
What it is about
The travelling salesman problem (TSP) asks for the shortest tour that visits each city exactly once and returns. With n cities there are (n − 1)!/2 tours, so trying them all is impossible beyond a few dozen cities. In practice one first builds a start tour quickly and improves it with local moves such as 2-opt until no move helps. This local optimum is usually not the global one. Metaheuristics such as simulated annealing, tabu search, genetic algorithms or ant colonies get out of such valleys again.
What the app shows
Up to 500 cities on a map, freely in space or on a globe with real world cities, where edges are great-circle arcs. Nine start heuristics, from nearest neighbour via insertion methods and the spanning tree to the Hilbert curve, build their tour visibly step by step. 2-opt, Or-opt and 3-opt show every move: removed edges dashed, new ones coloured. Seven metaheuristics run live: the temperature in annealing, forbidden edges in tabu search, the population in the genetic algorithm, the pheromone trails of the ants, the kicks of iterated local search, ruin & recreate and an elastic net. The chart measures every tour against the Held–Karp lower bound.
Try it yourself
Let 2-opt run to the end: the tour then has no crossings left and is still a few per cent above the bound. Then start simulated annealing and watch the length first rise and, as it cools, fall lower than before. Place your own cities in the plane or delete some, and the running tour adapts at once. With the speed slider you go move by move or tens of thousands of steps per second. The magnifier explains every part of the scene.
Frequently asked questions
- What is 2-opt for the travelling salesman problem?
- 2-opt is a local improvement move: two edges of the tour are removed and reconnected crosswise, and the piece between them is traversed in the opposite direction. The move is made only if it shortens the tour. 2-opt stops when no such move exists; the tour then has no crossings in the plane but is in general not optimal.
- How does simulated annealing escape a local optimum?
- Simulated annealing also accepts moves that lengthen the tour, with probability e to the power of minus the worsening divided by the temperature. At first the temperature is high and many worsenings are accepted; it falls slowly until almost only improvements pass. So the search can leave valleys before it commits.
- How do you measure the quality of a TSP solution without the optimum?
- With a lower bound. The Held–Karp bound computes 1-trees (a minimum spanning tree plus two edges at one city) and raises them with weights on the cities. No tour can be shorter; if a tour is 3 % above it, it is at most 3 % worse than the optimum.
- Can I place my own cities in the app?
- Yes, in the plane: cities can be moved, added and deleted. A new city is inserted at the cheapest position of the running tour, and a running method continues with the changed map.
Subject: Operations research: DP & heuristics
More from Operations research: DP & heuristics
A VisuApp by heyprof: interactive, free in your browser, no sign-up. What is a VisuApp? · All apps