Auf Toleranzen basierende Methoden zur Lösung des Handelsreisendenproblems

Das Handesreisendenproblem (TSP) ist eines der meist studierten Probleme der kombinatorischen Optimierung und gilt aus Sicht der Komplexitätstherorie als Inbegriff eines schwierig zu lösenden Problems. Die Faszination des TSP liegt vor allem im Kontrast zwischen seiner extrem einfachen Formulierung und der enormen Schwierigkeit, dieses Problem zu lösen. Es ist nicht zu erwarten, dass es Algorithmen gibt, die das TSP für alle möglichen Eingaben in vernünftiger Zeit exakt lösen. Deswegen hat man eine Vielzahl heuristischer und approximativer Algorithmen entwickelt. Nur in Ausnahmefällen kann man beweisen, dass ein solcherAlgorithmus besser ist als ein anderer. Statt dessen gibt es eine große Menge von Standardeingaben (benchmarks), mit denen ein neuer Algorithmus getestet werden kann. Fortschritt heißt dann entweder, dass man eine bekannte Lösung wesentlich schneller findet als bisher, oder dass man näher an eine noch unbekannte exakte Lösung herankommt, oder dass man zum ersten Mal ein Problem exakt löst (und auch zeigt, dass man es exakt gelöst hat). Im geplanten Projekt soll ein neues Konzept, das Konzept der Toleranzen, zur Lösung des TSP getestet werden. Das Projekt wurde von Herrn Prof. Dr. Sibeyn, Halle, und Herrn Dr. Goldengorin, Groningen, initiiert. Herr Prof. Dr. Sibeyn gilt seit März 2005 als vermisst. Von Hallenser Seite wurde das Projekt im Einverständnis mit der DFG zum 1. Juni 2005 durch Prof. Dr. Paul Molitor übernommen.