Die kürzeste Fußroute, um alle 81.998 Kneipen in Korea zu besuchen, dauert 178 Tage

xguru · 2025-04-23T09:31:02+09:00

Weltweit erster Fall, in dem Professor William Cook von der University of Waterloo das Traveling-Salesman-Problem (TSP) für die kürzeste Route zum Besuch von 81.998 Kneipen in Korea berechnet hat Mit der Open Source Routing Machine (OSRM) wurden rund 3,3 Milliarden Paarungen von Gehzeiten berechnet und mathematisch bewiesen, dass die Lösung optimal ist Das Ergebnis der Berechnung: Bei ununterbrochenem Gehen dauert die Route insgesamt 15.386.177 Sekunden, also 178 Tage, 1 Stunde, 56 Minuten und 17 Sekunden Für die TSP-Optimierung wurden die Werkzeuge LKH und Concorde verwendet, dabei kam die Cutting-Plane-Methode zum Einsatz Damit ist dies der weltweit größte gelöste straßenbasierte TSP-Fall und übertrifft den bisherigen Rekord von 57.912 Punkten in den Niederlanden Das Traveling-Salesman-Problem zu allen Kneipen Koreas zu Fuß Es wurde die kürzeste Route berechnet, die alle 81.998 Kneipen in Korea besucht und wieder zum Ausgangspunkt zurückkehrt Zum ersten Mal weltweit wurde ein TSP-Problem mit so vielen Orten optimal gelöst Die Gehzeiten für insgesamt 3.361.795.003 Paare von Kneipen wurden mit OSRM - Open Source Routing Machine berechnet Mathematisch ist bewiesen, dass keine kürzere Route existiert Gemessen an der Zahl der Stopps ist dies das größte TSP-Problem, das je gelöst wurde Benötigte Zeit für die kürzeste Route Wer der berechneten optimalen Route ohne Pause folgt, braucht insgesamt 15.386.177 Sekunden Das entspricht 178 Tagen, 1 Stunde, 56 Minuten und 17 Sekunden In der Praxis dürfte ein exakter Abschluss schwierig sein, weil man beim Gehen pausiert oder etwas trinkt Auf Basis der mit OSRM berechneten Gehzeiten ist dies eine optimale Route, die sich nicht einmal um 1 Sekunde verkürzen lässt Historischer TSP-Kontext und neuer Rekord Der bisherige Rekord war eine Fahrradroute zu 57.912 Punkten in den Niederlanden Die neue Route korea81998 ist ein noch größerer gelöster TSP-Fall Die Berechnungen wurden von Dezember 2024 bis März 2025 an der Roskilde University und der University of Waterloo durchgeführt Details zur Berechnung sind auf einer separaten Berechnungsseite zu finden So lässt sich die Route visualisieren Die Route kann auf einer interaktiven Karte betrachtet werden und ist in 7 Regionen zur Erkundung unterteilt Es gibt verschiedene Visualisierungsmodi, etwa eine farbige Distanzkarte oder Graustufen Hochauflösende Bilder einzelner Teile der Route werden ebenfalls separat bereitgestellt Vergrößerte Ansichten nach Städten gibt es auf den Stadtseiten TSP-Lösungsstrategie und Missverständnisse Manche Medien berichten, dass schon 22 Städte 1.000 Jahre benötigen würden; das gilt jedoch nur, wenn man alle Routen zufällig ausprobiert In der Praxis lassen sich auch sehr viele Punkte mit fortgeschrittenen Optimierungsmethoden lösen Bei korea81998 entspricht die Zahl möglicher Routen einer 2 mit 367.308 Nullen dahinter Für die Lösung wurden der LKH(Lin-Kernighan Heuristic)-Algorithmus und der Concorde TSP Solver - Cutting-Plane-Methode kombiniert Kurz erklärt: die Cutting-Plane-Methode Sie basiert auf linearer Programmierung Statt nur zu markieren, ob eine Straße genutzt wird, wird der Verbindungsgrad als Wert zwischen 0 und 1 dargestellt Durch das schrittweise Hinzufügen von Nebenbedingungen wird die kürzeste Route gefunden Eine ausführlichere Erklärung gibt es bei Scientific American und in einem YouTube-Vortrag Das P-vs-NP-Problem Das TSP ist ein NP-vollständiges Problem und ein typisches Beispiel in der Diskussion um P und NP Eine interessante zugehörige Diskussion wird in einer Arbeit von Professor Lance Fortnow vorgestellt Das Thema gehört zu den berühmtesten ungelösten Problemen der Informatik Die Bedeutung mathematischer Optimierung Dieses Projekt ist ein Experiment zu allgemeinen Optimierungsmethoden und eine Grundlage für deren Weiterentwicklung Es besitzt großes Anwendungspotenzial in Industrie, Wirtschaft, Medizin und Umwelt Mathematische Modellierung ist ein wichtiges Werkzeug, um begrenzte Ressourcen effizient zu nutzen Das Forschungsteam William Cook: University of Waterloo, Kanada Daniel Espinoza: Alicanto Labs, Chile Marcos Goycoolea: Universidad Adolfo Ibáñez, Chile Keld Helsgaun: Roskilde University, Dänemark Danksagung IBM CPLEX Optimizer: Dank für die kostenlose Bereitstellung für akademische Forschung Die Karten wurden mit Leaflet, OpenStreetMap, Carto und Stadia Maps erstellt Dr. Sang-il Eom stellte auf Basis von Daten der koreanischen Nationalen Polizeibehörde Standortdaten zu Kneipen bereit Für die Berechnung der Gehzeiten wurde OSRM genutzt Beispiele für TSP-Projekte in anderen Ländern Japan: 40.426 Convenience Stores Vereinigtes Königreich: 49.687 Kneipen USA: 49.603 historische Orte Niederlande: 57.912 Denkmäler Weiterführende Materialien In Pursuit of the Traveling Salesman: Geschichte und Anwendungen des TSP Traveling Salesman Problem: Forschung zur Anwendung der Cutting-Plane-Methode The Golden Ticket: Einführung in das P-vs.-NP-Problem Opt Art: Künstlerische Bilderzeugung mit TSP Approximation Algorithms: Aktuelle Forschung zu TSP-Approximationsalgorithmen Computational Solutions for TSP Applications: Buch zu Anwendungsfällen, erschienen 1994

