Das Traveling Salesman Problem

Der Kürzeste Weg?

Text?

Das Problem des Handlungsreisenden (engl. Traveling Salesman Problem, kurz TSP) ist ein kombinatorisches Optimierungsproblem. Hierbei geht es im Wesentlichen um die Suche der kürzesten Route über eine bestimmte Anzahl von Orten, die ein Handlungsreisender bestimmen will, bevor er die Reise antritt. Abstrahiert man dieses Problem mit Hilfe der Graphentheorie, so formuliert sich das Problem folgenderweise: Finde bei gegebener Anzahl von Knoten ( Orte ) und ihren durch eine Abstandsfunktion gegebenen Distanzen zueinander, die kürzeste Kantenfolge (Route) durch alle Knoten.

In der Praxis gibt es genügend Bereiche in denen dieses Problem auftritt. Beispielsweise in der Tourenplanung, in der Logistik oder im Design von Mikrochips. Noch häufiger tritt es allerdings als Unterproblem auf, wie z. B. bei der Verteilung von Waren, bei der Planung von Touren eines Kunden- oder Pannendienstes.

Das Problem des Handlungsreisenden kann exakt gelöst werden, indem man die Weglängen aller möglichen Rundreisen berechnet und dann eine mit der kleinsten Weglänge auswählt. Das ist aber schon bei einer kleinen Zahl von Städten nicht mehr praktisch durchführbar. Bei der einfachsten Variante, dem symmetrischen TSP mit n Städten, gibt es (n ? 1)! / 2 verschiedene Rundreisen, das sind bei 15 Städten über 43 Milliarden und bei 18 Städten bereits über 17 Billionen. Wie schnell die Rechenzeit mit wachsender Anzahl von Städten wächst zeigt das folgende Beispiel. Hat man einen Rechner, der die Lösung für 30 Städte in einer Stunde berechnet, dann braucht dieser für zwei zusätzliche Städte annähernd die tausendfache Zeit; das sind mehr als 40 Tage. Deswegen bedient man sich meistens versichedener Heuristiken, die dieses Problem zwar nicht exakt aber dafür schnell und fast genauso gut lösen.