How DoorDash Uses Machine Learning ML And Optimization Models To Solve Dispatch Problem

DoorDash is a logistic platform that delivers millions of orders every day with the help of its DeepRed system. In their recent blog, Data Scientist Alex Weinstein and Data Science Manager Jianzhe Luo discuss how they use ML and optimization to solve the dispatch problem powering their platform. 

With DeepRed, their aim revolves around deliver orders fast and on time to offer a great user experience (to both consumers and merchants) and efficiently proposing best offers to Dashers (delivery partners) to help them maximize their earning opportunities.

They explain the following factors they need to consider in finding the best Dasher:

• The geographical location of Dashers: To find a Dasher who is close to the store and minimize the total travel time. 
• Ensuring that Dasher arrives at the right time: The Dasher will have to wait for the order to be ready if the Dasher is dispatched too soon. And Food may go cold if they are dispatched too late, and customers may be dissatisfied that their order was not delivered as quickly as possible.
• Batching: Maximizing the use of Dashers by seeking out opportunities when a single Dasher can pick up many orders at the same store or a set of nearby stores.

Furthermore, various marketplace conditions influence the decision to select the best Dasher. This includes market supply and demand, weather conditions, and traffic. 

The team tackles this dispatch problem in two stages. In the first stage, they built a sophisticated dispatch service that employs multiple ML and optimization models to understand the state of the marketplace and make the best possible offers to Dashers to meet the needs of the marketplace. The second stage builds simulation and experimentation platforms that help in improving their current dispatch service. 

Building DeepRed

They used two sets of mathematical models to build DeepRed. The first set of models are ML models developed to predict how the order would evolve if offered to a specific Dasher. The goal of these models is to make predictions about each order, store, and Dasher.

The estimations are then fed into the optimization modeling layer that determines which orders should be offered to which Dashers at the end. This layer focuses on making system-wide decisions for the entire marketplace, whereas the ML layers are focused on creating individual estimations for each order.

Millions of data points from the marketplace are condensed into a set of dispatch decisions by the ML models and optimization layer, ensuring that each order is offered to the Dasher, who can efficiently deliver it from store to consumer as fast as possible.

When a new order is placed, the system first updates the current status of the marketplace and how this order interacts with Dashers and other orders, accounting for not only Dashers who are available but also who are waiting to pick up their orders. 

The ML Layer

This preliminary understanding enables them to construct prospective offers for a new order: a group of Dashers to whom this order may be offered, as well as additional orders that the same Dasher could pick up. These possible offers are then transmitted to the ML layer, which forecasts what will happen to them in the actual world. Their ML methods enable them to predict when the order will be available for pickup, estimate the time it will take a Dasher to travel to the store and then deliver to the requested location, and estimate the likelihood that each Dasher will accept the order if it is offered.

In addition to that, they also model different aspects of Dasher’s trip, such as the duration of the Dasher’s time to find parking, the time it takes them to manage the logistics of collecting the order, and the time it takes them to return to their vehicles. All these steps require their own model, some based on naive models, while some are created on their Sibyl ML platform. 

The Optimization Layer

The optimization layer’s mixed-integer program (MIP) scores and ranks the incoming order’s prospective offerings, making batching judgments and strategically delaying dispatches as needed. The scoring function recognizes tradeoffs between efficiency and quality while attempting to account for explained and unexplained variance in the ML estimates of order ready times, travel times, and Dasher acceptance rate, the scoring function recognizes tradeoffs between efficiency and quality. Following the scoring of each offer, MIP is solved using Gurobi, a software-based commercial MIP solver capable of solving this type of problem at scale quickly.

The optimization model also analyzes which orders are to be batched to increase efficiency in addition to scoring and ranking individual orders. The solver makes the best decisions to alter the scoring formula, take stock orders into account, and compare them with individual orders.

Finally, the next crucial step is to choose between Dasher available right now or delay the dispatch to select a more optimal Dasher that might be available soon. The optimization model makes the best tradeoff between dispatching right away or waiting. This marks the completion of the order’s through dispatch, and it is offered to the elected Dasher. 

Overcoming Challenges

A new order passes through ML and the optimization layer in its dispatch journey. The interaction between ML and optimization models poses critical challenges to the dispatch system. These challenges include:

1. Dealing with garbage in garbage out – The quality of optimization declines if the travel time predictions start to drift over time. That is why the team regularly retrain the ML models. In addition to this, they use rolling historical and real-time features to make sure the inputs to their models stay fresh.
2. Avoiding overfitting – ML models are prone to overfitting and often fall into the trap of local optimum. To prevent this, the engineers have implemented Bayesian optimization techniques to tune parameters robustly and adaptively.
3. Handling cascading variability – Each of the ML models contributes to the final model’s variance. DeepRed’s constructed scoring mechanism accounts for the extra variance from more complex routes by including a penalty term. The penalty scales with each complexity and warns DeepRed from offering high-variability offers.

It’s difficult to improve the dispatch models because dispatch decisions directly impact DoorDash’s business, and any product changes can have complicated interactions and downstream effects across DeepRed. Experimentation and simulation are two modeling tools the team uses to address this difficulty.

Before embarking on a significant implementation effort, they use offline simulation to analyze and forecast the system-wide consequences of product concepts. Furthermore, rigorous testing allows them to assess the overall impact of all modifications to the dispatch’s underlying ML and optimization models.

Source: https://doordash.engineering/2021/08/17/using-ml-and-optimization-to-solve-doordashs-dispatch-problem/