The December 2022 issue of IEEE Spectrum is here!

Close bar

MIT’s Superefficient Dispatching Algorithm Minimizes a City's Taxi Fleet

An app-based algorithm could cut Manhattan's cab population by nearly a third

2 min read
A group of NYC taxis.
Photo: iStockphoto

Researchers at MIT say they’ve found an efficient dispatching algorithm that can cut a city’s fleet of taxis by 30 percent.

They describe their work in a paper published today in Nature.

“New York would need 30 percent fewer vehicles if the taxi fleet, even with human drivers, is managed better,” Carlo Ratti, the director of MIT's Senseable City Lab tells IEEE Spectrum. That’s a big savings, both in taxis and in the space they take up on city streets. New York’s 14,000-odd taxis log some 500,000 trips a day. 

The technology would seem to help the beleaguered taxi business fend off private ride-hailing services, like Uber and Lyft. They have their own algorithms, optimized partly to match drivers and passengers and partly to pool ride-sharing customers.

Ride sharing was the first thing Ratti and his colleagues studied, back in 2014, when they determined that if taxi passengers in Manhattan could put up with just a five-minute delay, nearly 95 percent of their trips could be shared. That would cut the total time that passengers spend in taxis by up to 40 percent.

This time, the researchers asked how a better dispatching model could make better use of the taxi fleet as it’s run today, that is, without assuming much ride sharing. They call it the minimum fleet problem, and they handle it as a master pool player does, by making each shot set up the next one. By giving due weight to minimizing the distance between a taxi’s destination and the origin of its next potential trip, the model moves more passengers per vehicle over a given period of time.

A perfect solution would lay to rest the famous traveling salesman problem, which tries to find the shortest path a salesman must take to hit every spot on his route. That problem quickly becomes intractable, however, as the number of spots increases. You could solve it for Mayberry, but not for Manhattan.

Instead, the MIT researchers created what they call a vehicle sharing network, similar to the network they used in 2014 for optimizing ride sharing. It looks like a graph in which each node represents a trip and each line linking two nodes represents a pair of trips that one vehicle can handle. Manipulating the layout of the graph provides ways of improving (if not perfecting) the solution.

What if all of Manhattan’s 280,000 or so vehicles were robocars, driving themselves while under the control of the MIT master plan? “If we were to look at a fully autonomous city,” Rotti says, “the reduction in vehicles would be closer to 50 percent.”

The Conversation (0)

Chinese Joint Venture Will Begin Mass-Producing an Autonomous Electric Car

With the Robo-01, Baidu and Chinese carmaker Geely aim for a fully self-driving car

4 min read
A black car sits against a white backdrop decorated with Chinese writing. The car’s doors are open, like a butterfly’s wings. Two charging stations are on the car’s left; two men stand on the right.

The Robo-01 autonomous electric car shows off its butterfly doors at a reveal to the media in Beijing, in June 2022.

Tingshu Wang/Reuters/Alamy

In October, a startup called Jidu Automotive, backed by Chinese AI giant Baidu and Chinese carmaker Geely, officially released an autonomous electric car, the Robo-01 Lunar Edition. In 2023, the car will go on sale.

At roughly US $55,000, the Robo-01 Lunar Edition is a limited edition, cobranded with China’s Lunar Exploration Project. It has two lidars, a 5-millimeter-range radar, 12 ultrasonic sensors, and 12 high-definition cameras. It is the first vehicle to offer on-board, AI-assisted voice recognition, with voice response speeds within 700 milliseconds, thanks to the Qualcomm Snapdragon 8295 chip.

Keep Reading ↓Show less