Traveling Salesman is NP-Hard. Don't think it is solvable with current technology.
The Concorde TSP solver can apparently solve instances with 85.6k cities to optimality. Pretty amazing!
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.
You’re right that the problem space is simply matching available drivers to riders.
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.
As soon as humans and the real world are involved, seemingly contradictory criteria need to be met.
Algorithms like A* search may not be able to capture these criteria robustly enough.
Example: a driver may be assigned the optimal route, but because they are human will not want to sit and wait for 15 minutes between several of their rides
A* is great for path finding but it's not a global panacea for all subproblems related to ridesharing
Likely one of Uber/Lyfts greatest strengths in their algos is discovering the E[X] of those heuristics. This could probably be captured from the human dispatchers as well.
"You have to leave enough time in-between trips so the driver isn’t late for their next client." also seems bizarre, as you should just be routing the minimal time cost set of vehicles to those awaiting rides. This seems to imply most rides are scheduled pickups?
Did you read the article? This is their entire business model right now.
Given that drivers are driving the shorted distance/time route at the speed limit, treating customers with respect, arriving on time to scheduled pickups, etc. The next thing to focus on is scheduling/filling orders such that drive time is maximised.
You are optimizing for least amount of time riders have to wait, not just for shortest distance driven.
Point being though that it's fundamentally a deterministic combinatorial problem. And they have the added benefit in this case of only worrying about prescheduled trips that need to be calculated the day before. It's not trivial, but it's an algorithmic problem that has no need for inductive output.
I worry about this. Travelling salesman is a solved problem. Throwing "AI" into the mix sounds like someone was sold a bridge.