[petra]

Not choosing optimal routes would lead to a more expensive service, which is critical for a commodity.

As for routes only having 4 stops - sure, but that's after you chosen which users will drive in the same car/trip, which is hard in itself.

BTW the dial-a-ride problem is quite similar to the ridesharing problem, and the complexity there is O(number_of_pickup_and_drop_points^2 ) [1]

[1]https://www.itu.dk/people/pagh/CAOS/DARP.pdf - altough it's a bit old, so maybe results have improved since.

[lern_too_spel]

If you compute routes that are close enough to optimal, it doesn't matter. If you compute good enough routes quickly, that will likely reduce costs more than computing the best routes slowly. There are enough other areas of optimization that will give a better return on investment that it doesn't necessarily make sense to invest in finding the actual best routes.

Also, this particular problem is much easier than you surmise. The problem statement isn't a set of millions of cars sitting in particular locations with a set of millions of riders with particular sources and destinations and matching them and ordering routes to minimize fuel usage or median rider travel time. The problem is of hundreds of nearby cars traveling existing routes and matching a single new rider with a particular source and destination to one of those cars. There is a secondary problem of where to send empty cars that is more interesting.

[petra]

I agree. But that's true for current Uber .

But once we start talking about UberPool and via its pretty close for the problem I describe, especially if we're talking about the commute , with a possibility of people preordering rides sometime in advance(or even some prediction abilities about that).

As for the other option, carpooling ,it depends how far will people be willing to drive out of their way for that extra income. But being conservative and I they won't go out of their way , the problem becomes assigning riders to a million bus routes with small capacity, which seems to naturally break this problem into many ,largely independent problems , and may prevent any big exponential complexity.

Don't you agree ?