Kandidatenmengen für das TSP

Das Traveling Salesman Problem (Problem des Handlungsreisenden, TSP) ist ein klassisches Problem des Operations Research. Die Planungsaufgabe besteht (vereinfacht) in der Ermittlung einer Rundreise minimaler Länge durch eine gegebene Anzahl Städte. Für das TSP existiert eine Fülle von kaufmännischen Anwendungen z. B. in der Logistik, der Maschinensteuerung, der Personaleinsatzplanung oder der Maschinenbelegungsplanung. Im Gegensatz zur leichten und eingängigen Formulierung des Problems erweist sich insbesondere seine exakte Lösung für relevante Problemgrößen als außerordentlich schwierig. Vor diesem Hintergrund hat sich die heuristische Lösung des TSP für Theorie und Praxis äußerst fruchtbar gezeigt. Aus praktischer Sicht können heute auch sehr große TSP in angemessener Zeit mit sehr guten – wenn auch nicht unbedingt optimalen – Ergebnissen gelöst werden. Allerdings wachsen die Größen der TSP mit der fortschreitenden technischen Entwicklung, so dass sich die TSP-Forschung immer neuen Herausforderungen zu stellen hat. Werden für ein großes TSP schnelle und gute Lösungen gesucht, liegt es nahe, die Suche nach der kürzesten Rundreise auf vielversprechende Wege zwischen den Städten zu beschränken, anstatt alle denkbaren Wege zwischen den Städten in Betracht zu ziehen. Eine solche vorab getroffene, beschränkte Auswahl an Wegen wird Kandidatenmenge oder Candidate Set genannt. Die vorliegende Arbeit stellt die Erzeugung und Verwendung von Kandidatenmengen im Zusammenhang mit der heuristischen Lösung einer konkreten Klasse von TSP umfassend dar und erweitert die Methoden zur Erzeugung von Kandidatenmengen um eine eigene, neue Methode. Diese neue Methode wird einer ausführlichen vergleichenden und kritischen empirischen Analyse unterworfen und zeigt sehr gute Ergebnisse.