|
|||||
  1.
Das Traveling-Salesman-Problem (TSP) |
|
Das Traveling-Salesman-Problem /
Travelling-Salesman-Problem (TSP), auch als
Rundreiseproblem oder Problem des Handelsreisenden (bzw.
Handlungsreisenden) bezeichnet, ist eines der berühmtesten Probleme
in der kombinatorischen Optimierung. Der Weltrekord einer optimalen Lösung von symmetrischen TSP liegt seit Mai 2004 vorläufig bei 24978 Orten. Beim früheren Rekord über 13509 Orte im Jahre 1998 hatten D.APPLEGATE, R.BIXBY und W.COOK (Rice University in Houston, Texas / USA) sowie V.CHVATAL (Rutgers University in New Brunswik, New Jersey / USA) mit Hilfe eines Clusters von drei Digital AlphaServer 4100s und eines Clusters von 32 Pentium-II PCs das Optimum berechnet. Die Berechnung dauerte drei Monate und basierte auf der Methode „Lineare Programmierung“. Untersucht man bekannte Optimallösungen von symmetrischen TSP mit vielen Orten, so stellt man fest, dass ausnahmslos alle TSP neben der Symmetrie außerdem als zusätzliche Spezialität die Ortsbezogenheit besitzen, d.h. es werden für jeden Ort die Koordinaten angegeben, aus denen sich dann die kürzeste Entfernung zwischen je zwei Orten berechnen läßt. Die Entfernungen entsprechen den Ausprägungen des interessierenden Merkmals, deren Summe zu minimieren ist. Die Verbindung zwischen zwei Orten besitzt somit nicht nur das Merkmal „Länge“, sondern außerdem implizit als zusätzliches Merkmal die „Lage im Raum“. Dieses zusätzliche Merkmal ist entscheidend dafür, dass unabhängig vom Wert der Länge bestimmte Verbindungen für die Lösung ausgeschieden werden können und so die Problemstellung enger wird. Kreuzt sich z.B. der Weg einer Rundreise, so wird das Ergebnis der Optimierung dadurch verbessert, dass die beiden sich überschneidenden Verbindungen der vier beteiligten Orte gegen zwei gegenüberliegende Verbindungen ausgetauscht werden. Der Austausch der Verbindungen erfolgt nicht wegen der Länge sondern wegen der örtlichen Lage der Verbindungen. Diese Fälle von raumbezogenen symmetrischen TSP kann man daher als gelöst ansehen. Anders verhält es sich für den allgemeinen Fall von symmetrischen TSP, bei denen keine zusätzlichen Merkmale für die Lösung herangezogen werden und die Ausprägungen des interessierenden Merkmals beliebige positive und negative Werte annehmen können. Alle bekannten Verfahren zur Ermittlung einer Optimallösung laufen auf eine vollständige Analyse der n! möglichen Rundreisen hinaus. Bis heute ist noch kein Algorithmus bekannt, der weniger als exponentiellen Zeitaufwand (bezogen auf die Anzahl der Orte) benötigt, um eine optimale Rundreise zu ermitteln. So sind nach herrschender Ansicht für symmetrische TSP strikt kombinatorische Lösungsansätze wie die enumerative Berechnung von symmetrischen Rundreisen mit 25 Orten nicht möglich. Mit der hier beschriebenen „ZIP-Methode“ lassen sich solche symmetrische Rundreisen enumerativ in kurzer Zeit optimal lösen. Symmetrische Rundreisen mit bis zu zehn Orten können mit der ZIP-Methode ggf. sogar ohne jedes Hilfsmittel gelöst werden. Grundsätzlich ist diese Methode auch auf nicht-symmetrische Rundreiseprobleme anwendbar. Die Grundidee ist allgemeiner Natur und schließt alle Spezialfälle ein. Inwieweit die ZIP-Methode einen Durchbruch für die optimale Berechnung von allgemeinen symmetrischen und nicht-symmetrischen TSP bedeutet, muss sich in der Zukunft erweisen. In jedem Fall wird die Grenze der Berechenbarkeit optimaler TSP nach oben verschoben. Die ZIP-Methode läßt sich sicherlich nicht nur auf die begrenzte Enumeration sondern auch auf andere Lösungsmethoden anwenden. Dazu enthalten die drei Beispiele eine Vielzahl von Anregungen für weitere Untersuchungen.
|