Shortest-possible walking tour to 81,998 bars in South Korea

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 OS ... Read full article.