Das Travelling-Salesman-Problem (TSP) fragt nach der kürzesten Rundreise durch n Orte: Jeder Ort wird genau einmal besucht, am Ende kehrt man zum Ausgangspunkt zurück, und die Gesamtdistanz soll minimal sein. Trotz der einfachen Formulierung ist das Problem NP-schwer – die Entscheidungsvariante (gibt es eine Tour der Länge ≤ k?) ist NP-vollständig (Karp 1972).
Beispiel: Paketroute
Ein Kurier muss fünf Stadtteile anfahren und wieder zum Depot zurückkehren. Alle Reihenfolgen ausprobieren sind 5! = 120 Möglichkeiten; bei 20 Orten sind es bereits 20! ≈ 2,4 · 10¹⁸ – zu viele für erschöpfende Suche. Genau dafür sucht die TSP-Forschung clevere Verfahren.
Zusammenhang zum Hamiltonkreis
Eine TSP-Tour ist ein Hamiltonkreis mit minimalem Gesamtgewicht: Sie besucht jeden Knoten genau einmal und kehrt zum Start zurück. Ohne Gewichte ist die Frage „existiert überhaupt eine solche Tour?“ bereits NP-vollständig; das TSP verschärft das Problem um die Optimierung der Länge. Auch der Hamiltonpfad (Start und Ende verschieden) ist eng verwandt.
Lösungsansätze
- Exakt: Der Algorithmus von Held und Karp löst das TSP mit dynamischer Programmierung in O(n² · 2ⁿ) – für n bis etwa 20 bis 25 Orte praktikabel.
- Approximation: Für das metrische TSP (Dreiecksungleichung gilt) erreicht die Christofides-Heuristik das 1,5-Fache des Optimums; die doppelte Baumtour liefert die 2-Approximation. Details unter Approximationsalgorithmen.
- Heuristiken: In der Praxis dominieren lokale Suche (2-opt), Simulated Annealing, der Ameisenalgorithmus und weitere Metaheuristiken – sie liefern auch für tausende Orte sehr gute Touren.
Anwendungen
- Logistik und Routenplanung: Zustellung, Abholung, Tourenoptimierung
- Fertigung: Bohren von Leiterplatten und Schneiden von Blechen als TSP
- Bioinformatik: DNA-Fragment-Rekonstruktion (Sequencing by Hybridization)
Verwandte schwere Probleme im selben Themenkreis: Eulerkreis, Eulerpfad (Kantenvarianten, polynomial lösbar) und Satisfiability; die Komplexitätseinordnung liefert der Artikel NP-vollständig.