Gelöst: Der Korea-Kneipen-Marathon mit 81.998 Lokalen – Ein Meilenstein beim Travelling Salesperson Problem

Ein Team hat das Travelling Salesperson Problem (TSP) für 81.998 Bars in Südkorea gelöst und die kürzeste mögliche Route gefunden, um alle zu besuchen. Die gesamte Gehzeit beträgt beeindruckende 178 Tage, obwohl eine praktische Umsetzung in diesem Zeitraum unmöglich ist. Die Präzision der Lösung beweist jedoch ihre Optimalität und übertrifft den vorherigen Rekord von 57.912 Stationen in den Niederlanden. Das Team verwendete die Algorithmen LKH und Concorde, kombiniert mit der „Schnitt-Ebenen-Methode“, und demonstrierte, dass selbst bei einer astronomisch großen Anzahl von Möglichkeiten optimale Lösungen gefunden werden können. Dies stellt einen bedeutenden Fortschritt bei der Lösung von Optimierungsproblemen in großem Maßstab dar.