Login für Redakteure
Traveling-Salesman Problem
gefördert im Rahmen eines Normalverfahrens:
10.2004 - 09.2006 und 10.2007 - 02.2010
Übersicht
Was ist das TSP?
Das Handelsreisendenproblem oder Traveling Salesman Problem (TSP) ist eines der meist studierten Probleme der kombinatorischen Optimierung. In einem gewichteten, vollständigen Graphen sucht man einen kürzesten, geschlossenen Weg, der jeden Knoten genau einmal durchläuft. Dabei unterscheidet man das symmetrische TSP (STSP), bei dem das Gewicht einer Kante immer gleich dem Gewicht der entgegengesetzten Kante ist, und das asymmetrische TSP (ATSP), bei dem diese Bedingung nicht immer erfüllt ist.
Welche Bedeutung hat das TSP?
TSP ist ein NP-schwieriges Problem und wird wegen seiner einfachen Formulierung und seiner praktischen Bedeutung dazu benutzt, verschiedene Methoden und Algorithmen miteinander zu vergleichen. Als etablierte Referenz gilt hierbei die TSPLIB mit Instanzen von 14 bis zu 85.900 Knoten, denen in der Regel reale Städteprobleme zugrunde liegen, und die VLSI TSP , die auf VLSI Schaltkreise zurückgehen. Obwohl es wenig Polynomialzeit-Algorithmen mit beweisbaren Approximationsschranken gibt, existieren viele gute Heuristiken. Die zur Zeit führenden Algorithmen sind für das STSP der exakte Branch-and-Cut-Algorithmus von
Applegate, Bixby, Chvátal, Cook und die von Helsgaun verbesserte Lin-Kernighan-Heuristik und für das ATSP der Branch-and-Bound-Algorithmus von Carpaneto, dell`Amico, Toth und die Contract-or-Patch-Heuristik von von Glover, Gutin, Yeo und Zverovich.
Was sind Toleranzen?
Ein wichtiger Ansatzpunkt zur Lösung eines TSP ist die Frage, welche Kanten mit hoher Wahrscheinlichkeit in einer guten Tour auftauchen bzw. welche nicht. Der Begriff der Toleranz ist hierfür ein sehr gutes Kriterium. Für das TSP ist die Toleranz folgendermaßen erklärt.
Sei eine feste (nicht notwendig eindeutige) optimale Tour gegeben.
- Die obere Toleranz einer Kante aus dieser optimalen Tour gibt an, um wieviel das Gewicht dieser Kante erhöht werden muss, sodass sie mindestens in einer optimalen Tour nicht enthalten ist.
- Die untere Toleranz einer Kante, die nicht zu dieser optimalen Tour gehört, bestimmt, um wieviel ihr Gewicht verringert werden muss, damit sie in mindestens einer optimalen Tour liegt.
Analog kann die Toleranz für Relaxationen des TSP wie minimal spannender Baum für das STSP und lineares Zuordnungsproblem und relaxiertes Zuordnungsproblem für das ATSP definiert werden.
Welches Ziel verfolgte das Projekt?
Anliegen des Projektes war es, neue Methoden zur schnelleren Lösung des TSP zu entwickeln und zu implementieren. Dazu sollten mögliche toleranzbasierte Kriterien zur Auswahl von Kanten genau analysiert und in Heuristiken sowie Branch-and-Bound-Algorithmen angewendet werden. Insbesondere sollte nachgewiesen werden, dass eine toleranzbasierte Auswahl von Kanten den üblichen auf Gewichten basierenden Auswahlverfahren überlegen ist. Da die Berechnung der Toleranzen zum TSP mindestens genau so schwer wie die Lösung des TSP-Problems selbst ist, verwendeten wir die Toleranzen bzgl. der oben aufgeführten zum TSP verwandten, in Polynomialzeit lösbaren Probleme. Zum Beispiel kann man erwarten, dass Kanten eines minimal aufspannenden Baumes des Graphen, die bzgl. dieses optimalen Baumes eine große obere Toleranz haben, also in gewisser Weise stabil in diesem minimalen aufspannenden Baum liegen, mit hoher Wahrscheinlichkeit auch in einer guten Tour des Graphen liegen.
Ein weiterer Arbeitspunkt bestand darin, Ansätze herauszuarbeiten, die ein hierarchisches Vorgehen erlauben, um so wirklich große TSP-Instanzen angehen zu können.
Wie entstand das Projekt?
Das Projekt wurde im September 2003 von Prof. Dr. Jop Sibeyn und Prof. Dr. Boris Goldengorin in Zusammenarbeit mit Dr. Holger Blaar bei der Deutschen Forschungsgemeinschaft (DFG) beantragt und im März 2004 für zwei Jahre bewilligt. Das Projekt wurde durch die DFG um zwei weitere Jahre verlängert (bis 2009). In den Zeitäumen von Oktober 2004 bis September 2006 und Oktober 2007 bis August 2009 arbeitete Dr. Gerold Jäger als hauptamtlicher wissenschaftlicher Mitarbeiter an diesem Projekt. Ab Juni 2005 hatte Prof. Dr. Paul Molitor die Projektleitung inne. Prof. Dr. Jop Sibeyn gilt seit einer Wanderung über das Eismeer in Schweden im März 2005 als vermisst.