Problem des Handlungsreisenden

Das Traveling Salesman Problem (oft TSP genannt) ist ein klassisches algorithmisches Problem aus dem Bereich der Informatik und des Operations Research. Es ist auf Optimierung ausgerichtet. Bessere Lösung bedeutet in diesem Zusammenhang oft eine Lösung, die billiger, kürzer oder schneller ist. TSP ist ein mathematisches Problem. Es lässt sich am einfachsten in Form eines Graphen ausdrücken, der die Positionen einer Menge von Knoten beschreibt.

Das Problem der Handlungsreisenden wurde in den 1800er Jahren von dem irischen Mathematiker W. R. Hamilton und dem britischen Mathematiker Thomas Kirkman definiert. Hamiltons Icosian Game war ein Erholungsrätsel, das auf der Suche nach einem Hamilton-Zyklus basierte. Die allgemeine Form des TSP scheint erstmals in den 1930er Jahren von Mathematikern in Wien und in Harvard untersucht worden zu sein, insbesondere von Karl Menger. Menger definiert das Problem, betrachtet den offensichtlichen Brute-Force-Algorithmus und beobachtet die Nichtoptimalität der Heuristik des nächsten Nachbarn:

Wir bezeichnen als Botenproblem (da diese Frage in der Praxis von jedem Postboten, jedenfalls auch von vielen Reisenden, gelöst werden sollte) die Aufgabe, für ﬁnitely viele Punkte, deren paarweise Entfernungen bekannt sind, den kürzesten Weg zu finden, der die Punkte verbindet. Natürlich ist dieses Problem durch endlich viele Versuche lösbar. Regeln, die die Anzahl der Versuche unter die Anzahl der Permutationen der gegebenen Punkte drücken würden, sind nicht bekannt. Die Regel, dass man zuerst vom Startpunkt zum nächstgelegenen Punkt gehen soll, dann zum nächstgelegenen Punkt usw., ergibt im Allgemeinen nicht den kürzesten Weg.

Hassler Whitney an der Universität Princeton führte bald darauf das Problem des Namens Reiseverkäufer ein.

William Rowan Hamilton

Ein Verkäufer möchte alle Städte A, B, C und D besuchen. Wie kann er dies am besten erreichen (billigste Flugtickets und minimale Reisezeit)?

Optimale Route eines Verkäufers, der die 15 größten Städte in Deutschland besucht. Die dargestellte Route ist die kürzeste der 43.589.145.600 möglichen Routen.

Darstellung des Problems

Das Travelling Salesman Problem beschreibt einen Verkäufer, der zwischen N Städten reisen muss. Die Reihenfolge, in der er dies tut, ist ihm egal, solange er jede Stadt während seiner Reise einmal besucht und dort ankommt, wo er zuerst war. Jede Stadt ist durch nahe gelegene Städte oder Knotenpunkte, durch Flugzeuge, Straßen oder Eisenbahnen mit anderen Städten verbunden. Jede dieser Verbindungen zwischen den Städten ist mit einem oder mehreren Gewichten (oder den Kosten) versehen. Die Kosten beschreiben, wie "schwierig" es ist, diese Kante im Diagramm zu überqueren, und können z.B. durch die Kosten für ein Flug- oder Zugticket oder vielleicht durch die Länge der Kante oder die für die Überquerung benötigte Zeit angegeben werden. Der Verkäufer möchte sowohl die Reisekosten als auch die Entfernung, die er zurücklegt, so gering wie möglich halten.

Das Traveling Salesman Problem ist typisch für eine große Klasse "harter" Optimierungsprobleme, die Mathematiker und Informatiker seit Jahren faszinieren. Am wichtigsten ist, dass es Anwendungen in Wissenschaft und Technik hat. Zum Beispiel ist es bei der Herstellung einer Leiterplatte wichtig, die beste Reihenfolge zu bestimmen, in der ein Laser Tausende von Löchern bohren wird. Eine effiziente Lösung für dieses Problem senkt die Produktionskosten für den Hersteller.

