Hacker News Reader

Comment by Sai_ | Hacker News Reader

https://en.wikipedia.org/wiki/Travelling_salesman_problem

Traveling Salesman is NP-Hard. Don't think it is solvable with current technology.

Surprisingly you can solve massive TSPs using heuristics. The solutions are not guaranteed to be optimal, but they can get very close to optimal without a crazy amount of computing power.

The Concorde TSP solver can apparently solve instances with 85.6k cities to optimality. Pretty amazing!

Ride share companies are surviving so it’s clear that some good enough solutions do exist.

There’s a difference between the algorithms ride shares have to use and the heuristic based solution for 85.6k cities.

The graph for ride shares is constantly changing as passengers request rides from random starting points to random destinations.

This version of TSP is much harder to solve.

Sorry but how is ride share problem a TSP problem? Rides are assigned one at a time and I do not think they would take into account future rides while doing the assignment optimization.

Not my industry, but imagining that they accept rides within a 48 hour windows from now. You’d quickly get something somewhat similar to a TSP. But given that you have lots of additional constraints (people tend to have a clear idea when they want to get from A to B) compared to the classical TSP, it might actually be easier to solve. As those constraints limit the paths you must evaluate.

True. I got derailed because the person I replied to and the replies to my comment used to TSP formulation to discuss this.

You’re right that the problem space is simply matching available drivers to riders.

Being NP-hard doesn't mean it's unsolvable at all. It means it's not solvable quickly. Google maps does this millions of times per day... the number of points on the trip are few enough that you can brute force it perfectly or use a heuristic to solve it faster but less optimally. Very solvable just not optimizable algorithmicly.

My answer that you are replying to ends with “…with current technology” which contains what you said.

The technology doesn't matter unless you're going to make a far-fetched quantum computer argument. This is pure math.

Only in the worst case and large N. For practical problems, it’s solvable for tens of thousands of nodes.

A cab service with unknown, frequently updated nodes where edge weights - driving distance from last drop to next pickup- can vary, would qualify as pretty bad version of TSP.

You can come up with a good enough solution but it’s not “solved”.

This “good enough” solution starts to break down whenever there is a huge concentration of drivers in a location. If this weren’t the case, ride shares wouldn’t have had to add a cancellation fee and hidden destinations from drivers.

Reply on news.ycombinator.com