(math.uwaterloo.ca)

23 Punkte von xguru 2025-04-23 | 10 Kommentare | Auf WhatsApp teilen

Weltweit erster Fall, in dem Professor William Cook von der University of Waterloo das Traveling-Salesman-Problem (TSP) für die kürzeste Route zum Besuch von 81.998 Kneipen in Korea berechnet hat
Mit der Open Source Routing Machine (OSRM) wurden rund 3,3 Milliarden Paarungen von Gehzeiten berechnet und mathematisch bewiesen, dass die Lösung optimal ist
Das Ergebnis der Berechnung: Bei ununterbrochenem Gehen dauert die Route insgesamt 15.386.177 Sekunden, also 178 Tage, 1 Stunde, 56 Minuten und 17 Sekunden
Für die TSP-Optimierung wurden die Werkzeuge LKH und Concorde verwendet, dabei kam die Cutting-Plane-Methode zum Einsatz
Damit ist dies der weltweit größte gelöste straßenbasierte TSP-Fall und übertrifft den bisherigen Rekord von 57.912 Punkten in den Niederlanden

Das Traveling-Salesman-Problem zu allen Kneipen Koreas zu Fuß

Es wurde die kürzeste Route berechnet, die alle 81.998 Kneipen in Korea besucht und wieder zum Ausgangspunkt zurückkehrt
Zum ersten Mal weltweit wurde ein TSP-Problem mit so vielen Orten optimal gelöst
Die Gehzeiten für insgesamt 3.361.795.003 Paare von Kneipen wurden mit OSRM - Open Source Routing Machine berechnet
Mathematisch ist bewiesen, dass keine kürzere Route existiert
Gemessen an der Zahl der Stopps ist dies das größte TSP-Problem, das je gelöst wurde

Benötigte Zeit für die kürzeste Route

Wer der berechneten optimalen Route ohne Pause folgt, braucht insgesamt 15.386.177 Sekunden
Das entspricht 178 Tagen, 1 Stunde, 56 Minuten und 17 Sekunden
In der Praxis dürfte ein exakter Abschluss schwierig sein, weil man beim Gehen pausiert oder etwas trinkt
Auf Basis der mit OSRM berechneten Gehzeiten ist dies eine optimale Route, die sich nicht einmal um 1 Sekunde verkürzen lässt

Historischer TSP-Kontext und neuer Rekord

Der bisherige Rekord war eine Fahrradroute zu 57.912 Punkten in den Niederlanden
Die neue Route korea81998 ist ein noch größerer gelöster TSP-Fall
Die Berechnungen wurden von Dezember 2024 bis März 2025 an der Roskilde University und der University of Waterloo durchgeführt
Details zur Berechnung sind auf einer separaten Berechnungsseite zu finden

So lässt sich die Route visualisieren

Die Route kann auf einer interaktiven Karte betrachtet werden und ist in 7 Regionen zur Erkundung unterteilt
Es gibt verschiedene Visualisierungsmodi, etwa eine farbige Distanzkarte oder Graustufen
Hochauflösende Bilder einzelner Teile der Route werden ebenfalls separat bereitgestellt
Vergrößerte Ansichten nach Städten gibt es auf den Stadtseiten

TSP-Lösungsstrategie und Missverständnisse

Manche Medien berichten, dass schon 22 Städte 1.000 Jahre benötigen würden; das gilt jedoch nur, wenn man alle Routen zufällig ausprobiert
In der Praxis lassen sich auch sehr viele Punkte mit fortgeschrittenen Optimierungsmethoden lösen
Bei korea81998 entspricht die Zahl möglicher Routen einer 2 mit 367.308 Nullen dahinter
Für die Lösung wurden der LKH(Lin-Kernighan Heuristic)-Algorithmus und der Concorde TSP Solver - Cutting-Plane-Methode kombiniert

