Problem des Handlungsreisenden
Das Problem des Handlungsreisenden (kurz PdH, englisch Traveling Salesman Problem bzw. mittlerweile politisch korrekt Traveling Salesperson Problem genannt, kurz TSP) ist ein recht alltägliches Problem. Es modelliert die Frage, wie man möglichst schnell oder billig mehrere Orte hintereinander besuchen kann und wieder zum Ausgangsort zurückkehrt.
Aus theoretischer Sicht wird häufig nur der Fall zugelassen, dass jeder Ort nur einmal besucht wird. In der Praxis gestattet man meist Orte mehrmals zu besuchen, wodurch die Reise günstiger werden kann. Dadurch kann man das Problem immer so modellieren, das der zugrundeliegende Graph metrisch wird, dass heißt drei Knoten erfüllen stets die Dreiecksungleichung. Dies ist besonders für die algorithmischen Lösung des Problems vorteilhaft.
Modellierung des Problems als Graph
Um das Problem graphentheoretisch zu beschreiben, werden die zu besuchenden Orte sowie der Ausgangsort als Knoten eines Graphen interpretiert. Zwischen je zwei Knoten werden gerichtete Kanten eingefügt, wenn zwischen ihren korrespondierenden Orten ein Weg existiert. Es kann dabei vorkommen, dass nur ein Weg in eine Richtung existiert (zum Beispiel bei einer Einbahnstraße) oder zwischen zwei Orten gar kein Weg vorhanden ist.
Die Kanten erhalten ein Gewicht, das den Kosten entspricht, die entstehen, wenn man den Weg in entsprechender Richtung nutzt, der zwischen den korespondierenden Orten existiert. Hier kann es auch vorkommen, dass die Kanten in entgegengesetzter Richtung zwischen zwei Knoten unterschiedliches Gewicht enthalten. Gibt es mehrere Wege zwischen zwei Orten, so würde man in der Praxis natürlich immer den billigsten wählen. Daher trägt man in diesem Fall natürlich auch das kleinste entsprechende Gewicht an einer Kante ein.
Für den Fall, dass Orte mehrfach besucht werden dürfen, kann man aus dem so entstandenen Graphen einen Distanzgraphen bilden. Dieser hat die Eigenschaft metrisch zu sein. Durch mehrfache Anwendung des Algorithmus von Dijkstra berechnet man dabei zwischen allen Paaren von Knoten den kürzesten Weg und bildet einen vollständigen kantengewichteten gerichteten Graphen, wobei die Kantengewichte die Länge der entsprechenden kürzesten Wege bilden. Voraussetzung ist hierbei natürlich, dass der ursprüngliche Graph stark zusammenhängend ist. Dies ist aber insofern keine Einschränkung, als dass auch eine Rundreise nur unter dieser Bedingung existiert.
Graphentheoretische Beschreibung
In gerichteten Graphen mit Kantengewichten bezeichnet man einen Hamiltonkreis, also einen Kreis, der alle Knoten miteinander verbindet als Traveling-Salesman-Tour. Das Problem, zu einem solchen Graphen zu entscheiden, ob eine Traveling-Salesman-Tour der Länge höchstens k existiert, wobei k eine beliebige reelle Zahl ist, bezeichnet man als Problem des Handlungsreisenden (PdH). Neben diesem Entscheidungsproblem gibt es noch das Optimierungsproblem das kleinste k zu bestimmen, für das eine Traveling-Salesman-Tour der Länge k existiert und das Suchproblem eine kürzeste Traveling-Salesman-Tour zu finden. Eine Traveling-Salesman-Tour kann nur existieren, wenn der Graph stark zusammenhängend ist. Diese Eigenschaft lässt sich aber relativ leicht in linearer Zeit prüfen (siehe Zusammenhang von Graphen).
In der Praxis betrachtet man häufig nur metrische Graphen G=(V,E,f), in denen also die Kantengewichtsfunktion f die Dreiecksungleichung erfüllt, dass heißt für drei beliebige verschiedene Knoten x, y, z aus V gilt f((x,y))+f((y,z))≥f((x,z)). Der Distanzsgraph zu einem stark zusammenhängenden gerichteten Graphen besitzt immer diese Eigenschaft.
Beschränkt man sich auf Graphen, in denen diese Bedingung erfüllt ist, so spricht man vom metrischen Problem des Handlungsreisenden. Zwei Speziallfälle sind das euklidische Problem des Handlungsreisenden und das rektilineare Problem des Handlungsreisenden. Diese Fälle liegen vor, wenn es eine Funktion gibt, die den Knoten des Graphen einen Punkt in der euklidischen Ebene zuordnet, so dass die Kantengewichte gerade dem Abstand der zugeordneten Punkte in der Ebene nach 2-Norm (für euklidisches PdH) bzw. 1-Norm (für rektilineares PdH) entsprechen.
Algorithmische Komplexität
Das Problem des Handlungsreisenden ist NP-vollständig. Die Optimierungs- und Suchvariante sind NP-äquivalent. Daran ändert sich nichts, wenn man sich auf das metrische PdH oder sogar noch spezieller auf das euklidische oder rektilineare PdH beschränkt. Für das metrische PdH gibt es aber verschiedene polynomielle Algorithmen (Heuristiken).
Die einfachste Heuristik ist die so genannte Nähester-Nachbar-Heuristik (englisch auch Nearest-Neighbor-Heuristik), die bei einem beliebigen Knoten beginnend den jeweils am nähesten noch nicht besuchten Nachbarn aufsucht und so eine Traveling-Salesman-Tour generiert. Die Güte der so erzeugten Tour kann aber beliebig schlecht werden.
Für das metrische PdH gibt es zwei Approximationsalgorithmen. Die Minimum-Spanning-Tree-Heuristik -- kurz auch MST-Heuristik genannt -- liefert eine Approximationsgüte mit dem Faktor 2, dass heißt die gefundene Traveling-Salesman-Tour ist höchstens doppelt so lang wie die kürzeste. Dazu berechnet sie zunächst einen minimal spannenden Baum und erzeugt dann einen Umlauf um diesen (Verdopplung der Kanten, finden einer Eulertour in dem entstandenen eulerschen Graphen und ersetzen benachbarter Kanten, falls ihr gemeinsamer Nachbar in der Eulertour mehr als einmal besucht wird).
Noch bessere Approximationsgüte liefert die Cristofides-Heuristik, die eine Tour berechnet, die höchstens 1,5 mal so lang wie die kürzeste Tour ist. Hierbei wird statt der Verdopplung der Kanten zusätzlich zur MST-Heuristik eine kleinste perfekte Paarung auf den Knoten ungeraden Grades im minimal spannenden Baum berechnet, um einen eulerschen Graphen zu erzeugen. Dieser Algorithmus ist aber komplizierter und langsamer.
Meilensteine gelöster Probleme
Jahr Forscher Probleminstanz ---------------------------------------------------------- 1954 Dantzig, Fulkerson, Johnson 49 Städte 1971 Held, Karp 64 Städte 1975 Camerini, Fratte, Maffioli 100 Städte 1977 Grötschel 120 Städte 1980 Crowder, Padberg 318 Städte 1987 Padberg, Rinaldi 532 Städte 1987 Grötschel, Holland 666 Städte 1987 Padberg, Rinaldi 2.392 Städte 1994 Applegate, Bixby, Chvátal, Cook 7.397 Städte 1998 Applegate, Bixby, Chvátal, Cook 13.509 Städte 2001 Applegate, Bixby, Chvátal, Cook 15.112 Städte