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

https://www.math.uwaterloo.ca/tsp/korea/index.html

147•geeknews•4h ago

Comments

labster•2h ago

They call it the Traveling Salesman Problem, but it sounds more like the Drunkard’s Walk to me.

The28thDuck•2h ago

I’d like to call it a stumble :)

srcreigh•2h ago

Title is incorrect. 178 days is the walking time of the optimal tour, not how long it took to solve for the best route

modeless•2h ago

3 months, using 44 CPU-years, is that time.

dang•1h ago

(Submitted title was "Shortest walking tour to 81,998 bars in Korea — TSP solved in 178 days".)

OsrsNeedsf2P•2h ago

I'm impressed they found a dataset this hard, but not much harder. It's a delicate balance between beating the last Traveling Salesman hiscore (Netherlands), and never finishing your compute

bjornsing•48m ago

Do we know they didn’t just prune problematic bars from the dataset until they found a one with a solution?

dumbfounder•28m ago

You and I don’t know. But this is hacker news so there is probably somebody here keeping them honest.

mofunnyman•2h ago

If you spent 40 years of your life on this path, you would still be visiting 5.616 bars per day. Nuts.

kirubakaran•1h ago

Less than 6 bars a day is pretty doable! :-p

Smar•1h ago

Isn't comma the decimal separator ;)

devonkim•48m ago

That’s also not considering whether they’re open or existing anymore after so much time has passed.

notesinthefield•2h ago

I am overwhelmed with the thought of nearly 82 thousand bars within a country roughly the size of Ohio.

dyauspitr•2h ago

NYC that is like 20 miles across has 11,000 locations that serve alcohol.

zeckalpha•2h ago

How many bars do you expect are in Ohio?

fakeBeerDrinker•2h ago

Less than 40,000

zamadatix•2h ago

One would hope with 5x fewer people!

fakeBeerDrinker•2h ago

I think it’s far fewer, probably under 5,000 if we are really talking about “bars” and not any ole liquor licensed establishment such as a restaurant…

jhalstead•1h ago

It seems like you're pretty close with that guess.

https://www.ibisworld.com/us/industry/ohio/bars-nightclubs/1... (2025) estimates there are about 3,000 "bars and nightclubs" in Ohio.

And https://vinepair.com/articles/map-states-with-most-bars/ (2022) estimates there are 1800 bars in Ohio, apparently placing it in the Top 10 of states with the most bars.

lifthrasiir•2h ago

That country has a population of 52 million, i.e. about 5 times Ohio.

kijin•1h ago

Looks like they got their hands on a dataset of every restaurant that is licensed to serve alcohol -- or at least a decent subset of such restaurants, filtered by menu or whatever.

I checked a few dots near where I live and they're all fried chicken joints. Yeah, we do love chimaek around here. :)

flerchin•2h ago

Oh no, looks like a few new bars opened up, and a few others closed. Time to recalculate.

noduerme•2h ago

It's strange that they don't mention the total distance. I understand that the point-to-point travel time is what they're solving for, but it would be interesting to know what the actual distance of travel was, if for no other reason than calculating caloric burn. But then you could also see how much it deviated from the shortest-distance path.

moralestapia•2h ago

>Our computation produced a tour together with a proof that it is a shortest-possible route [...]

Proof nowhere to be found.

Waterloo-ers are nice people but I see an increasing trend of them just lying to get some cred. Come on guys, you don't have to follow the valley model that much.

inasio•1h ago

Not sure what you expected to get. The Concorde TSP solver is an exact solver that uses branch and bound search, it will return either a solution with a specified bound or the optimal bound. They provide the dataset and the solution they found (and I believe their solver is open source), if you don't believe them you can go ahead and find a better tour.

7e•58m ago

I also expected to get an actual proof.

inasio•39m ago

Proof in this case is that the upper bound and the lower bound of the solver converged. This is not like a SAT solver where the solution itself can be trivially evaluated to verify the solution, it requires trusting that the solver does what it's supposed to be doing, similar to what happens when you solve a MILP with Gurobi or CPLEX.

kopirgan•1h ago

Very interesting..

Is anything supposed to happen if you click on those red circles? I was hoping it will show name or other info!

bjornsing•50m ago

Would be nice if they could briefly describe the algorithm. Sounds like they’ve turned the TSP into an integer linear program that they can do branch and bound on, but I’m not sure.

pkhuong•40m ago

It's classic Lin Kernighan (http://webhotel4.ruc.dk/~keld/research/LKH/) for the primal heuristic, and optimality proof by Concorde for cutting plane generation and branching (https://www.math.uwaterloo.ca/tsp/book/index.html, or https://www.math.uwaterloo.ca/tsp/korea/computation.html for details specific to this instance), with CPLEX as the underlying LP solver.

marvinkennis•47m ago

It would suck to get to bar 51,248 only to find out it's now permanently closed

awesome_dude•14m ago

Kids, we're going on a road trip!

Trends in AI Supercomputers

Show HN: Hyprnote – A privacy-first AI notepad that works locally

The tools I love are made by awful people

Show HN: ParseLM – Reliably Structure LLM Outputs for Data and Control Flow

Start a Book Club

Prediction markets create harmful outcomes: a case study

$6.7M stolen from city of Portland in phishing scheme

Show HN: ProfileMagic – $10 AI LinkedIn headshots (20 photos, look natural)

Gen Z grads say their college degrees were a waste as AI infiltrates workplace

A dozen states sue the Trump administration to stop tariff policy

The CIA's 'Heart Attack Gun': A Cold War Weapon for Targeted Assassinations

Nanda: The Internet of AI Agents

Enabling Secure Boot on Odroid M1 (RK3568B)

The Rise of the AI Engineer

The Latent Space of Human Creativity

Scientists say they have resurrected the dire wolf

Asia reaches 50 percent IPv6 capability and leads the world in user numbers

Databases and Discovery in Arithmetic [video]

Trump invites top meme coin holders to dinner; price surges

Can the legal system catch up with climate science?

Software is rapidly being commoditized

MS's patch for symlink vulnerability introduces another symlink vulnerability

Exploiting Undefined Behavior in C/C++ Programs for Optimization [pdf]

SERP Blocks – 1000 Component Library for React Built on ShadcnUI

AI Firm: "Start Cheating"

The Temple Operating System

Hydroxylation and Hydrogen Diffusion in Lunar Samples: Spectral Measurements

JWST explores enigmatic mid-infrared rings in planetary nebula NGC 1514

NASA experiment shows solar wind might make water on the moon

Sodom comet paper to be retracted