Credit: Pixabay.

The advent of ride-sharing apps has been hailed as an inflection point in transportation. Companies like Uber and Lyft are severely disrupting transportation and will continue to transform the way people ride from A to B once self-driving cars become more common.

One of the most appealing things about ride sharing, from an environmental perspective, is that it makes car ownership redundant in many cases. As private car ownership is expected to shift toward shared mobility services, there should be a significant reduction of traffic in urban areas and greenhouse gas emissions. This is happening already, as evidenced by a previous study which focused on Austin, Texas, a city where Uber and Lyft were temporarily forced to cease operations due to a local ordinance. According to the study, 41% of those surveyed turned to their own vehicle to fill the void left by apps ceasing operations and 9% actually bought an additional car for this purpose.

However, in order for mobility services to operate at maximum efficiency, we require computationally efficient algorithms that can match people with on-demand vehicles. The problem is that this is a lot harder than it sounds. Even using today’s powerful computer, plotting the optimal routes with complex variables can be a daunting task, which is why good solutions for fleet management have been severely constrained in size, keeping them to a few tens of vehicles.

This is obviously not an option when dealing with big cities. New Yorkers, for instance, are served by approximately 13,500 taxis which make around 500,000 trips daily.

Researchers at MIT’s Senseable City Lab found a workaround, however. They recently unveiled 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?”

The MIT team wrote their algorithm by using variations of the “traveling salesman problem,” which aims to minimize the total distance traveled by a salesman who must visit a given number of destinations in a city.  In February 2018, the Washington Post reported that it would take at least 1,000 years for a computer to find an optimal route to only 22 points. However, the MIT researchers used a different approach —  a network-based model dubbed “vehicle sharing network”, which was previously used in 2014 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 structure amounting to a set of objects in which some pairs of the objects are, in some sense, “related.” Each trip is represented by a node, while the edges of the graph represent the fact that two trips can be served by a single vehicle.

In order to test their solution, Ratti and colleagues ran the algorithm using a data set of 150 million taxi trips taken in New York over the course of one year. The researchers learned that if their method was implemented, the fleet size could be reduced by 30% while still achieving the same service levels. An even greater reduction of vehicles would be achieved if the solution involved individuals sharing a journey, which the algorithm doesn’t take into account. Instead, the model simply reorganizes the whole taxi dispatching operation, which is enough to vastly optimize travel time. As more and more cars become networked and come with autonomous functions, this sort of model could become even more efficient and appealing.

“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 findings appeared in the journal Nature.