Schwierigkeit

Im Allgemeinen ist das Problem der Handlungsreisenden schwer zu lösen. Wenn es einen Weg gibt, dieses Problem in kleinere Komponentenprobleme zu zerlegen, werden die Komponenten mindestens so komplex wie das ursprüngliche Problem sein. Dies ist das, was Informatiker als NP-harte Probleme bezeichnen.

Viele Menschen haben sich mit diesem Problem beschäftigt. Die einfachste (und teuerste) Lösung ist, einfach alle Möglichkeiten auszuprobieren. Das Problem dabei ist, dass Sie für N Städte (N-1) faktorielle Möglichkeiten haben. Das bedeutet, dass für nur 10 Städte über 180.000 Kombinationen auszuprobieren sind (da die Startstadt definiert ist, kann es für die restlichen neun Kombinationen Permutationen geben). Wir zählen nur die Hälfte, da jede Route eine gleiche Strecke in umgekehrter Richtung mit der gleichen Länge oder den gleichen Kosten hat. 9! / 2 = 181 440

Mit Hilfe von Branch- und Bound-Algorithmen können exakte Lösungen für das Problem gefunden werden. Dies ist derzeit für bis zu 85.900 Städte möglich.
Heuristische Ansätze verwenden eine Reihe von Leitregeln für die Auswahl des nächsten Knotens. Da Heuristiken jedoch zu Approximationen führen, werden sie nicht immer die optimale Lösung liefern, obwohl zulässige Heuristiken von hoher Qualität eine nützliche Lösung in einem Bruchteil der Zeit finden können, die für eine vollständige Brute-Force-Lösung des Problems erforderlich ist. Ein Beispiel für eine Heuristik für einen Knoten wäre eine Summierung, wie viele nicht besuchte Knoten sich "in der Nähe" eines verbundenen Knotens befinden. Dies könnte den Verkäufer dazu anregen, eine Gruppe von nahe beieinander liegenden Knoten zu besuchen, die zu einem Cluster zusammengefasst sind, bevor er sich zu einem anderen natürlichen Cluster im Diagramm begibt. Siehe Monte-Carlo-Algorithmen und Las-Vegas-Algorithmen

Fragen und Antworten

F: Was ist das Traveling Salesman Problem?

A: Das Traveling Salesman Problem (TSP) ist ein klassisches algorithmisches Problem aus dem Bereich der Informatik und des Operations Research. Es konzentriert sich auf die Optimierung, wobei bessere Lösungen oft billigere, kürzere oder schnellere Lösungen bedeuten.

F: Wie wird das TSP ausgedrückt?

A: TSP lässt sich am einfachsten als Graph ausdrücken, der die Positionen einer Reihe von Knoten beschreibt.

F: Wer hat das TSP zuerst definiert?

A: Das Traveling Salesman Problem wurde in den 1800er Jahren von dem irischen Mathematiker W. R. Hamilton und dem britischen Mathematiker Thomas Kirkman definiert.

F: Wer hat es in den 1930er Jahren weiter untersucht?

A: In den 1930er Jahren untersuchten die Mathematiker Karl Menger in Wien und Harvard das Problem weiter.

F: Was hat Hassler Whitney kurz darauf eingeführt?

A: Hassler Whitney von der Princeton University führte kurz nach der Definition des Problems den Namen "Traveling Salesman Problem" ein.

F: Was bedeutet "bessere Lösung" in diesem Zusammenhang?

A: In diesem Zusammenhang bedeutet "bessere Lösung" oft eine Lösung, die billiger, kürzer oder schneller ist.

F: Welchen Algorithmus hielt Menger bei der Untersuchung des TSP für naheliegend?

A: Menger betrachtete bei der Untersuchung von TSP einen offensichtlichen Brute-Force-Algorithmus und stellte fest, dass die Heuristik des nächsten Nachbarn nicht immer optimale Ergebnisse liefert.