Shortest-possible walking tour to 81,998 bars in South Korea | Hacker News Reader

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

math.uwaterloo.ca

435 pointsgeeknews139 comments

If you find this impressive, take a look at the 1.33 billion stars TSP solution provided by the same authors.

- Gaia DR2 (1,331,906,450 Stars): https://www.math.uwaterloo.ca/tsp/star/gaia2.html

> "The tour is at most 1.0038 times the length of a shortest-possible route."

But that presumably doesn't handle the relative motion of the stars, which makes the problem even trickier, since the distances will change as you travel, no? Or is my astronomy off base here?

I think your astronomy skills are correct, but if we have to worry about actual travel then you would also have to consider things like fuel capacity, refuel opportunities, the fact that you probably don't want to actually fly through a star but around it, etc.

I think it's still valid to have a distinction between travel logistics and having a route that's at least theoretically possible. I suppose what they've calculated would work with a star gate like system, but then I'm not sure what the point of having minimal distance would be.

Isn't the flying around problem just "e" since it is so many orders of magnitude less than the distance between stars that for this calculation it is irrelevant anyway?

The bar problem has its own issues. With that many bars some may close or new ones may appear during the time of the walk.

At that point we should also factor in time relativity, making it hard to measure the actual location of the stars at all.

This also doesn't handle new bars being opened and closed as you travel. Not to mention bouncers having bad days so you will have to revisit the bar.

I don't think this is presented as a means to get drunk around south korea. It's just an interesting application of TSP

But they are so far apart and move on roughly the same trajectory that it shouldn't really matter.

That's not true. The tour is 16.2 billion light years long, so even at the speed of light, it would take more than the current age of the universe to travel. Stars will move a lot over that period of time.

Yes I was assuming instant travel, even with one star the trajectory will be nonlinear.

That doesn't make sense to me. If you're assuming instant travel, then of course you don't need to account for stellar drift. Your response talking about stars "moving on roughly the same trajectory" doesn't make sense in that context. And anyway the GP was obviously not talking about instantaneous travel.

Unfortunate - they didn't pin the version of Three.js they were using for the interactive viewer at https://www.math.uwaterloo.ca/tsp/star/star10m_tour.html

And as a result it's been broken since May 2022: https://github.com/mrdoob/three.js/releases/tag/r141

I downloaded the HTML file and replaced the link with a versioned one, and the viewer still works just fine.

If you just use the simple-minded Bell Labs probabilistic algorithm, how much worse is that result?

The classic TSP approach is:

1. Hook up all the nodes in some arbitrary path.

2. Cut the path in two places to create three pieces.

3. Rearrange those three pieces in the six possible ways and keep the shortest.

4. Iterate steps 2-3 until no improvement has been observed for a while.

This is not guaranteed to be optimal, but for most real-world problems either finds the optimal result or is very close.

Note that the tour itself was found quickly using a heuristic solver (https://www.math.uwaterloo.ca/tsp/korea/computation.html), the achievement here and all the computation is to establish that this is the lower bound (assuming I understood correctly).

So, the heuristic solver worked pretty darn well :) Although, I’m not sure how close it would have been the heuristic algorithm you are describing (I suspect that it is considerably more advanced for good reasons, randomly picking will take too long to converge).

The algorithm that OP describes is more commonly known as 2-opt [0]. The heuristic used in this case is referred to as LKH which I assume means the Lin-Kernighan Heuristic [1]. The latter is sort of a meta generalisation of the former.

[0] https://en.m.wikipedia.org/wiki/2-opt

[1] https://en.m.wikipedia.org/wiki/Lin%E2%80%93Kernighan_heuris...

2-opt is a bit simpler.

LKH is a bit different, refers to Lin-Kernighan+Helsgaun -- http://webhotel4.ruc.dk/~keld/research/LKH/

Iirc the (probably simplified) LKH heuristic they used:

  For each iteration:
     apply some randomisation
     starting at each place
         cut the path in 2..n places
           reconnect in the most optimal way 
           if the new tour is the new best, save

n is a small number like 4 maybe 5?

2-opt: [a, b, ..., d, e]

reversing subarray from b to d is a 2-opt move.

3-opt (1 particular move):

a b c d e f

a e d c b f -- reversal from b to e

