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

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

185•geeknews•5h ago

Comments

labster•4h ago

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

The28thDuck•3h ago

I’d like to call it a stumble :)

srcreigh•4h 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•3h ago

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

dang•3h ago

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

OsrsNeedsf2P•3h 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•1h ago

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

dumbfounder•1h ago

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

omoikane•39m ago

In the "computations" page[1], the table lists the Netherlands computation as costing 97 CPU years with 6 months of elapsed time, while the Korean bars costs 44 years of CPU time and 3 months of elapsed time. I can't tell if the two problems were solved using the same hardware.

[1] https://www.math.uwaterloo.ca/tsp/korea/computation.html

mofunnyman•3h ago

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

kirubakaran•3h ago

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

Smar•2h ago

Isn't comma the decimal separator ;)

throwaway019254•1h ago

It depends on which part of the world you live in.

speedgoose•27m ago

It’s not that many bars.

devonkim•1h ago

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

notesinthefield•3h ago

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

dyauspitr•3h ago

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

zeckalpha•3h ago

How many bars do you expect are in Ohio?

fakeBeerDrinker•3h ago

Less than 40,000

zamadatix•3h ago

One would hope with 5x fewer people!

fakeBeerDrinker•3h 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•2h 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•3h ago

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

kijin•2h 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. :)

yard2010•21m ago

In korea after a certain hour every restaurant, karaoke, PCBang, and hotteok parlor is basically a bar :)

God I miss this place so much <3

flerchin•3h ago

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

noduerme•3h 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•3h 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•2h 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•2h ago

I also expected to get an actual proof.

inasio•1h 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•2h 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•2h 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•1h 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•1h ago

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

awesome_dude•1h ago

Kids, we're going on a road trip!

rurban•44m ago

So NP is like P again. I learned in school 13 is the max and one of my algebra professors advanced it to 15 (in the 80ies). Then came 20, then came 20.000, this is 80k with proof, and at the World TSP page we see the record was 1m.

http://webhotel4.ruc.dk/~keld/research/LKH/

The biggest proven optimum is for 3178031 right now.

This should be really done with CUDA, not plain C, btw.

eduardosalaz•12m ago

There is tons of work to do on running optimization algorithms in GPU. In its current form, Branch and Bound and Cutting Planes do not gain an advantage if implemented in CUDA. There is a new algorithm, PDLP, which is implementable in GPUs but it is still in early stages. For more, see https://blogs.nvidia.com/blog/cuopt-open-source/.

JohnKemeny•7m ago

The thing is that Euclidean TSP needs a lot of data to encode hard instances.

N=15 was even considered solved in the 60s, and N=20 has never been considered large instances, especially not of Euclidean TSP.

I cannot see how anyone could say 13 is the max: you need 100k memory slots and 1M comparisons. This has been trivial for quite some time.

blt•36m ago

Branch-and-bound is an algorithm "from the book" to me. Fundamentally very simple, provided you view the LP solver as a black box, but incredibly useful.

DennisL123•24m ago

OSRM lead dev here. Love to see this large of an instance being solved.

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

Show HN: My from-scratch OS kernel that runs DOOM

How a 20 year old bug in GTA San Andreas surfaced in Windows 11 24H2

CubeCL: GPU Kernels in Rust for CUDA, ROCm, and WGPU

You wouldn't steal a font

Yagri: You are gonna read it

Teaching LLMs how to solid model

Launch HN: Cua (YC X25) – Open-Source Docker Container for Computer-Use Agents

Apple and Meta fined millions for breaching EU law

Graphics livecoding in Common Lisp

AI Horseless Carriages

Clinical trial: novel nutritional formula treats gut microbial overgrowth

Google blocked Motorola use of Perplexity AI, witness says

MCP on AWS Lambda with MCPEngine

First Successful Lightning Triggering and Guiding Using a Drone

I Tried to Buy an Actual Barrel of Crude Oil (2015)

The Future of MCPs

My experience of participating to a startup weekend competition in Italy

Show HN: Node.js video tutorials where you can edit and run the code

C++26: more constexpr in the core language

DOGE worker’s code supports NLRB whistleblower

Sail-Trim Simulator

Lucene University

Yaakov Kirschen’s other legacy

Sustain your creative drive in the face of technological change

Spring 83: a draft protocol intended to suggest new ways of relating online

Beer on Board in the Age of Sail (2017)

More Everything Forever

Show HN: Index – New Open Source browser agent

Get your Minitel back, the COMPUTEL videotex BBS is back

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

Show HN: My from-scratch OS kernel that runs DOOM

How a 20 year old bug in GTA San Andreas surfaced in Windows 11 24H2

CubeCL: GPU Kernels in Rust for CUDA, ROCm, and WGPU

You wouldn't steal a font

Yagri: You are gonna read it

Teaching LLMs how to solid model

Launch HN: Cua (YC X25) – Open-Source Docker Container for Computer-Use Agents

Apple and Meta fined millions for breaching EU law

Graphics livecoding in Common Lisp

AI Horseless Carriages

Clinical trial: novel nutritional formula treats gut microbial overgrowth

Google blocked Motorola use of Perplexity AI, witness says

MCP on AWS Lambda with MCPEngine

First Successful Lightning Triggering and Guiding Using a Drone

I Tried to Buy an Actual Barrel of Crude Oil (2015)

The Future of MCPs

My experience of participating to a startup weekend competition in Italy

Show HN: Node.js video tutorials where you can edit and run the code

C++26: more constexpr in the core language

DOGE worker’s code supports NLRB whistleblower

Sail-Trim Simulator

Lucene University

Yaakov Kirschen’s other legacy

Sustain your creative drive in the face of technological change

Spring 83: a draft protocol intended to suggest new ways of relating online

Beer on Board in the Age of Sail (2017)

More Everything Forever

Show HN: Index – New Open Source browser agent

Get your Minitel back, the COMPUTEL videotex BBS is back

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

Comments