Traveling-Salesman Problem
gefördert durch die DFG im Rahmen eines Normalverfahrens
(Laufzeit: 01.10.2004 - 31.12.2006, 01.05.2007 - 30.04.2009)
Übersicht
Nachrichten
Neue "Weltrekorde" bei TSP-Benchmark-Instanzen
[ letzte Änderung: 15.08.2008 ]
Im Rahmen des DFG-Projektes "Bessere Methoden zum Lösen des Handelsreisendenproblems" konnten neue beste Touren für die Benchmarkgraphen
- FNA52057 (52057 Städte / Tourlänge 147.789 / 15.08.2008),
- SRA104815 (104.815 / 251.350 / 08.08.2008),
- ARA238035 (238.025 / 578.808 / 08.08.2008),
- *XIB32892 (32.892 / 96.760 / 21.07.2008),
- *BNA56769 (56.769 / 158.084 / 14.07.2008),
- ISC39603 (39.603 / 106.820 / 14.07.2008),
- FYG28534 (28.534 / 78.562 / 14.07.2008),
- BBY34656 (34.656 / 99.159 / 30.06.2008),
- BOA28924 (28.924 / 79.622 / 30.06.2008),
- IDO21215 (21.215 / 63.517 / 23.06.2008),
- PBA38478 (38.478 / 108.318 / 27.05.2008),
- #PJH17845 (17.845 / 48.092 / 05.05.2008),
- FNC19402 (19.402 / 59.287 / 01.04.2008),
- XVB13584 (13.584 / 37.083 / 28.03.2008)
- *FHT47608 (47.608 / 125.120 / 20.03.2008),
- *FRH19289 (19.289 / 55.799 / 22.10.2006),
- XSC6880 (6.880 / 21.535 / 24.05.2006),
gefunden werden. Die meisten dieser Touren konnten mit einem Ansatz, der die von Keld Helsgaun implementierte Lin-Kernighan Heuristik (LKH) um eine Backbone Kontraktion erweitert bzw. einen verbesserten Partitionierungsalgorithmus verwendet, gefunden werden, die übrigen durch eine geschickte Wahl der Parameter der LKH.
(Legende: *: alter Weltrekord; #: Weltrekord eingestellt)
Pseudo-Backbonekanten der TSP-Benchmark-Instanz nrw1379
Kontrahierte Pseudo-Backbonekanten der Instanz
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 verfolgt das Projekt?
Anliegen des Projektes ist es, neue Methoden zur schnelleren Lösung des TSP zu entwickeln und zu implementieren. Dazu sollen mögliche toleranzbasierte Kriterien zur Auswahl von Kanten genau analysiert und in Heuristiken sowie Branch-and-Bound-Algorithmen angewendet werden. Insbesondere soll 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, verwenden 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 Punkt besteht 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. Seit Oktober 2004 arbeitet Dr. Gerold Jäger als hauptamtlicher wissenschaftlicher Mitarbeiter an diesem Projekt. Seit Juni 2005 hat 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.
Die DFG hat im Januar 2007 den Antrag auf Verlängerung des Projektes bis 2009 positiv beschieden.
Gruppenfoto