6 ms·

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 aft

by 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

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.