Overcoming food delivery challenges with data science
Coupang Eats’ predictive modeling and optimization techniques for order assignment, pricing, ETA, and more
This post is also available in Korean.
Coupang Eats is the online food ordering and delivery platform that began operating in Korea in late 2019. Since its launch just over two years ago, the Eats business has quickly grown to become one of the top players in the Korean market despite being a latecomer.
In this post, we will elaborate on some of the key data science problems that we faced in online food delivery service along with our technical solutions.
Table of contents
· Challenges
· Order Assignment (OA) optimization
· Static and dynamic pricing
· Estimated Time of Arrival (ETA)
· Other data science challenges
· Summary
Challenges
Online food order and delivery is a complex online-to-offline (O2O) business that involves competition and collaboration of a three-sided marketplace composed of customers, merchants, and delivery partners. Customers are consumers with demand on food; merchants are the food suppliers; and delivery partners are responsible for order fulfillment from food pickup to delivery. The following figure shows a typical interaction process between the three parties.
As a platform, Coupang Eats provides a channel for customers, merchants, and delivery partners to complete food order and delivery transactions. On the delivery side, we work with Eats Delivery Partners (EDP) in a crowdsourcing model in which they can decline the order assignment. EDPs are not bound to our platform and are free to come and go.
In this post, we will discuss the major challenges our Eats business faced, specifically with food delivery and EDPs. Some of the main algorithmic problems we faced include:
- Order Assignment (OA): How to assign each order to the optimal EDP for quick and cost-efficient pickup and delivery.
- Pricing: How to determine the suitable delivery fee for each order.
- Estimated Time of Arrival (ETA): How to accurately estimate food preparation time, travel time, and total delivery time.
- Other: How to balance EDP supply and customer demand and how to determine delivery scope of merchants for maximum order conversion while maintaining delivery quality.
Order Assignment (OA) optimization
Efficiently assigning each order to the optimal EDP is critical for quick delivery and high-quality customer experience (CX). In this section, we will discuss why OA is a challenging data science task and some common approaches used to resolve OA challenges.
The biggest challenge of OA is that it is a real-time scenario. In a matter of seconds, numerous calculations and predictions must be made to create an optimal match between orders and EDPs. Our main objectives in OA optimization include decreasing delivery time, decreasing longtail order percentages, and increasing EDP acceptance rates to provide the best CX.
Approaches to OA
There are generally two approaches to OA: routing-based and matching-based.
The routing-based approach casts OA as a Vehicle Routing Problem (VRP), a classic problem in Operations Research (OR), where a discrete optimization problem is formulated to simultaneously determine the best order assignments to EDPs and the best set of routes for each EDP. The purpose of this routing-based approach is to maximize a certain objective function given different constraints, such as minimizing the total travel distances or minimizing the promised delivery time of all orders.
However, VRP is an NP hard problem without efficient solutions in general cases. This limits its applications to real-time scenarios like food delivery, where decisions must be made within seconds.
In contrast, the matching-based approach casts OA as a matching problem between EDPs and orders. Each EDP-order pair has a matching score, and the optimal assignment is obtained by maximizing the total matching scores. Compared to the routing-based approach that treats OA as a VRP, the matching-based algorithm is computationally more efficient and better suited to real-time scenarios, which is why we use the matching-based approach at Eats.
Matching-based OA
In this section, we will discuss the matching-based algorithm in more detail.
Local and global assignment
Depending on how the matching problem is solved, we can further divide the matching-based approach to local and global assignment algorithms.
The local assignment algorithm takes a greedy approach by considering orders one by one and assigning each order to the closest EDP. Despite its simplicity, the quality of the local assignment algorithm heavily depends on the specific order in which delivery tasks, or orders, are processed and can often result in a poor solution with non-optimal assignments.
Conversely, the global assignment algorithm views orders and EDPs as nodes on each side of a bipartite graph, where its edge weights are its matching scores. In global assignment, OA is treated as a bipartite graph matching problem, in which a globally optimal solution maximizing the total matching score can be obtained in polynomial time. For these reasons, we opt to use this score-based global assignment method at Coupang Eats.
Figure 2 below compares local and global assignment algorithms in a simplified example. In local assignment (left), the orders are processed chronologically. Order o1 is assigned to EDP d2 first because d2 is closer to o1 compared to d1. In this case, o2 must be assigned to d1, a poor assignment considering the long pickup distance from d1 to o2. Global assignment (right) can resolve this issue and obtain a globally optimal solution for both orders, where o1 is assigned to d1 and o2 is assigned to d2. Here the matching scores are calculated based on pickup distances and reversely proportional to them — the smaller the distance, the higher the matching score.
Matching scores
Matching scores are critical to improving the quality of assignment in a matching-based approach. The most intuitive choice is to directly utilize EDP pickup distance as the matching score. However, to balance the OA objectives of improving CX and EDP acceptance rate, factors such as EDP wait time, EDP preference, order overtime possibility, and new customer preferences are also considered in matching score calculations. Some of these factors and predictions are obtained using the output of machine learning models, such as preference models trained on historical data.
On top of the component scores, varying strategies can be designed for certain business goals by assigning different weights to the scores. The weights can be determined by methods such as offline simulations, online experiments, online optimization, and reinforcement learning.
Static and dynamic pricing
Determining the appropriate delivery price for each order is another important challenge in food delivery. In pricing, our main objectives are to decrease the cost per order (CPO) and increase delivery efficiency. The two main factors affecting pricing are delivery costs and the balance between EDP supply and customer demand.
Food delivery costs are difficult to quantify objectively. Except factors that can be explicitly measured, such as the distance between pickup and delivery points, the actual labor cost for the EDP is difficult to measure because labor costs can vary according to food wait time, number of and the weight of ordered food items, difficulties of delivering certain food categories, and customer destinations.
Moreover, supply and demand greatly impact pricing, as the number of orders fluctuate throughout the day. Prices need to be dynamically adjusted according to changing EDP supply and customer demand ratios. To accommodate for varying delivery scenarios in a cost-efficient and systematic way, Eats uses a hierarchical pricing system as shown in the figure below.
Pricing system
EDPs are paid per delivery order but also paid per person according to their individual missions. In this section, we will discuss how our pricing system motivates EDPs to stay on our platform through missions and dynamic price adjustments.
Static pricing
For pay per EDP, missions are designed to incentivize EDPs to go online and maintain an active status. On these missions, EDPs are paid when they complete a certain number of orders within a set timeframe. The mission goals are adjusted to suit different EDP grades and capacities. In addition to missions, EDPs are paid a base delivery fee for each order they complete.
The mission and base price calculations are conducted offline and remain relatively stable. They are static prices that depend on labor costs and EDP supply in the region, factors that do not drastically fluctuate over short periods of time.
Dynamic pricing
Unlike mission and base payments, region level and task level prices are sensitive to real-time factors and must be dynamically adjusted online. As you can imagine, major data science challenges lie in dynamic pricing.
Although regional dynamic pricing can be adjusted based on predefined operational rules, such rules do not capture real-time changes in supply and demand. In contrast, a dynamic pricing model can track the real-time supply and demand ratio to raise the regional base price during supply shortages and lower it under normal conditions.
However, we found that using actual real-time data lagged the system due to rapid changes in supply and demand during peak hours. To prevent lagging issues, we leverage predictive models to calculate supply and demand forecast values to improve the efficiency of price adjustments.
Regional dynamic pricing determines a coarse price level for orders in the region, but delivery prices in the same region may vary according to the type of task. Because it is objectively difficult to quantify the cost and difficulty for each task, we use EDP order response data to derive price-related signals. Under the same price level, EDPs immediately accept easy tasks but delay accepting or decline difficult tasks.
Based on the historical acceptance rates of different tasks, we built a task-level price sensitivity model to capture the changes of acceptance rates over different prices. Easy tasks tend to be price insensitive, and their acceptance rates may not vary much with price changes. Difficult tasks tend to be more price sensitive, and their acceptance rates can change dramatically with increasing prices. By reducing the prices for easy, price insensitive tasks and increasing the prices for difficult, price sensitive tasks, we not only achieve a fairer task-level pricing but also reduce the overall CPO while still maintaining delivery efficiency.
Estimated Time of Arrival (ETA)
ETA is also a classic problem in food delivery. There are two important ETA problems, namely food preparation time estimation and delivery time estimation.
Accurate food preparation time is important for both customers and EDPs. For customers, overestimation impacts customer conversion. For EDPs, underestimation may cause long wait times, while overestimation may cause cooked food to get cold. Accurate delivery time sets the right expectations for customers and large deviations to the true value may impact customer retention.
To derive accurate ETAs, we treat both preparation and delivery time estimations as regression problems, where predictive models are trained to predict output values given input features.
Food preparation ETA
For food preparation ETA, input features include the offline historical statistics of preparation times of different food categories and the near real-time preparation time data collected during the past hours of the day.
Because standard regression only makes a single estimation, we also leverage quantile regression for food preparation time estimation to compute estimated values at different confidence levels. These confidence levels are used to derive more conservative or aggressive estimates for purposeful overestimation or underestimation, according to different business scenarios. For example, if we aim to minimize the latency for food pickup, underestimation of food preparation time will make the EDP go to the store earlier for pick up. On the other hand, overestimation will shorten EDP wait time at the store and improve EDP experiences.
Delivery ETA
Unlike food preparation time estimation which simply calculates the elapsed time between the merchant accepting the order and the food being ready, delivery time estimation is a multi-hop prediction task from the time the customer places the order to the time that the order gets delivered, as shown in the following figure.
There are typically two approaches to delivery time estimation. The bottom-up approach takes a divide-and-conquer approach by decomposing it into a set of sub-tasks of estimation and aggregating the estimation results from sub-tasks to get the final estimate. Each sub-task is a regression problem and can be separately modeled as the following:
- Assignment time estimation: The time it takes for the merchant and an EDP to accept the order.
- Point-to-point time estimation: The time it takes for the EDP to arrive at the store for pickup and the time it takes for the EDP to travel to the customer location. Note that point-to-point time only accounts for the time that EDP spends on the road and does not include the navigation time inside the buildings of merchants or customer locations.
- Endpoint travel time estimation: The time spent navigating inside the campuses or buildings of stores and customer locations. Unlike taxis where customers are picked up and dropped off on the roads, food delivery requires door-to-door delivery. Travel times at different endpoints are non-trivial and need to be explicitly accounted for in delivery time estimations.
Though intuitive, the bottom-up approach depends heavily on the accuracy of each sub-task, and errors may accumulate from each sub-task to yield poor overall estimates.
To the contrary, the top-down approach views the whole process as a black box and takes a holistic approach. In this approach, a single regression model is trained to directly estimate the delivery time. At Coupang Eats, we utilize our growing database and the latest machine learning techniques to train a powerful deep neural network model that captures the complex relations in end-to-end delivery time estimation.
Other data science challenges
Besides the algorithmic challenges mentioned above, some other challenges in food include balancing supply and demand and delivery scope design.
Supply and demand adjustments
As previously mentioned, orders are not evenly distributed over the course of a day. Orders can dramatically increase during peak hours, holidays, or bad weather, leading to an EDP supply shortage. In such imbalanced EDP supply and customer demand situations, our objective is to quickly adjust and neutralize the supply and demand ratio.
Previously, we discussed region-level dynamic pricing as a method of balancing supply and demand. In addition to pricing, we can manipulate a variety of adjustments to suppress customer demand and stimulate EDP supply in urgent situations. For example, we can decrease the merchant’s delivery scope and withhold promotions. Refer to the figure below for more examples.
To identify trigger points for adjustments, we built a powerful prediction model that recognizes supply and demand imbalance points ahead of time, more quickly than models that use operational rules. Our prediction model can be flexibly adjusted according to parameters such as regions and time periods.
Using these predictions, we make various adjustments to derive the best balance between supply and demand. This is usually achieved with a multi-objective global optimization by maximizing the total orders while preserving delivery efficiency or vice versa.
Delivery scope design
Merchant delivery scope impacts both customer conversion and delivery quality. Expanding the scope may increase customer conversions, but it can also increase delivery time. A reasonable delivery scope must be set to achieve a balance between conversions and delivery efficiency.
A straightforward way to determine delivery scope is to draw a circle with a fixed radius around the merchant’s location. However, travel distances can greatly differ within the circle according to road and building conditions. Furthermore, a simple circle fails to consider complex geographical properties. For instance, a circle may split the same apartment complex so that one building is inside the delivery scope and one outside. This can cause confusion and inconsistent experiences for customers.
A more sophisticated and effective approach is to replace regular circles with irregular isochrones determined by actual travel distances and road networks, as shown in the figure below. In this approach, an optimal scope can be determined by considering the order volumes and delivery qualities of potential scopes.
Summary
Compared to other domains, data science problems in online food delivery are quite special, often involving a combination of predictive modeling and optimization techniques.
Problems such as OA, pricing, or supply and demand rebalancing are optimization problems, but the parameters of such optimization problems are provided by complex prediction models trained on historical data.
Moreover, all these problems are multi-objective optimization problems. We need to achieve a dynamic balance between different objectives (customer vs EDP experiences, efficiency vs cost, average vs long-tail) and customize to business requirements at different stages.
The complex delivery issues at Coupang Eats presents fresh and exciting challenges for data scientists. If you are an engineer with a passion for solving complex problems using cutting-edge optimization and prediction models, check out our job openings.
