Skip to content ↓

How many taxis does a city need?

New dispatching approach could cut the number of cars on the road while meeting rider demand.
Watch Video
Press Inquiries

Press Contact:

Karl-Lydie Jean-Baptiste
Phone: (617) 253-1682
MIT News

Media Download

Rear view of yellow taxi in city traffic
Download Image
The algorithm represents the shareability of the taxi fleet as a graph, a mathematical abstraction consisting of nodes (or circles) and edges (the lines between nodes). In this case, the nodes represent trips, and the edges represent the fact that two specific trips can be served by a single vehicle.
Download Image
Caption: The algorithm represents the shareability of the taxi fleet as a graph, a mathematical abstraction consisting of nodes (or circles) and edges (the lines between nodes). In this case, the nodes represent trips, and the edges represent the fact that two specific trips can be served by a single vehicle.
Credits: Courtesy of the researchers

*Terms of Use:

Images for download on the MIT News office website are made available to non-commercial entities, press and the general public under a Creative Commons Attribution Non-Commercial No Derivatives license. You may not alter the images provided, other than to crop them to size. A credit line must be used when reproducing images; if one is not provided below, credit the images to "MIT."

Close
A new algorithm represents the shareability of the taxi fleet as a graph, a mathematical abstraction consisting of nodes (or circles) and edges (the lines between nodes). In this case, the nodes represent trips, and the edges represent the fact that two specific trips can be served by a single vehicle.
Caption:
A new algorithm represents the shareability of the taxi fleet as a graph, a mathematical abstraction consisting of nodes (or circles) and edges (the lines between nodes). In this case, the nodes represent trips, and the edges represent the fact that two specific trips can be served by a single vehicle.
Credits:
Courtesy of the researchers

The rise of self-driving cars is set to dramatically alter the way we move around cities in the future.

In particular, private car ownership is expected to shift toward shared mobility services, with vehicle fleet operators offering on-demand transportation. This should help to reduce traffic in urban areas and cut greenhouse gas emissions.

For these services to grow, however, accurate and computationally efficient algorithms will be needed to effectively match individuals with on-demand vehicles, in order to cope with the hundreds of thousands of trips that are routinely made within large cities.

But researchers have yet to solve the problem of how best to size and operate a fleet of vehicles, given a particular level of demand for personal mobility.

Now, in a paper published today in the journal Nature, a team of researchers coordinated by Carlo Ratti, director of MIT’s Senseable City Lab, unveil a computationally efficient solution to this problem, which they dub the “minimum fleet problem.”

“We started looking into this problem motivated by the increasing trends toward shared mobility, which will likely become even stronger with the transition to autonomous vehicles,” says Ratti, who is also a professor of the practice in MIT’s Department of Urban Studies and Planning. “If demand for mobility is served by fleets of shared vehicles, a fundamental question is: How many vehicles do we need to serve the mobility needs of, say, a city such as New York?”

Researchers have previously attempted to solve this question using variations of the “traveling salesman problem,” which aims to minimize the total distance travelled by a salesman who must visit a given number of destinations in a city.

However, it has so far proven extremely difficult to find an optimal solution to the travelling salesman problem, even using today’s powerful computers. As a result, good solutions for fleet management have been severely constrained in size, meaning they can only be computed for fleets with just a few tens of vehicles, according to Paolo Santi, a research scientist at the Senseable City Lab and a senior researcher at the Italian National Research Council CNR, who led the research team.

This is not enough to meet the needs of a large city such as New York, he says.

“If we were to consider replacing the current taxi system in New York with an optimized fleet of vehicles, we would have to find the best way of serving the around 500,000 trips made in a day, which are currently served by about 13,500 taxis,” says Santi.

Instead, the researchers used a network-based model they have dubbed the “vehicle sharing network” to approach the problem. They previously used a similar approach, called the “shareability network,” in a 2014 paper to find the best way to share rides in a large city.

The algorithm represents the shareability of the taxi fleet as a graph, a mathematical abstraction consisting of nodes (or circles) and edges (the lines between nodes). In this case, the nodes represent trips, and the edges represent the fact that two specific trips can be served by a single vehicle.

Using this graph, the algorithm was able to find the best solution for fleet sharing.

The team, which also included Moe Vazifeh, the first author of the paper and formerly a lead researcher at the Senseable City Lab; Giovanni Resta, a researcher at the Institute of Informatics and Telematics of CNR; and Steven Strogatz, a professor of mathematics at Cornell University, tested the solution on a data set of 150 million taxi trips taken in New York over the course of one year.

They computed travel times using the actual Manhattan road network and GPS-based estimations derived from the taxi trip data set.

They found that real-time implementation of the method with near-optimal service levels reduced the fleet size needed by 30 percent.

The solution does not assume any individuals must share a journey. Instead, it simply involves the reorganization of the taxi dispatching operation, which could be carried out with a simple smartphone app.

The solution could become even more relevant in the years ahead, as fleets of networked, self-driving cars become commonplace, says Ratti.

“If we look at Manhattan as a whole, we could theoretically satisfy its mobility demand with approximately 140,000 vehicles — around half of today’s number,” he says. “This shows that tomorrow’s urban problems regarding mobility can be tackled not necessarily with more physical infrastructure but with more intelligence, or in other words: with more silicon and less asphalt.”

The researchers demonstrate that the problems of movement in cities can be made much more efficient by minimizing the size of the transport fleet through a centralized dispatching system, says Michael Batty, a professor of planning at the Center for Advanced Spatial Analysis at University College London, who was not involved in the research.

“They demonstrate some impressive results with respect to data in New York City, and they suggest that their algorithm could be used for many other transit and travel systems in large cities,” he says.

The researchers are now planning to carry out further work to explore the minimum number of parking spaces needed in cities, alongside insurance firm Allianz.

Press Mentions

Xinhuanet

MIT researchers have developed an algorithm that can accurately determine how many taxis a city needs, providing a way to reduce the number of cars on the road, according to Xinhua. “Using the new algorithm, they found the fleet size of cab-hailing service in New York could be cut down by about 30 percent in an optimal scenario.”

Related Links

Related Topics

Related Articles

More MIT News