Credit: Provided

The way people get around, particularly in big cities like New York, is changing rapidly, but a fundamental problem remains unsolved: how to best size and operate a fleet of vehicles, especially traditional taxis and particularly given taxi riders’ attitudes toward sharing.

A study conducted by the Massachusetts Institute of Technology’s Senseable City Laboratory – with important input from Steven Strogatz, the Jacob Gould Schurman Professor of Applied Mathematics – offers a network-based solution to the classic “minimum fleet problem:” Given a collection of trips – specified by origin, destination and start time – what is the minimum number of vehicles needed to serve all the trips, without incurring any delay to the passengers?

“You could view it as, in the best of all possible worlds, what’s the fewest cabs that we would need?” said Strogatz, a Stephen H. Weiss Presidential Fellow, who collaborated with MIT’s Carlo Ratti, senior author of “Addressing the Minimum Fleet Problem in On-Demand Urban Mobility,” which published May 23 in Nature.

Instead of “ride-sharing,” Ratti and Strogatz considered the notion of “vehicle sharing” in their model system. Using a 2011 data set of 150 million taxi trips taken in New York City over a year, the group used the Hopcroft-Karp algorithm – a matching formula co-developed more than 40 years ago by Cornell computer science professor John Hopcroft – to solve the problem of matching rides to riders with the fewest vehicles possible.

Strogatz admits that there are portions of the study that assume best-case conditions: All the desired trips are known in advance, and no passenger should have to wait for their taxi to arrive.

“And no driver should be driving around for more than 15 minutes between drop-off and the next pickup,” Strogatz said. “Those are all pretty strong assumptions.”

The results: With optimal service levels, their research allows for a 40 percent reduction in fleet size, compared with current taxi operation. Even if trips are not known in advance, a real-time version of the algorithm – in which customers hail rides with an online app – allows for a 30 percent reduction.

Researchers openly state that their approach assumes a “top-down” model, in which trip requests and vehicle dispatching are all centralized, which is obviously not the case in the real world.

“To some extent,” the researchers wrote, “our results can then be seen as a quantification of the well-known game-theoretic notion of ‘price of anarchy’ in urban taxi operation.”

“Price of anarchy” refers to the notion that there is some efficiency loss in a system’s lack of coordination.

“While optimal from the vehicle operation and environmental viewpoint,” they wrote, “a monopolistic market is however highly undesirable for many other reasons, most importantly lack of competition and consequent higher prices.”

Nevertheless, the group’s computational analysis of the data – from which they’ve culled results in past work, including a 2017 paper on urban ride-sharing– proposes that there exists a more efficient way to deploy taxis, lowering emissions and traffic congestion in the process.

“The point I think we’re making is that reducing the anarchy – having a little bit of planning and optimizing – seems to go a long way,” Strogatz said.

The researchers say their results could become even more relevant down the road as fleets of networked, autonomous vehicles become commonplace.

“This shows that tomorrow’s urban problems regarding mobility can be tackled not necessarily with more physical infrastructure but with more intelligence,” Ratti said. “In other words: More silicon, and less asphalt.”

Ratti, a renowned architect and professor in MIT’s Department of Urban Studies, holds a fellowship position at Cornell Tech.