IIn New York, the taxi and limousine commission carefully watches over each of the approximately 13,000 yellow cabs in the city’s canyons today. How meticulous is shown by the data that the Commission collects and publishes every year. Since 2009 there has been information on each of the approximately 150 million taxi journeys through New York each year about the respective starting and destination points, travel times and the number of passengers – a unique treasure trove of data. But with this collecting frenzy, the taxi commission could ultimately ensure that a large part of the yellow cabs disappear from the cityscape of New York one day. Because this data also reveals a lot about where the taxi service is not running optimally.
A number of researchers have now made it their task to track down these deficiencies. One of them was a group of mathematicians and computer scientists from America and Italy who published an article in Nature in May. They present an algorithm that optimally assigns taxis and passengers. As it turns out, all trips in Manhattan could be served with 4,627 taxis – 40 percent less than the average today on the streets of New York at any time.
In their search for the minimum fleet, the researchers assumed two conditions: passengers shouldn’t have to wait any longer than before, and drivers shouldn’t need more than 15 minutes from one passenger to the next. As is usual for mathematicians, they first transformed the problem into a simpler, but abstract form: a graph.
Thousands of taxis that you could do without
In mathematics, a graph consists of a number of nodes, some of which are connected to one another. The researchers’ algorithm produced a graph for each day in New York. The nodes represent individual taxi rides. The computer then combined two journeys, if it was mathematically possible for a taxi to do one journey first and then the second. A huge network was created in which all the journeys that a taxi could take over were connected. All the researchers had to do now was find the paths through the network that would take the fewest taxis overall.
The result of this calculation is impressive, but the method has a weakness: It only works if it is clear in advance when the passengers want to go where. From the historical data from New York, the researchers were able to calculate this without any problems. In practice, you don’t have this information because people sometimes order taxis just before driving or stop on the street. Then why did the scientists develop the system in the first place? “We wanted to know how far we are from the optimum today,” says Mohammad Vazifeh, one of the computer scientists involved. This discrepancy between the optimum and the current state is evident in New York in the form of 3,121 Yellow Cabs, which one could theoretically do without.
– .
