Problem des Handlungsreisenden
Das Problem des Handlungsreisenden (englisch traveling salesman problem) ist sicher ein Problem, das viele Personen aus dem Alltag kennen. Es modelliert die Frage, wie man möglichst schnell oder billig mehrere Orte hintereinander besuchen kann und wieder zum Ausgangsort zurückkehrt. In der Praxis wird man dabei auch zulassen, Orte mehrmals zu besuchen, wenn die Reise dadurch günstiger wird. Die für ein allgemeines PdH gegebene Einschränkung, jeden Ort genau einmal zu besuchen, ist also eher künstlich. Indem man gestattet Orte mehrmals zu besuchen, kann man das Problem immer als metrisches PdH modellieren (man bildet einfach den Distanzgraphen und ersetzt in einer Lösung die Kanten des Distanzgraphen durch die Pfade des Originalgraphen). Wie unten dargestellt, ist dies vorteilhaft bei der algorithmischen Lösung des Problems.Praktisch einsetzbare Lösungsverfahren für das Problem des Handlungsreisenden werden innerhalb des Gebietes Operations-Research und als Approximationsalgorithmen erarbeitet.
Graphentheoretische Beschreibung
In vollständigen Graphen mit Kantengewichten bezeichnet man einen Hamiltonkreis 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) bzw. engl Traveling-Salesman-Problem, inzwischen politisch korrekt traveling salesperson problem, kurz TSP. 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.
In der Praxis betrachtet man häufig nur Graphen, in denen die Kantengewichtsfunktion f die Dreiecksungleichung erfüllt, d.h. für drei beliebige verschiedene Knoten x, y, z aus V gilt f({x,y})+f({y,z})≥f({x,z}). Solche Graphen nennt man auch metrisch. Beschränkt man sich auf Graphen, in denen diese Bedingung erfüllt ist, so spricht man vom metrischen Problem des Handlungsreisenden bzw. metrischen Traveling-Salesman-Problem. Zwei Speziallfälle sind das euklidische Problem des Handlungsreisenden bzw. euklidische Travelings-Salesman-Problem und das rektilineare Problem des Handlungsreisenden bzw. rectilineare Traveling-Salesman-Problem. 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.
Graphen mit Mehrfachkanten werden hier nicht betrachtet, da es offensichtlich nicht auf die Vielfachheit der Kanten ankommt.
Graphentheoretische Probleme und ihre algorithmische Komplexität
Das Problem des Handlungsreisenden ist in all seinen Varianten (Entscheidungs-, Optimierungs- und Suchproblem) NP-schwer. (Das Entscheidungsproblem ist außerdem NP-vollständig.) Es bleibt selbst dann NP-schwer, wenn man sich auf metrisches PdH oder sogar noch spezieller auf euklidisches oder rektilineares PdH beschränkt. Es gibt aber verschiedene polynomielle Algorithmen (Heuristiken) für das Problem.
Die einfachste Heuristik ist die so genannte Nächster-Nachbar-Heuristik (manchmal 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 metrisches PdH gibt es zwei bessere Heuristiken. Die Minimum-Spanning-Tree-Heuristik kurz auch MST-Heuristik genannt, liefert eine Approximationsgüte mit dem Faktor 2, d. h. 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 besser ist die Cristofides-Heuristik mit Approximationsgüte 1,5. 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.
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