MIT's Dispatching Algorithm Can Minimize a City's Taxi Fleet by 30 Percent
【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.
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.
Originally from New Jersey, Eric is an automotive and technology reporter specializing in the high-tech industry in Silicon Valley. Eric has over fifteen years of automotive experience and a B.A. in computer science. These skills, combined with technical writing and news reporting, allows him to fully understand and identify new and innovative technologies in the automotive industry and beyond. He has worked on self-driving cars and as a technical writer, helping people to understand and work with technology. Outside of work, Eric likes to travel to new places, play guitar, and explore the outdoors.
Electric Adventure Vehicle Maker Rivian Announces a $700 Million Investment Led by Amazon
California DMV Publishes Self-Driving Car Disengagement Report, Waymo is Still the Leader
Silicon Valley Robotics Startup Nuro Raises Nearly $1 Billion in Latest Funding Round
Amazon Enters the Self-Driving Car Space with Investment in Aurora
Ford is Testing a ‘Visual Language’ to Help Self-Driving Cars Communicate with Pedestrians
Toyota Establishes a New Company Named “KINTO” That Will Offer Car Subscriptions
Google to Develop Self-Driving Taxis with the Renault-Nissan-Mitsubishi Auto Alliance
Audi e-tron is the First EV Using the EEBUS Standard for Charging
- Harley Davidson, IBM & Panasonic Create Cloud-Based Riding Experience
- Driverless Startup Apex.AI Completes Series A Round, Raises $15.5 Million
- BMW i Ventures Announces Investment in Tekion, a Silicon Valley-based Cloud Platform Provider of Automotive Retail Services
- Here's What You Need to Know About the Rivian R1S All-electric SUV
- Volkswagen's Plans to Electrify America with a Network of EV Chargers
- Volkswagen & Ford Still at Odds Over Autonomous Driving Partnership
- Saudi Arabia’s Public Investment Fund Hedges its Stake in Tesla
- GM Hints at Flying Cars, Talks the Future of EVs
- Mercedes Benz & Bosch to Launch a Self-driving Taxi Service in San Jose
- Volkswagen Converting Assembly Plants in Order to Build Europe’s Largest EV Production Network