Taxi Dispatch Algorithms: Why Route Optimization Reigns

This article describes the result of a competition between software engineers and compares six different taxi dispatch algorithms. When I accepted the challenge, I wondered how well a full-fledged route optimization algorithm would work in a real-time dispatching environment. Pretty darn well, it turns out.

* * *

Recently, I encountered an irresistible coding challenge put out by Local Motion: it’s a realistic simulation of the taxi dispatch problem. People appear on the map and start demanding rides, spawning a chaotic rush-hour scenario. The challenge is to write an algorithm that will dispatch your fleet of vehicles in a way that can maximize your profits. In essence: more passengers = more money.

When I shared the link with my colleagues, they, being the hackers they are, couldn’t help but start working on a solution. They began comparing their algorithms with one another, and a little friendly competition was born.

Who could design an algorithm that would pick up the most number of passengers, make the most money, and claim bragging rights?

Dispatching in the real world

In today’s on-demand economy, the taxi dispatch problem is everywhere. It doesn’t matter if you transport people, deliver food from restaurants, or pick up and drop off courier packages; the logistics of managing an on-demand fleet is all the same.

(Side note: True “on-demand” companies promise same-day pickup and delivery. Some on-demand companies have the luxury to offer next-day or scheduled deliveries. However subtle the difference, the former can be solved with dispatching algorithms described in this article, whereas the latter requires route optimization algorithms. Here is an op-ed (The Case Against Everything on Demand) I wrote on why I think that companies that schedule pickups and deliveries in advance will be the true winners in this space.)

Traditional courier and taxi companies are so inefficient, you’re not going to believe it. They typically employ a roomful of human dispatchers, each committing about 5 to 10 drivers to memory, and communicate with them using ancient radio technology. Dispatchers are often former drivers who have spent a lifetime on the road, because in this world, knowledge of the streets is still a necessity. I was shocked to discover that many don’t even use digital maps.

“How do you keep track of everything? The roads, your drivers, and the changing schedules?” I asked them.

The “best” dispatchers would tap their heads and say: “It’s all in here, buddy.”

The status quo in this industry is abysmal.

The good news is that this is changing quickly with the rise of disruptive on-demand startups. For an on-demand startup to be truly scalable, it needs to rely heavily on technology and dispatching algorithms. In most cases, even simple heuristics will get the job done, but the real question is: what margins are you leaving on the table?

The Local Motion challenge

There are 7 buildings. Passengers have a pickup and dropoff location, as well as a “latest time of arrival” constraint. You have 5 cars in your control, each with a maximum of 4 seats. You will earn $50 for each passenger that you drop off on time. The objective is to maximize your profits in 1,000 turns. You will have “passed” the challenge if you reach a minimum of $10,000.

Passengers may request a ride at any time, and some may even cancel their ride and start walking. Quite a realistic simulation indeed!

The following are 6 high-level descriptions of taxi dispatch algorithms that pass the challenge:

(Side note: You may argue that these are but simple heuristics, rather than “real” algorithms (except for the route optimization approach). Nonetheless, I learned that most on-demand companies — even some of the largest ones — simply resort to very basic greedy heuristics. However inefficient this approach may be, it gets the job done. And as long as they are most concerned with VC funded hyper growth, getting the job done is all that matters in the short term. This is a whole other discussion on business and ethics that we’ll avoid for now.)

1. Pure greedy

Dispatch every idle car to pick up the closest passenger that is waiting for a ride.

This is probably the most straight-forward approach, nonetheless quite effective. I’d venture to say that this is probably the most common approach for taxi companies because of its simplicity and ease of execution.

2. Greedy car pool

This approach is very similar to the previous approach in that the closest available vehicle is dispatched. The only difference is that each vehicle will pick up multiple packages at the pickup location, and deliver them one-by-one, in order of proximity.

3. Along the way

This approach considers not only idle cars that are closest to the passenger, but also vehicles that already have passengers on board. Cars are dispatched to pick up new passengers that are along the way, as long as there are enough seats and the driver can still drop all their passengers off on time.

This may resemble a rudimentary approach to something like UberPool or Lyft Line, where drivers can pick up more passengers that are heading in roughly the same direction.

4. Easy wins

This method might sound familiar, because it’s what happens when old-school cab drivers deny you a ride if you request one that’s too far for their liking. It is more lucrative for a cabbie to make a bunch of quick trips, because of the minimum fixed fee they earn each time.

This algorithm will look for quick and easy wins, i.e. short trips in close proximity. While driving towards a pickup location, the car can be rerouted to a pick up new package if it is an easier win. It will also pick up multiple packages at the same location.

In order to maximize the chances of finding these short trips, 1 car is assigned to roam exclusively the dense area of buildings in the centre.

5. Chinese cab drivers

This algorithm reminds me of a time when my wife and I tried to take a cab from the Wenzhou train station. The usual frenzy of fighting for a cab wasn’t that bad, if it weren’t for the fact that once we finally got seated, the cab driver decided to wait and look for more passengers heading the same way.

Obviously, this isn’t the best strategy if you care about your customers.

After 20 minutes of waiting and arguing with the driver, we decided to ditch the cab and take another one that was ready to hit the road.

The essence of this approach is to defer departure and and pick up as many passengers as possible, while ensuring that passengers will not be dropped off late. Our chinese cab driver didn’t understand that last part.

6. Route optimization

Route optimization is about finding the shortest total driving time, given a fleet of vehicles and a host of orders with their constraints. This is also known as the Vehicle Routing Problem. In this particular case, we need to solve a same-day Pickup and Delivery problem with time-windows and car capacities. Each snapshot in time can be considered a routing problem that we solve for, the results of which become the updated driving instructions for the fleet.

To this end, we hooked up Routific’s same-day pickup and delivery API to the Local Motion challenge, and called the API every 5 turns. You can find the code here. As new information becomes available throughout the simulation, the entire fleet is re-optimized so they are always taking the most optimal routes.

And the winner is…

Each of the above algorithms are run 3 times on the simulation model. Here are the results:

Well, there you have it folks: Route Optimization is the clear winner! Not only that, looks like we’ve set a new world record [4]:

It performs on average 30% better when compared with other approaches. When sized up against the ‘Pure Greedy’ approach — the simplest and most popular approach — route optimization performs 41% better.

It considers all the information at hand and can come up with routes for drivers that include multiple pickups and dropoffs intertwined. More importantly, it allows the entire fleet to operate as one centralized system.

What’s surprising is that the simple Greedy car pool approach performs much better than the more sophisticated heuristics. But it’s also important to note that in reality, passengers can spawn from any location, not just at select buildings, which means that a this approach typically won’t have as many doubles or triples.

Meanwhile, route optimization will still work in the real world as it considers each passenger with its unique pickup and dropoff locations individually. In fact, since the routing problem is known to become exponentially more difficult with size, the more passengers, the more cars, the more complex the real-world situation is, the clearer it becomes that simple heuristics are not good enough.

On this simple simulation model, it performs on average about 30% better than the other algorithms. In the real world, this would be a lower bound.

We have known this to be the case with scheduled routing, where route optimization can find solutions that are 37% shorter. Thanks to Local Motion’s simulation model we now know that route optimization can bring significant efficiencies to on-demand taxi dispatch operations.