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

Clarifying the result and computation

• The “178 days” refers to walking time along the optimal route, not time to compute it.
• The computation itself took about 3 months of wall time and 44 CPU‑years.
• Comparison is made to a previous Netherlands TSP instance that used ~97 CPU‑years over 6 months.

Problem difficulty and algorithms

• Commenters note the careful choice of instance: hard enough to beat older “hiscores” but still solvable.
• Some speculate whether points could have been pruned, but acknowledge the community tends to scrutinize such claims.
• The solution process: heuristic tour via LKH (Lin‑Kernighan‑Helsgaun) and optimality proof via the Concorde solver with cutting planes and branch‑and‑bound, using CPLEX for LP.
• Discussion touches on simpler heuristics like 2‑opt and how they compare.
• There is debate about GPU/CUDA applicability: current branch‑and‑bound / cutting‑plane methods don’t map well to GPUs, though newer PDLP‑type approaches may.

What counts as a “bar” and dataset issues

• Data come from a Korean National Police Agency database of alcohol‑licensed venues.
• Many points appear to be small restaurants, fried chicken places, karaoke rooms, etc., not just classic bars.
• Some locals say many neighborhood spots aren’t even in public maps, so coverage is incomplete.

Number of bars: comparisons and culture

• People are struck by ~82k venues in a country about the size of a U.S. state.
• Comparisons are made to Ohio, Indiana, NYC, the UK; ratios per capita and per area vary widely.
• Some argue this reflects a very strong drinking culture; others note similar per‑capita figures once all liquor licenses are counted.
• Differences in what “bar” means across countries (e.g., Spanish bars as all‑purpose social centers) are emphasized.

Urban design, parking, and drinking

• Thread branches into parking minimums in U.S. suburbs versus tiny, dense, walkable drinking districts in Korea and Europe.
• Some see parking minimums as a cause of asphalt deserts; others say lots are usually full and necessary in car‑centric places.
• There’s concern about bars with mandated parking encouraging drunk driving; practices like designated drivers and leaving cars overnight are discussed.
• Debate arises over whether “a culture of hanging out and drinking” truly requires walkable urbanism or simply historically walkable settlements that later urbanized.

Dynamic reality vs static TSP

• Multiple comments joke that during a 40‑year real tour, many bars would open, close, or deny entry, invalidating the route.
• This is compared to the star tour instance, where stellar motion would also break a literal path over cosmological timescales.

UI and data wishes

• Some wish clicking red dots on the map showed venue names or details.
• Others note the site doesn’t show total distance or calories, only travel time; computing exact real‑road distances with a routing API would be expensive and complicated.

Related TSP work and theory discussion

• The authors’ earlier work on a 1.33‑billion‑star TSP (Gaia data) is mentioned, where the tour is within 0.38% of optimal.
• There is clarification that for very large instances, they report high‑quality heuristics rather than proven optima.
• One commenter reminisces outdated classroom claims like “13 cities is the max” and is corrected with modern record sizes (millions of points with proofs).
• Basic concepts like branch‑and‑bound and NP‑hardness are briefly discussed; someone asks whether large‑scale quantum computers would solve such problems easily, without a definite answer.

Humor and anecdotes

• Many jokes about “Drunkard’s Walk,” “traveling drinking man’s problem,” and visiting 5–6 bars per day for decades.
• Classic pub‑riddle anecdotes and personal walking‑every‑street projects are shared as small‑scale analogues of the TSP idea.