a e d b c f -- reversal from c to b

LK heuristic is a bit more involved, but focuses on continuing to reverse the subarray on the [b, ..., d] segment, with search and backtracking involved. (I think that's refered to as sequential k-opt moves, but I think it's already quite hard to know what exactly LK is, and LKH does much more)

By focusing on the subarray, assuming distance symmetry (length from b to e is same as length from e to b, but there are correct workarounds if this does not hold), you can evaluate the cost of the new route in constant time (but with bigger k there's more moves to evaluate https://oeis.org/A001171)

https://www.youtube.com/watch?v=tChnXG6ulyE

Author's presentation about it

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.

Proper routing is also an expensive computation. Yes you could just run A* or something on the roads but that would assume no closures, no one way roads, wouldn’t account for elevation change, ect. Using a proper routing API is almost certainly cost prohibitive

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

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

How many bars do you expect are in Ohio?

Less than 40,000

One would hope with 5x fewer people!

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…

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.

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

Sure, but Ohio has ~4200 bars[0]. Which is roughly 1/4 the ratio of bars to people.

[0]: https://rentechdigital.com/smartscraper/business-report-deta...

Ohioans love "big bars".

I don't think bars in Korea have parking minimums like they do in Ohio.

What's a parking minimum?

The minimum number of parking that needs to be available per seat/dining area.

https://codelibrary.amlegal.com/codes/plaincity/latest/plain...

Codes like these are the secret sauce of America's asphalt deserts, in which you'll find - by international standards - comparatively large restaurants and stores. Walkable cities tend to gravitate towards smaller equivalents, and more of them.

A minimum amount of parking spots per patron capacity. So a bar with 60 people capacity must have 15 parking spaces. [0]

Usually parking minimums are WAY too high in required parking spaces to make sense in most cases. Which leads to stuff like a arena having 5x the land area be parking than what is taken up by the arena itself. [1]

0: https://codelibrary.amlegal.com/codes/harrison/latest/harris... (this is for harrison, ohio, just happened to be the first result I found. it's under commercial -> "Tavern, bar, club, lodge, and dance hall.")

1: https://www.youtube.com/watch?v=OUNXFHpUhu8

The idea of a bar (ie a place people go to get drunk) with a dedicated parking lot strikes me as particularly bad for road safety. I'm baffled that this is not only encouraged, but mandated.

How do people do this in practice? Just drink and drive and hope they don't crash / get fined? Or does everybody bring 1 friend who sips colas the whole night?

We call the latter a designated driver [1] though as you can imagine sometimes the designated driver is "only" slightly drunk.

[1]: https://en.wikipedia.org/wiki/Designated_driver

Yeah but I mean, if everybody goes to the pub by car, does it mean everybody brings a designated driver? Or is this one of those things where everybody drives drunk but pretends nobody does?

Taxis exist.

The parking minimum is for taxis?

It's pretty common for people drive to the bar, get drunk, taxi/Uber/Lyft/DD home, and then return the following day to get their vehicle. I don't think it makes sense personally, but I also don't drink at all so I'm not a great judge here.

Makes perfect sense if people are not planning on having a big night and then do.

You can see people taxi/uber into a place if they are definitely planning to get blathered.

Mostly the latter IMO. The most popular bar where I grew up is on a busy highway with no housing within walking distance. Parking lot reliably fills up every weekend night, mostly with single occupancy vehicles. You can do the math.

Parking lots are not mandated for bars in the US, at least not everywhere. I helped my girlfriend's dad open a bar in Long Beach 20 years ago. The city required us to pay for the maintenance of three streetside parking spaces, but that was it. Pay the city. We didn't have to build anything that didn't already exist.

>Parking lots are not mandated for bars in the US, at least not everywhere.

This, they are making the mistake that all the people on /r/askamerican do over on reddit. Laws like this mostly aren't nationwide or even statewide, they are decided on a very local level.

>Usually parking minimums are WAY too high in required parking spaces to make sense in most cases.

That hasn't been my experience. Anytime I've wanted to go somewhere halfway popular the lot is usually full or nearly full. On the flipside, the lots are often empty during times when the business is closed, but reducing the size of the lot would exacerbate the issue of not being able to park nearby when the business is open. You aren't going to stop the US from being car centric, so you either have to dictate that businesses maintain a reasonable amount of parking or you have to have the municipality maintain several large parking structures throughout the city. Most cities would rather have the businesses that need the parking pay for the parking and most people would rather park near the businesses that they frequent.

> You aren't going to stop the US from being car centric

I think this isn't true. The same way suburbia spread out from cities, I think walkability can spread outwards too in baby steps.

For example, SF is relatively walkable/has public transit. The next step would be slowly removing parking minimums and making the areas surrounding SF more walkable. And then over time as people in those surrounding areas start using their cars less (not getting rid of them but at least trying to do short journeys on foot/bike/transit).

Over time that spreads outwards because half the community served by an area no longer needs a car for their daily travel and the envelope of walkability spreads further.

Sure you can slowly, over a long time, convert already dense areas into being less car centric, but you aren't going to make the rest of the country that way. Parking minimums, when they exist, are set by super local governments, they already don't exist or are set very low in areas of high density. The solution is to increase density, but again you aren't going to do that in the rest of the country. Random bars in Ohio are still going to have large parking lots, because land is cheap and given the choice, most people prefer less density.

82k places in Korea include any restaurant or joint or karaoke with a license to serve alcohol. Personally I would not care to call 80% of them "bar".

So in Ohio probably everything with class C and D license. How many is not public but probably many times more than 4k.

Many actual street level bona fide bars in Seoul (which has half of all the people of the entire country and the most bars by far) are tiny rooms that fit a few people each. But you always have a "bar street" with 50 of those next to each other.

Ok, that gets the numbers in line -- there are about 27,000 liquor licenses in Ohio, according to a random Google, which is about the same per capita.

South Korea apparently ranks #97 on alcohol deaths, so it's apparently not a problematic number of bars, by global standards.

A lot of bars in walkable cities fit about 10 or fewer people. East Asia in particular has loads of tiny bars.

Plus being able to walk or take a train home makes them far more accessible for people than needing to drive home.

Just to compare, they also have a tour for the UK https://www.math.uwaterloo.ca/tsp/uk/index.html : 49,687 pubs.

They are such an urban phenomenon. A largely empty rural state, with the legacy of prohibition, where you have to drive? That's going to have way fewer drinking locations. A culture of hanging out and drinking requires walkable urbanism. Many of the UK pubs pre-date the invention of the car; "peak pub" appears to have been the late 1800s with over 100,000.

I'm impressed that Korea has more than the UK, but this is definitely going to be a matter of size and the tiny Korean bars.

> A culture of hanging out and drinking requires walkable urbanism.

I don't think that's really true. In the UK, villages had pubs. Gradually some of the villages were joined together into larger cities, and the pubs remained. It wasn't planned as walkable urbanism.

You didn't have to plan to get walkable urbanism before cars. It just happened because everyone needed a pub, store, school, etc. within walking distance.

But it wasn't urban. That's my point.

This is also upper-bounded by the law; Ohio only issues one class D-5 liquor license (license to sell beer, wine, and spirits) per 2000 residents, which roughly maxes it out at ~5950 bars (in practice this looks to be rounded up on a per-town basis, making this an underestimate). An Ohio with the population of South Korea would only be allowed ~25000 bars.

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. :)

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

