Die kürzeste Fußroute durch 81.998 Bars in Korea

 (math.uwaterloo.ca)
2 Punkte von GN⁺ 2025-04-25 | 2 Kommentare | Auf WhatsApp teilen
  • Das Travelling-Salesman-Problem (TSP) wurde hier als Aufgabe formuliert, die kürzeste Route zu finden, um 81.998 Bars in Korea zu besuchen, und mit der Open Source Routing Machine (OSRM) gelöst
  • Diese Route ist eine optimale Route, die mehr als 178 Tage dauert, was durch Berechnungen mit OSRM nachgewiesen wurde
  • Mithilfe von LKH-Code und Concorde-Code wurde die cutting-plane method angewandt, um ein groß angelegtes TSP zu lösen
  • Mathematische Optimierung und Operations Research konzentrieren sich auf die Entwicklung von Werkzeugen zur Steigerung der Ressourceneffizienz
  • Die Forschung wurde an der Roskilde University und der University of Waterloo durchgeführt, unter Verwendung des IBM CPLEX Optimizer und der Leaflet-Bibliothek

Die kürzeste Route zum Besuch von 81.998 Bars in Korea

  • Das Travelling-Salesman-Problem (TSP) wurde hier als Aufgabe formuliert, die kürzeste Route zu finden, um 81.998 Bars in Korea zu besuchen, und mit der Open Source Routing Machine (OSRM) gelöst
  • Diese Route ist eine optimale Route, die mehr als 178 Tage dauert, was durch Berechnungen mit OSRM nachgewiesen wurde
  • Mithilfe von LKH-Code und Concorde-Code wurde die cutting-plane method angewandt, um dieses groß angelegte TSP zu lösen

Lösung eines groß angelegten TSP

  • Mathematische Optimierung und Operations Research konzentrieren sich auf die Entwicklung von Werkzeugen zur Steigerung der Ressourceneffizienz
  • Die Forschung wurde an der Roskilde University und der University of Waterloo durchgeführt, wobei der IBM CPLEX Optimizer und die Leaflet-Bibliothek verwendet wurden

Forschungsteam und Danksagung

  • Das Forschungsteam bestand aus William Cook, Daniel Espinoza, Marcos Goycoolea und Keld Helsgaun
  • Für die Forschung wurden der CPLEX Optimizer von IBM und die Leaflet-Bibliothek verwendet
  • Die Standorte der Bars in Korea wurden aus der Datenbank der koreanischen Nationalpolizei entnommen

Verwandte Beiträge

2 Kommentare

 
xguru 2025-04-25

Ich habe den Beitrag Die kürzeste Wanderroute, um alle 81.998 Bars in Korea zu besuchen, dauert 178 Tage mit dem GeekNews-Account auf Hacker News gepostet.
Er bekam viele Stimmen, stand 6 Stunden lang ganz oben und wurde dann zu einem beliebten Beitrag, sodass er wieder als GN+ importiert (?) wurde.

Ich habe das ausprobiert, weil zu dem Beitrag auch eine englische Version vorhanden war; gelegentlich möchte ich Beiträge, die auch Englisch enthalten, künftig auf Hacker News posten.
 
GN⁺ 2025-04-25
Hacker-News-Kommentare
  • Beeindruckend ist die TSP-Lösung mit 133 Millionen Kanten
    • Die Tour ist 1,0038-mal so lang wie die kürzeste Route
    • Ich frage mich, wie schlecht das Ergebnis mit dem probabilistischen Algorithmus der Bell Labs wäre
  • Erklärung des klassischen TSP-Ansatzes
    • Alle Knoten werden in einer beliebigen Route verbunden
    • Die Route wird an zwei Stellen aufgetrennt, sodass drei Teile entstehen
    • Die drei Teile werden auf sechs mögliche Arten neu angeordnet, und die kürzeste wird gewählt
    • Schritt 2–3 wird wiederholt, bis es keine Verbesserung mehr gibt
    • Das garantiert kein optimales Ergebnis, ist aber bei den meisten realen Problemen optimal oder sehr nah dran
  • Es ist seltsam, dass die Gesamtdistanz nicht erwähnt wird
    • Das Ziel ist zwar, die Reisezeit zu optimieren, aber es wäre auch interessant, die tatsächliche zurückgelegte Strecke zu kennen
    • Man könnte den Kalorienverbrauch berechnen oder prüfen, wie stark die Route von der kürzesten Distanz abweicht
  • Ich bin überwältigt bei dem Gedanken, dass es in einem Land von der Größe Ohios fast 82.000 Bars gibt
  • Während COVID habe ich mir mit CityStrides das Ziel gesetzt, jede Straße meiner Stadt zu Fuß abzulaufen
    • Es verfolgt die gelaufene Strecke und zeigt an, wie viel Prozent der Stadt man bereits abgelaufen ist
    • Es optimiert die Route nicht, aber es war ein unterhaltsames mentales Rätsel, möglichst viele Straßen ohne Wiederholungen zu gehen
    • Automatisierungstools können zwar Spaß machen, aber es von Hand zu machen war Teil der Reise
    • Auf der CityStrides-Website kann man die LifeMaps anderer Leute ansehen
    • Manche Menschen laufen erstaunlich viel
  • Das erinnert mich an eine Frage, die in den 60ern in der irischen Armee gestellt wurde
    • „Wie kommt man von Bachelor's Walk zu den Collins Barracks, ohne an einer Bar vorbeizukommen?“
    • Die Antwort war: „Indem man in jede Bar hineingeht“
  • Beeindruckend, dass dieses Dataset gefunden wurde, aber viel schwerer ist es nicht
    • Es ist ein subtiler Balanceakt zwischen dem Brechen des letzten Traveling-Salesman-Rekords und dem Punkt, an dem man die Berechnung nicht mehr zu Ende führen kann
  • NP sieht wieder wie P aus
    • In der Schule habe ich gelernt, dass 13 das Maximum sei, und in den 80ern brachte mein Professor es auf 15
    • Danach kamen 20, 20.000 und diesmal sind 80.000 bewiesen worden
    • Auf der World-TSP-Seite liegt der Rekord bei 1 Million
    • Der derzeit größte bewiesene Optimalwert liegt bei 3.178.031
    • Das muss man mit CUDA machen, nicht mit normalem C
  • Branch-and-bound ist ein Algorithmus „wie aus dem Lehrbuch“
    • Wenn man den LP-Solver als Blackbox betrachtet, ist er im Grunde sehr einfach, aber äußerst nützlich
  • Es sieht so aus, als hätten einige neue Bars geöffnet und einige andere geschlossen
    • Zeit für eine Neuberechnung