A researcher has calculated the shortest possible walking tour visiting all 81,998 bars in South Korea, a journey spanning approximately 115,116 kilometers. This massive traveling salesman problem (TSP) solution, while theoretically interesting, is practically infeasible. The route was computed using Concorde, a specialized TSP solver, and relies on road network data and bar locations extracted from OpenStreetMap. The resulting tour, visualized on the linked webpage, demonstrates the power of sophisticated algorithms to tackle complex optimization challenges, even if the application itself is whimsical.
This webpage meticulously documents the computational journey undertaken to devise a remarkably efficient walking tour encompassing a staggering 81,998 bars located across the entirety of South Korea. The central challenge, framed as a Traveling Salesperson Problem (TSP), involves determining the shortest possible route that visits each bar precisely once and returns to the starting point. Given the immense scale of this particular problem, with nearly 82,000 distinct locations to consider, arriving at an optimal solution presents a formidable computational hurdle.
The author employs sophisticated optimization techniques, specifically a refined implementation of the Lin-Kernighan heuristic, to tackle this complex task. The Lin-Kernighan heuristic is an iterative algorithm that systematically improves an initial tour by identifying and swapping segments to progressively reduce the overall distance. Due to the sheer magnitude of the problem, the computations were distributed across a network of computers, leveraging their combined processing power to gradually refine the solution over an extended period.
The resulting tour, meticulously detailed on the webpage, represents an exceptionally efficient traversal of these numerous establishments. The author provides various visualizations of the tour, including interactive maps and downloadable data files, allowing for in-depth exploration of the generated route. Furthermore, the webpage offers insights into the computational methodology employed, highlighting the challenges encountered and the strategies adopted to overcome them. The magnitude of the problem and the impressive optimization achieved underscore the power and applicability of advanced algorithmic techniques in tackling real-world logistical challenges, albeit in this instance, applied to a rather unconventional, yet fascinating, scenario. While the practical implications of visiting nearly 82,000 bars are perhaps debatable, the project serves as a compelling demonstration of the capabilities of modern optimization algorithms when applied to exceptionally large datasets.
Summary of Comments ( 122 )
https://news.ycombinator.com/item?id=43778105
HN commenters were impressed by the scale of the traveling salesman problem solved, with one noting it's the largest road network TSP solution ever found. Several discussed the practical applications, questioning the real-world usefulness given factors like bar opening/closing times and the impracticality of actually completing such a tour. The algorithm used, Concorde, was also a topic of discussion, with some explaining its workings and limitations. Some users highlighted potential issues with the data, specifically questioning whether all locations were truly accessible by road, particularly those on islands. Finally, a few users humorously imagined actually attempting the tour, calculating the time required, and referencing other enormous computational problems.
The Hacker News post titled "Shortest-possible walking tour to 81,998 bars in South Korea" sparked a discussion with a moderate number of comments, primarily focusing on the computational aspects of solving the Traveling Salesperson Problem (TSP) at such a large scale. Several commenters expressed fascination with the scale of the problem and the optimization techniques employed.
One commenter highlighted the use of Concorde, a specialized TSP solver known for its efficiency, and questioned whether the solution found was truly optimal or just a very good approximation. They also raised the practical considerations of such a tour, noting the impracticality of actually undertaking it. This sparked a small side discussion about the definition of "optimal" in the context of TSP solvers and the computational resources required to guarantee true optimality for very large datasets.
Another commenter delved into the specifics of the algorithm used, mentioning the Lin-Kernighan heuristic as a key component of Concorde's approach. They explained how this heuristic iteratively improves a tour by swapping edges to find shorter paths. The discussion then touched upon the concept of "tour length," distinguishing between Euclidean distance and actual travel distance, with an acknowledgement that the solution likely focuses on abstract distance rather than real-world walkability.
There was also a brief exchange about the data source for the bar locations, with speculation about the use of OpenStreetMap (OSM) or similar databases. This led to a comment about the potential issues with data accuracy and completeness, particularly in densely populated areas.
A few comments offered humorous takes on the premise, imagining the physical challenges of completing such a tour and the potential toll on one's liver.
Overall, the comments section reflects a mix of technical appreciation for the computational feat, practical considerations about the real-world implications, and lighthearted amusement at the absurdity of the concept. No one seemed to be planning an 82,000-bar pub crawl anytime soon, but the problem clearly captured the imagination of several commenters.