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. :)
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
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.
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.
>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.
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.
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.
I am overwhelmed with the thought of nearly 82 thousand bars within a country roughly the size of Ohio.
That country has a population of 52 million, i.e. about 5 times Ohio.
NYC that is like 20 miles across has 11,000 locations that serve alcohol.
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. :)
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.
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.
Oh no, looks like a few new bars opened up, and a few others closed. Time to recalculate.
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.
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.
It would suck to get to bar 51,248 only to find out it's now permanently closed
Kids, we're going on a road trip!
Very interesting..
Is anything supposed to happen if you click on those red circles? I was hoping it will show name or other info!
If you spent 40 years of your life on this path, you would still be visiting 5.616 bars per day. Nuts.
That’s also not considering whether they’re open or existing anymore after so much time has passed.
Less than 6 bars a day is pretty doable! :-p
Isn't comma the decimal separator ;)
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 :)
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".)
>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.
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.
I also expected to get an actual proof.
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.