Shortest walking tour to 81,998 bars in Korea – TSP solved in 178 days
a year ago
- #Optimization
- #Traveling Salesman Problem
- #South Korea
- Solved the largest road-map instance of the Traveling Salesman Problem (TSP) with 81,998 stops in South Korea.
- Total walking time for the optimal route is 15,386,177 seconds (178 days, 1 hour, 56 minutes, and 17 seconds).
- Used Open Source Routing Machine (OSRM) to compute 3,361,795,003 point-to-point travel times.
- Combined LKH and Concorde codes for computing optimal solutions and applying the cutting-plane method.
- Exceeded the previous record of a 57,912-stop tour in the Netherlands solved in February 2021.
- Computation carried out between December 2024 and March 2025 at Roskilde University and the University of Waterloo.
- Interactive map available for viewing the tour with options to display stop markers and tour edges.
- Addressed common misconceptions about solving large TSP instances by leveraging advanced optimization methods.
- Acknowledged contributions from IBM CPLEX Optimizer, OpenStreetMap, and the Korean National Police Agency.