Interviewer: Ellie Mackay
I’m standing outside King’s Cross train station here in the heart of London. It’s a busy morning, and as I’m sure you can hear there is a lot of traffic about. I can see a fair few taxi cabs too, and no doubt many of the people who’ve ordered them have done so via an app on their phone. Now, waiting for a taxi to pick us up is a minor inconvenience. But how do the dispatch systems calculate how many vehicles are needed at any given time? And how do taxi company owners juggle the demand for rides with the cost of keeping countless cars and drivers on the road? Their daily challenge is to make sure there are enough vehicles in their fleet to serve all their customers without delay, but not have so many that they’re losing profits. And of course, an excess of vehicles also creates traffic and pollution problems. It’s a mathematical conundrum known as the Minimum Fleet Problem, and it’s something that Moe Vazifeh from the Senseable City Lab at MIT has been trying to solve. His team have developed a new solution to this urban traffic puzzle — a computer algorithm they’ve been testing in New York, which they say could make taxi networks much more efficient. So Moe, when you’re looking at a city like New York, for example, why is this Minimum Fleet Problem so difficult to solve?
Interviewee: Moe Vazifeh
So when you look at New York City, there are around 300,000 to 400,000 taxi trips a day, served by around 13,000 cabs on the road. Traditional optimization approaches are not designed to be able to handle such a huge number. You can only solve this problem for a few thousand trips considering the frameworks which have been designed in the literature so far. So, if you want to solve this problem in real world scenarios, you have to like rethink the problem and design it in a way that is scalable and accurate.
Interviewer: Ellie Mackay
So your solution is different because it’s designed to handle these huge numbers of trips, and you call it a network-based solution. What does that mean?
Interviewee: Moe Vazifeh
So, we have reformulated the problem in a way that the problem becomes a network science problem. So basically, we have a fleet of vehicles that are being shared by all these trips, but all the trips remain independent. And the way we construct this network, is each node is a trip, and the links between the nodes represent whether trips could be shared by the same vehicle. So if you consider a pair of nodes, and there is a link from node A to node B, it means that a vehicle can serve first the trip A, and then go and serve trip B.
Interviewer: Ellie Mackay
So the computer algorithm then finds the best pathway through that network?
Interviewee: Moe Vazifeh
Yeah, so it’s decisions that we make for each individual car is affected by the whole system. So the problem of finding the minimum fleet size, becomes finding an efficient set of paths, chains on this network that connect all these dots, all these nodes, and they cover all this network.
Interviewer: Ellie Mackay
So in your paper you discuss some of the complexities that you include: the ride duration, the trip frequencies, the locations, and the distances. How long does it take for the computer to run these simulations and how does it respond to the fact that you’ve got new requests coming through all the time?
Interviewee: Moe Vazifeh
So we have two scenarios, we have offline and online optimisations. So for the offline, we have the knowledge of trips one day in advance. So this could be used, for example, for a delivery service. But in the online case, which is more relevant to on-demand mobility services, you have to assign vehicles to rides where you only have trip information in the next minute or so. And we show that in this paper, on a very simple desktop computer you can solve this in a very short time, like in the order of half a second.
Interviewer: Ellie Mackay
And so to test this algorithm, you’ve applied it to a year’s worth of data from New York City, so this is 150,000,000 previous taxi trips, which is about 3-400,000 a day. And you’ve looked at both offline and online systems, so that’s trip you know in advance, as well as live bookings. What did the algorithm show?
Interviewee: Moe Vazifeh
In the offline model, we show that consistently throughout the year you are able to provide the same level of service, reducing the number of cabs by 40% compared to what we have on the road today. And in the online model, we still have 30% reduction in the number of cabs while maintaining the level of service, and the level of service means the percentage of people served within a certain delay remains the same as the original.
Interviewer: Ellie Mackay
So essentially according to your algorithm, New York City could function fully with several thousand fewer taxis on the road.
Interviewee: Moe Vazifeh
Yes, that’s correct.
Interviewer: Ellie Mackay
Okay, so these reductions of 30 and 40% are pretty big numbers. But you discuss in the paper some of the factors that may limit us from achieving this maximum efficiency. What about driver behaviour, what if someone decides to collect the closest person to them, or take their preferred route rather than what the algorithm tells them?
Interviewee: Moe Vazifeh
So we are limited by the behaviour that we are observing in this historical data, but this is still, I would say, would be applicable. One year is long enough to capture most of the cases, but there still may be actually fundamental problems. I’ll give you an example, so if you have a sport match, and after the match suddenly you have huge number of diverging requests, then you have to add more vehicles to the system to be able to serve these trips.
Interviewer: Ellie Mackay
And also, this system is assuming one central dispatcher for a single large fleet, so doesn’t that encourage a monopoly in the market?
Interviewee: Moe Vazifeh
Not necessarily. This could be an agreement between companies for efficiency. As we have shown in the paper, even if you have a few players, you still get most of the efficiency that you expect. So we have considered 2 and 3 in the paper, and it shows that you only have 6–7% reduction in efficiency.
Interviewer: Ellie Mackay
Okay, so you’re still looking at 20–25% fewer vehicles required than currently, even with several competitors all sharing that information.
Interviewee: Moe Vazifeh
That is correct.
Interviewer: Ellie Mackay
Okay, so that’s great for taxi companies and could help traffic problems in big cities, but thinking ahead, you also think this algorithm could be especially relevant for maintaining sustainable cities in the future.
Interviewee: Moe Vazifeh
Sure, so we have a self-driving revolution ahead of us, and I think this work becomes even more relevant in that scenario. You’re directly translating these algorithms suggested decisions into a fleet of autonomous vehicles, serving these trips while keeping the footprint in the city as low as possible.
Host: Benjamin Thompson
That was Moe Vazifeh from the Senseable City Lab at MIT, speaking to reporter Ellie Mackay. You can read the full paper over at nature.com/nature.
