Algorithm does real-time, city-wide ridesharing

John Timmer

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, and that doesn't even consider all the pollution this traffic creates.

Despite those numbers, most people wouldn't choose to use options that cut congestion, like public transit or ride sharing. 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. In addition, it's possible to make some optimizations like limiting the cars that are considered for servicing a trip (to ones that start off within a set distance of the passenger, for example). That saves considerable computational time.

In addition to the optimizations, the authors' approach allows them to set limits on things like the waiting time and the amount of additional time a given rider experiences in the car due to other passenger's needs. It can also be adjusted to perform optimizations for different vehicle sizes.

The authors find that, for low capacity vehicles like existing taxis, it's possible to perform a full optimization; larger vehicles (like small vans) force the use of algorithms that are only likely to produce a fully optimized trip schedule. In either case, if the total travel delay per passenger is capped at five minutes, the algorithms can always produce a result in less than 30 seconds.

And now for reality...

With the software in hand, the team then turned to their real-world data: every single taxi trip taken during a week in May of 2013. That's the time and location of every pick-up and drop-off for each of the city's 13,586 taxis.

The authors suggest that using their system can get a lot of these cabs off the roads. With a fleet similar to today's four-seat vehicles, only 3,000 would be needed to serve 98 percent of the ride requests. Riders would experience a mean wait of 2.7 minutes (generally quicker than hailing a cab) and an in-ride delay of 2.3 minutes due to handling other passengers. Switching to vans with a capacity of 10 passengers, similar numbers could be generated with just 2,000 vehicles.

As the capacity goes up, more passengers will typically mean more travel delays. But these delays stay below 100 seconds, and they're partly offset by the fact that people tend to get picked up faster. Each vehicle ends up traveling fewer miles than a typical cab, which should cut down on maintenance to boot. Jamming into a crowded van isn't anyone's idea of fun, but in most cases, these vehicles aren't that crowded. Even if you cut the number of vans down to 1,000 and checked during the periods of peak demand, only 40 percent would be more than half full.

Of course, cabs are only one of the sources of congestion in a typical city, so this wouldn't be a cure-all for traffic—assuming most riders were even interested in using it. The same system would probably work for on-demand car pooling, which would add significantly to the decreased number of cabs. And it's hard not to notice the overlap between a system like this and Elon Musk's vision for the future of Tesla vehicles, which sees them autonomously serving passengers when not in use by their owners.