WASHINGTON, May 23 (Xinhua) -- American researchers have suggested a computationally efficient algorithm to decide how many taxis a city might actually need in an era of shared mobility services.
Using the new algorithm, they found the fleet size of cab-hailing service in New York could be cut down by about 30 percent in an optimal scenario, according to a study published on Wednesday in the journal Nature.
In order to cope with the hundreds of thousands of trips that are routinely made within large cities, a solution that can effectively match individuals with on-demand vehicles is badly needed.
However, the researchers have yet to solve the problem of how best to size and operate a fleet of vehicles, given a particular level of demand for personal mobility.
Researchers previously attempted to solve this question 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.
However, it has so far proven extremely difficult to find an optimal solution to the traveling salesman problem, even using today's powerful computers.
"If we were to consider replacing the current taxi system in New York with an optimized fleet of vehicles, we would have to find the best way of serving the around 500,000 trips made in a day, which are currently served by about 13,500 taxis," said Paolo Santi, a research scientist at the Senseable City Lab of Massachusetts Institute of Technology (MIT).
In this study, the researchers used a network-based model they dubbed the "vehicle sharing network" to approach the problem.
The algorithm represented the shareability of the taxi fleet as a graph, a mathematical abstraction consisting of nodes and edges or 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, according to the study.
Using this graph, the algorithm was able to find the best solution for fleet sharing.
The team tested the solution on a data set of 150 million taxi trips taken in New York over the course of one year.
They computed travel times using the actual Manhattan road network and GPS-based estimations derived from the taxi trip data set.
They found that real-time implementation of the method with near-optimal service levels reduced the fleet size needed by 30 percent.
The solution does not assume any individuals must share a journey. Instead, it simply involves the reorganization of the taxi dispatching operation, which could be carried out with a simple smartphone app.
The solution could become even more relevant in the years ahead, as fleets of networked, self-driving cars become commonplace, said Carlo Ratti, director of MIT's Senseable City Lab.