americans always compare massive cities to empty states

Snark aside - I used this site which compares the country question to the location closest to you. I live in ohio. https://www.mylifeelsewhere.com/country-size-comparison/unit...

South Korea has 5x the population of Ohio, but around 27x the number of bars [1]. So it really is a lot of bars.

[1] https://www.ibisworld.com/us/industry/ohio/bars-nightclubs/1...

As someone married to a Korean, I am not surprised in the least. Every single one I have met (males at least) drinks like a fish. It is impossible to describe to a westerner just how ingrained the drinking culture is over there.

They drink more than Eastern and Northern Europeans. It's insane!

Empty lol

The entire US and North America is massively more empty relative to almost anywhere else, even most perceptually sparse countries. Many of European countries are 5-10x denser than US.

  0: https://en.wikipedia.org/wiki/List_of_countries_and_dependencies_by_population_density

And South Korea has one of the highest rates of stomach cancer.

To be fair, it does sound like a pretty tough place to stomach.

After living there for about four years, my mind goes immediately to soju. Not sure if there is a connection, but that’s something I might deep dive with an LLM today.

"Bar" doesn't mean the same thing in every country. In Spain although a bar serves alcohol of all kinds it is also where one eats breakfast and lunch and gets a coffee. They are indispensable social centers and even a tiny town of 150 has one.

