Algorithm does real-time, city-wide ridesharing
Anyone who’s ever been stuck in stop-and-go traffic would be happy to tell you that congestion is a waste of time. But the true scale of the waste is difficult to comprehend. It’s estimated that congestion costs the US one percent of its annual GDP, as people waste otherwise productive hours and fuel sitting in their vehicles. That doesn’t even consider all the pollution it creates.
Despite those numbers, most people wouldn’t choose to use options that cut congestion, like public transit or ridesharing. In many cases, that’s because these alternatives require giving up some autonomy, as you can’t necessarily go where you want whenever you want.
A paper in this week’s PNAS suggests that doesn’t have to be the case. Using a real-world database of fully autonomous travel—a week’s worth of New York City taxi rides—the authors demonstrate an algorithm that can service travel needs in real time with minimal waits for a ride. The result would be far fewer cars on the road. Even with standard cabs, only a quarter of today’s taxi fleet would be required to service all the ride requests.
The work was done by a joint MIT/Cornell team, who decided to take on what’s essentially a massive computational challenge. Figuring out how to ride share is more than just matching passengers with vehicles. You want to match them with a vehicle that’s already nearby, meaning the wait for the ride is minimal. Then, other passengers have to be added in a way that doesn’t result in a significant diversion from the first passenger’s trip. Once a ride is shared, there needs to be a smooth addition and subtraction of passengers, such that the vehicle ends up empty as infrequently as possible.
As the paper puts it, “A major challenge when addressing this problem is the need to explore a very large decision space, while computing solutions fast enough to provide users with the experience of real-time booking and service.”
The biggest part of that challenge is finding the optimal solution within that entire decision space; algorithms often get hung up on a local optimum, or can’t explore the entire space within a reasonable amount of time. Fortunately, the authors recognized that they don’t need the global optimum. A reasonably good local optimum may not be the most efficient, but it’s good enough to get people in cars quickly. A first round of trip assignments is done using what’s called a greedy algorithm, which simply starts with the longest trips first and tries to minimize travel delays.
From there, the algorithm attempts optimizations, but it’s capable of producing an answer at any time if a decision has to be made.
