# New Algorithm Could Save Cities from Too Many Taxis

Over-crowded streets are a nuisance for anyone investing in a taxi, but this MIT algorithm could reduce that headache by 30 percent at least.

From Uber to Lyft, the number of taxis and rideshare services on the roads have skyrocketed within the last few years. With an increased reliance on these services could come even more cars on the road -- be it taxis or rideshares -- and thus, even more congestion. However, a team of researchers from Massachusetts Institute of Technology developed an algorithm that might spare drivers and passengers the headache of traffic while also meeting rising demands.

"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," the researchers explained in a statement.

The team used this graph to feed the algorithm and thus determine the best solution for rideshares and taxis.

"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," said 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?"

Previous attempts to solve these issues were also found in other mathematical attempts. The most famous way previously used to name the problem was the "traveling salesman problem," in which mathematicians would minimize the total distance a salesman would travel if he had to visit a certain number of stops in a day of sales.

"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?"

However, researchers have come across issues in finding a consistently optimal solution -- even leveraging computers and updated computing systems. There's also the issue of various companies' fleets determining optimal solutions for their particular companies. A number of factors have led to these previous attempts at calculating taxi density on the road failing, according to Paolo Santi. Santi serves as a research scientist for the Senseable City Lab and also as the Italian National Research Council CNR. That group was responsible for leading the research team.

The researchers used data from one of the globe's most congested areas -- Manhattan. They estimated travel times using Manhattan's road network and GPS-based estimates from taxi data available to them. The team discovered that they could reduce the overall fleet size needed by 30 percent and still maintain optimal service.