Town? More like village. You can have a nearly empty church, but there's no village without a bar.

If this is correct, it seems like Seoul has over 40x the number of bars that Chicago has, despite having only about 4x the population

How in the hell?

The bars may be much smaller.

Many countries have much more used “public” spaces, and people spend much more time in them, together.

The idea of driving home to the suburbs and locking yourself into your private home is very North American.

I just got back from10 months across Europe. The number of people in public places eating, chatting and just spending time (no simply going somewhere) makes LA or Chicago look like a ghost town.

Sure, but that's still an astronomically higher number of bars

the UK in totality has 45k pubs, nearly half Seoul's number

this is mostly emblematic of South Korea's major alcoholism problem. way too many bars and too much drinking.

I checked a few and there's a lot of restaurants included.

https://www.math.uwaterloo.ca/tsp/korea/data/korea81998.xy.t...

South Korea really said "you will not be thirsty on our watch."

What's really cool is if you go to a site like [0] that shows the "true" size of countries etc. (i.e. not distorted by a projection), Indiana is probably the most analogous state to South Korea, in terms of size and shape. But South Korea has 7x the population of Indiana!

Really puts into perspective a movie like "Train to Busan", which would be like taking a train from Gary to Madison!

0: https://thetruesize.com

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

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

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

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

Gotta respect the planning that went into choosing a problem that's both absurd and actually solvable

reminds me of a question they used to ask in the Irish army back in the 60s. My Dad told me this. "How do you get from Bachelor's Walk to Collins Barracks without passing a bar?". People would spend hours and days working on the answer. In the end, the answer was "Go in to every one".

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.

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/.

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.

Yeah, I probably mixed it up with the Hamiltonian Path problem. It was a long time ago

>80k with proof

Post proof.

During COVID I made it a goal to walk every street in my town using the web-based CityStrides (https://citystrides.com/) tracker. It keeps tracks of streets you have walked and lets you know what percentage of a town you have walked. It didn't optimize my routes for coverage, but it was a fun mental puzzle to plan out my walks to hit as many streets as possible without duplication. An automated tool might be fun, but doing it by hand was part of the journey as it were.

As you browse the CityStrides site you can find people's LifeMaps which show all their walking. Some people have done amazing amounts of walking. See this user for example and their coverage of Paris, France...

https://citystrides.com/users/15259/map#48.85741101618777,2....

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

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.

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

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

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

Isn't comma the decimal separator ;)

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

It’s not that many bars.

It's always worth spending 30s verifying something like this by reversing what you're arguing - in this case, 5000 * 365 * 40 is obviously more than 82,000.

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

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

I’d like to call it a stumble :)

I looked at near my home, they missed a few. A issue is that in Korea a lot of the local spots are not on any public maps.

Has anyone done the opposite of this, finding the longest possible route?

This is both hilarious and genuinely impressive. A TSP solution involving nearly 82 000 bars? That's a level of dedication to both math and beer I didn't know I needed in my life

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.

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.

I zoomed in on the map and discovered at least one shortcut where one could have saved a few seconds, now is that proof enough that the solution is not optimal? :P

Where?

Does it put the order of others off,i.e. a net loss?

Is that one of the problem quantum computers would resolve instantly if it is actually possible to scale them up?

Very interesting..

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

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

There was a man who documented his travel to every country in the world. Not long before he was finished, South Sudan gained independence and he had to take a special trip there to complete his journey, which apparently had already completed all the other countries in Africa long ago.

Seem i do need a pair of dry socks for part of the walk.

Does it account for "pit stops"

Kids, we're going on a road trip!

traveling drinking man's problem

No it's: The traveling ale-man's problem. ;)

Sadly I'm not a Soju fan

impresive, I have forgot TSP after graduated.

“The locations were downloaded from a database maintained by the Korean National Police Agency.”

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

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

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

Reply on news.ycombinator.com