Auf Toleranzen Basierende Methoden zur Lösung des Handelsreisendenproblems

• Antragsteller: Professor Dr. Paul Molitor
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2004 bis 2010
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 5426224

Das Handelsreisendenproblem, weiter zu "TSP" (Traveling Salesman Problem) abgekürzt, ist eines der meist studierten Probleme der kombinatorischen Optimierung und gilt als Inbegriff eines schwierigen Problems, ein Problem, über das auch in den Wissenschaftsbeilagen von Tageszeitungen geschrieben wird. Die Faszination des TSP liegt vor allem im Kontrast zwischen seiner extrem einfachen Formulierung und der enormen Schwierigkeit, dieses Problem zu lösen. Bisher gibt es nur Heuristiken. Es gibt eine große Menge von Standardeingaben, mit denen eine neue Heuristik getestet werden kann. In dem Kontext dieses Problems heißt Fortschritt, dass man entweder eine bekannte Lösung schneller findet als bisher, oder dass man näher an eine noch unbekannte Lösung herankommt, oder dass man zum ersten Mal ein Problem exakt löst. Im geplanten Projekt werden wir unsere Kräfte bündeln mit dem Ziel, neue Beiträge zu liefern. Dabei werden wir ganz unten in den verwendeten Heuristiken ansetzen: alle Heuristiken tasten sich an eine Lösung heran indem sie wiederholt Entscheidungen treffen, die sich u.U. nachher als falsch erweisen. Wir glauben, dass die "Toleranzen" eine bessere Grundlage für diese Entscheidungen sind als die üblichen Kriterien. Wenn dies so ist, könnte das dramatische Auswirkungen haben für die Zeit, die man zur Lösung eines Problems braucht. Die Rahmenbedingungen für das Projekt sind günstig: in der Arbeitsgruppe gibt es eine einmalige Mischung von vorhandenen Kapazitäten und sie verfügt über eine optimale Rechnerausstattung.

• DFG-Verfahren: Sachbeihilfen
• Internationaler Bezug: Niederlande
• Beteiligte Person: Professor Dr. Boris Goldengorin