Travelling Salesman Problem

Travelling Salesman Problem (TSP) ist das Stammproblem der kombinatorischen Optimierung der Operations Research: gegeben N Knoten und eine paarweise Kostenmatrix (Distanz, Zeit oder Geld), finde die geschlossene Tour, die jeden Knoten genau einmal besucht, mit minimalen Gesamtkosten. Formal NP-schwer, in der Praxis durch Branch-and-Cut auf sehr große Skala exakt bis zum Optimum lösbar — der Solver der Forschungsgruppe Princeton-Georgia Tech hat 85K+-Knoten-Instanzen gelöst (Applegate, Bixby, Chvátal und Cook 2006); die Heuristik LKH (Helsgaun 2000) bleibt bis Millionen-Knoten-Skala innerhalb 0,1-1% am Optimum. Varianten: symmetrisches TSP (Distanz A→B = B→A), asymmetrisches TSP (ATSP, richtungsabhängige Distanz), Euklidisches TSP, metrisches TSP (Dreiecksungleichung, Christofides-3/2-Approximationsgarantie), TSP mit Profiten. Grundlegende Quellen: Dantzig, Fulkerson und Johnson (1954) für den Cutting-Plane-Durchbruch; Lin und Kernighan (1973) für die kanonische Heuristik; Held und Karp (1962) für die O(n²·2^n)-DP-Formulierung. TSP ist das strukturelle Rückgrat der gesamten Vehicle-Routing-Familie (VRP) — VRP, VRPTW und PDPTW sind Erweiterungen des TSP um Kapazitäts-, Zeitfenster- und Paarungsbedingungen.