New York City, a place known for yellow taxis and traffic congestion, could soon feature a lot less of both with a shift toward ride-sharing services, a new study has found. Scientists at MIT have devised a new algorithm that suggests almost all of the city's 14,000 or so taxis could be replaced by just 3,000 ride-sharing vehicles, all without significantly impacting travel time.
Led by Professor Daniela Rus from MIT's Computer Science and Artificial Intelligence Laboratory (CSAIL), the team developed an algorithm that works in real-time to to redirect cars according the incoming requests.
Based on data from three million taxi rides, the algorithm begins by creating a graph of all ride requests and all vehicles. A second graph is then created of all the possible trip combinations and a method the team calls "integer linear programming" is used to determine the most efficient ride assignments. As the cars are assigned rides, the algorithm then sends remaining idle cars to high-demand areas, which apparently speeds up overall service by 20 percent.
"A key challenge was to develop a real-time solution that considers the thousands of vehicles and requests at once," she says. "We can do this in our method because that first step enables us to understand and abstract the road network at a fine level of detail."
While carpooling is not a new concept, and has been modernized by Uber and Lyft through the use of smartphone data in recent years, the team believes its new system is a big step forward. Where existing systems might require one user to be waiting en route for another for the service to work, or for all ride requests to be lodged before a route can be created, the new system, which Rus describes as an "anytime optimal algorithm," is purported to have more flexibility.
"To our knowledge, this is the first time that scientists have been able to experimentally quantify the trade-off between fleet size, capacity, waiting time, travel delay, and operational costs for a range of vehicles, from taxis to vans and shuttles," says Rus. "What's more, the system is particularly suited to autonomous cars, since it can continuously reroute vehicles based on real-time requests."
The researchers say the algorithm could see 3,000 four-passenger cars serve 98 percent of taxi demand in New York City, with an average wait time of 2.7 minutes. And it can also take into account which vehicle size is the most appropriate for the route in question – the team found that 95 percent of the city's taxi demand could be handled by 2,000 10-person vans.
"Instead of transporting people one at a time, drivers could transport two to four people at once, results in fewer trips, in less time, to make the same amount of money," says Rus. "A system like this could allow drivers to work shorter shifts, while also creating less traffic, cleaner air and shorter, less stressful commutes."
The research will be published this week in the journal Proceedings of the National Academy of the Sciences.
Source: MIT
