Hacker News Reader

Comment by jfrd | Hacker News Reader

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!

View on HN

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.

Reply on news.ycombinator.com