[petra]

One guess: the routing problem(the vehicle routing problem) is a core computer science problem, for decades. Tons of research have been done about it. I don't expect Google or Uber to have any breakthroughs there, because it's pure luck. But maybe they will, or maybe they'll will ackuire someone. Let's put it down to pure luck.

But assuming no brekathrough happens: one company that has tons of experience in that field is UPS, they are just finishing building a new system for running their vehicle-routing for 50K routes in the US daily, ~120 points per route, i.e. 600K customers daily. They invested ~$300 million in that system(and they employe hundreds of phd's) and they say it will give them a savings of less than 1% of revenue - just to get a sense how mature those systems are.

On the other hand, it seems that have larger access to customers could enable much more ideal routes, both in cost, customer time and maybe social factor(if social matches will be part of ride sharing). So i believe that to be key to winning.

And i don't think anybody can beat Google in marketing to android users, and even in the US, with iPhone's 40% share(but more wealthy users) - that's avery big advantage for Google.

On the other hand, i think Google prefer not to start a huge service that employs many people, and than have self-driving cars make them unemployed and suffer the huge reputational damage. So they won't go into true shared taxis like ridewithvia.com seems to be doing very sucsessfuly, and instead stick with wazer-rider , enabling drivers to give a lift to poeple for some very modest fee.

So to a certain extent, the winner in that battle would be determined by which approach of those two will win.

[lern_too_spel]

For this problem, they don't need to find the optimal routes, just reasonable routes. Individual routes have only four stops at a time. No breakthroughs required.

[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 ?