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.
