Follow
Subscribe

MIT's Dispatching Algorithm Can Minimize a City's Taxi Fleet by 30 Percent

Home > News > Content

【Summary】MIT researchers have developed an algorithm that makes taxi fleets more efficient. The researchers say they’ve found an efficient dispatching algorithm that can cut a city’s fleet of taxis by 30 percent.

Eric Walz    May 25, 2018 11:14 AM PT
MIT's Dispatching Algorithm Can Minimize a City's Taxi Fleet by 30 Percent

Major cities like New York, Houston, and San Francisco are known for their traffic problems. According to the New York Taxi and Limousine Commission, there are over 13,000 cabs in the city, with an even greater number of Uber and Lyft vehicles operating in Manhattan. All of these vehicle create a daily traffic nightmare for those looking to get across town. Researchers at MIT are working on a solution.

MIT researchers have developed an algorithm that makes taxi fleets more efficient. The researchers 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 this week 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 taxi fleet logs about 500,000 trips each day.

The technology would seem to help New York's antiquated taxi business fend off private ride-hailing services, like Uber and Lyft that use much more sophisticated algorithms to match riders and drivers.

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.

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 handled by making each taxi trip set up the next trip.

The algorithm gives 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 difficult  as the number of spots increases. You could solve it for a small rural town, but it's not so easily for a large city like 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 the solution.

50% Fleet Reduction with Autonomous Cars

Imagine that all of Manhattan's 280,000 vehicles were autonomous robocars, driving themselves while under the control of the MIT's algorithm. "If we were to look at a fully autonomous city," Rotti says, "the reduction in vehicles would be closer to 50 percent."

The transportation revolution could also offer immense benefits, including opportunities to resolve existing inefficiencies in individual urban mobility, thereby reducing traffic, whose carbon footprint currently accounts for about 23% of global greenhouse gas emissions.

The researchers tested their methodology on a dataset of over 150 million taxi trips performed in New York in the year 2011. This dataset has been selected from a number of available datasets because it is publicly available and since the taxi statistics are published by the New York Taxi and Limousine Commission, it is possible to compare the methodology directly with current taxi operation.


Prev                  Next
Writer's other posts
Comments:
    Related Content