133 — The Merits of Sharing a Ride

I’ve read before about ride-sharing and the associated NP-hard problems that arise when matching resources with demand. This paper extends the problem to accomodate multi-agent models with multi-agent demands; essentially, it proposes a solution to the multi-rider pickup problem.

The scenario is that $n$ riders want to ride at a given time, but either there are fewer than $n$ drivers, or the taxi service wants to minimize expense by “doubling up” riders on similar routes. (Anyone who has gone a long distance out of their way on Uber’s or Lyft’s existing services knows that the current algorithms are very imperfect.)

There are several challenges with multi-rider situations: For example, if each rider starts with a delay tolerance, now not only must the original driver’s time-to-pickup be optimized, but the algorithm must also accomodate the time spent driving to another user’s destination with the first user still in the car. A succint way of saying this is that the longer a user waits, the more direct of a route you should try to assign for them. Meanwhile, these costs must be balanced against the direct financial costs of gas, driver strain, and ride cancelation.

To model this complex system, Ehsani and Yu used the NYC Taxi dataset, capturing all times and locations of pickups and destinations of the Yellow Cab taxi service.

The algorithms and techniques explored in this paper demonstrate that you can greatly optimize rides by anticipating a probability distribution of the next ride to be requested. However, while this method is classified as “online” by the authors, they note that a more ideal algorithm would accomodate fully realtime requests that take place one a ride is already in progress, and proactively direct taxis to congregate near areas of high next-ride-probability rather than reactively distributing them in response to requests.