Kurz erklärt: die Cutting-Plane-Methode

Sie basiert auf linearer Programmierung
Statt nur zu markieren, ob eine Straße genutzt wird, wird der Verbindungsgrad als Wert zwischen 0 und 1 dargestellt
Durch das schrittweise Hinzufügen von Nebenbedingungen wird die kürzeste Route gefunden
Eine ausführlichere Erklärung gibt es bei Scientific American und in einem YouTube-Vortrag

Das P-vs-NP-Problem

Das TSP ist ein NP-vollständiges Problem und ein typisches Beispiel in der Diskussion um P und NP
Eine interessante zugehörige Diskussion wird in einer Arbeit von Professor Lance Fortnow vorgestellt
Das Thema gehört zu den berühmtesten ungelösten Problemen der Informatik

Die Bedeutung mathematischer Optimierung

Dieses Projekt ist ein Experiment zu allgemeinen Optimierungsmethoden und eine Grundlage für deren Weiterentwicklung
Es besitzt großes Anwendungspotenzial in Industrie, Wirtschaft, Medizin und Umwelt
Mathematische Modellierung ist ein wichtiges Werkzeug, um begrenzte Ressourcen effizient zu nutzen

Das Forschungsteam

William Cook: University of Waterloo, Kanada
Daniel Espinoza: Alicanto Labs, Chile
Marcos Goycoolea: Universidad Adolfo Ibáñez, Chile
Keld Helsgaun: Roskilde University, Dänemark

Danksagung

IBM CPLEX Optimizer: Dank für die kostenlose Bereitstellung für akademische Forschung
Die Karten wurden mit Leaflet, OpenStreetMap, Carto und Stadia Maps erstellt
Dr. Sang-il Eom stellte auf Basis von Daten der koreanischen Nationalen Polizeibehörde Standortdaten zu Kneipen bereit
Für die Berechnung der Gehzeiten wurde OSRM genutzt

Beispiele für TSP-Projekte in anderen Ländern

Japan: 40.426 Convenience Stores
Vereinigtes Königreich: 49.687 Kneipen
USA: 49.603 historische Orte
Niederlande: 57.912 Denkmäler

Weiterführende Materialien

In Pursuit of the Traveling Salesman: Geschichte und Anwendungen des TSP
Traveling Salesman Problem: Forschung zur Anwendung der Cutting-Plane-Methode
The Golden Ticket: Einführung in das P-vs.-NP-Problem
Opt Art: Künstlerische Bilderzeugung mit TSP
Approximation Algorithms: Aktuelle Forschung zu TSP-Approximationsalgorithmen
Computational Solutions for TSP Applications: Buch zu Anwendungsfällen, erschienen 1994

10 Kommentare

ep6tri 2025-04-24

Die englische Seite ist https://www.math.uwaterloo.ca/tsp/korea/index.html.
Die Tour ist natürlich ziemlich unrealistisch. Es scheint auch nicht berücksichtigt zu sein, Seewege per Fähre zu nehmen, wenn man vom Festland nach Jeju-do oder Ulleungdo reist. Dieses Bild zeigt es gut: https://www.math.uwaterloo.ca/tsp/korea/img/full_line.png

Das Ziel ist wohl nicht, die voraussichtliche Besuchsdauer exakt zu berechnen, sondern darin liegt die Bedeutung, dass das TSP mit realen Daten gelöst wurde.

skshin 2025-04-23

Wie kommt man zwischen den Inseln hin und her? Zu Fuß?

halfenif 2025-04-23

Weil dort walking and ferry steht, scheint es so, als würde man mit der Fähre fahren.

woalsdnd 2025-04-23

Wie sollte man damit umgehen, wenn in Echtzeit neue hinzukommen und andere schließen?

majorika 2025-04-23

> Ich sollte im März 2024 an der KAIST in Daejeon eine Vorlesung über TSP halten und suchte nach einem lokalen Datensatz für eine TSP-Tour durch Daejeon. Im Dezember 2023 schrieb mir Dr. Sang-il Um per E-Mail: „Brauchen Sie den landesweiten Datensatz über Bars, den die koreanische Nationalpolizei erstellt hat? Die aktuelle Datei kostet 1.000 Won und enthält 90.680 Einträge.“ Wow. Nachdem ich zuerst überprüft hatte, ob 1.000 Won weniger als 1 US-Dollar sind (es war gut, zu prüfen, ob der Wechselkurs nicht etwa umgekehrt war), antwortete ich: „Danke!“

https://www.math.uwaterloo.ca/tsp/korea/sk_data.html

kimjoin2 2025-04-23

Wow, das hatte also diesen Hintergrund. Danke fürs Zusammenfassen & Teilen.

kimjoin2 2025-04-23

Ich frage mich auch, warum ausgerechnet Korea ausgewählt wurde 👀

firea32 2025-04-28

Dass man für 1.000 Won an qualitativ hochwertige Daten kommen konnte, dürfte ebenfalls eine Rolle gespielt haben :)