4 ms·

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 e

by petra 10y ago

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 10y ago
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 10y ago
  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 https://www.itu.dk/people/pagh/CAOS/DARP.pdf - altough it's a bit old, so maybe results have improved since.
  - lern_too_spel 10y ago
    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 10y ago
      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 ?
      - deleted 10y ago
        [deleted]
      - lern_too_spel 10y ago
        I suspect that preordering rides will be a niche case. Most people will be happy with the latency of ordering a car when they need one with an estimate of how long it will take to be picked up when they open the app (like existing Uber Pool). They will only order a car in advance if they need a guarantee that a car will pick them up at a particular time and wait for them, and in that case, it will make sense to dedicate a car to the user for that trip — nobody else will want to wait in the car while the scheduled user gets ready. That particular users have commutes at around the same time every weekday, plus or minus half an hour depending on their first meeting and when they finish their work or close their shift or socialize with coworkers, will be better handled by the system placing empty cars appropriately.

by petra 10y ago

lern_too_spel 10y ago

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 10y ago
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 https://www.itu.dk/people/pagh/CAOS/DARP.pdf - altough it's a bit old, so maybe results have improved since.
- lern_too_spel 10y ago
  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 10y ago
    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 ?
    - deleted 10y ago
      [deleted]
    - lern_too_spel 10y ago
      I suspect that preordering rides will be a niche case. Most people will be happy with the latency of ordering a car when they need one with an estimate of how long it will take to be picked up when they open the app (like existing Uber Pool). They will only order a car in advance if they need a guarantee that a car will pick them up at a particular time and wait for them, and in that case, it will make sense to dedicate a car to the user for that trip — nobody else will want to wait in the car while the scheduled user gets ready. That particular users have commutes at around the same time every weekday, plus or minus half an hour depending on their first meeting and when they finish their work or close their shift or socialize with coworkers, will be better handled by the system placing empty cars appropriately.