Shortest walking tour to 81,998 bars in Korea – TSP solved in 178 days

Summary

We have solved a traveling salesman problem (TSP) to walk to 81,998 bars in South Korea. The problem was created using the Open Source Routing Machine (OSRM) to build a table of the 3,361,795,003 point-to-point travel times, one for each pair of bar locations. Our computation produced a tour together with a proof that it is a shortest-possible route to visit all 81,998 stops when measured with the OSRM times. It would be a very long pub crawl. The total walking time for the round trip is 15,386,177 seconds, or 178 days, 1 hour, 56 minutes, and 17 seconds. You will need to stop for plenty of drinks along the way (better stick with water, tea, or Diet Coke if you want to finish the route in only a few years), so it's not likely you would count every second on such a journey. But the level of precision makes the point that this not just a good route, it is an optimal solution to the 81,998-stop TSP. It is not possible to rearrange the order of stops to save even a single second of the OSRM-estimated walking time. This is the largest road-map instance of the TSP that has been solved to provable optimality, exceeding the 57,912-stop tour through the Netherlands solved in February 2021. The computations were carried out between December 2024 and March 2025 at Roskilde University and at the University of Waterloo. Details of the computing work can be found on the Computation page. Interactive map The figure below is a screen shot of an interactive map of the korea81998 tour. The menu on the left-hand-side lets you select one of seven regions to view. At the top right-hand-side you can choose to have either a colored street map or a grayscale map without street labels. Just below this menu you can select whether or not to display the stop markers, or to display the tour edges, or to display both. You can view the map by clicking on the image. Snapshots of the Tour If you have trouble viewing the interactive map, you can click on the drawings below to see high-resolution ima...