Fulfillment Time Estimation: How to Make Food Delivery Faster?

Foreword

Recently, a paper by Ali's local life smart logistics team - Order Fulfillment Cycle Time Estimation for On-Demand Food Delivery was accepted by KDD'2020 Applied Data Science Track as an Oral presentation (ACM Knowledge Discovery and Data Mining (SIGKDD), CCF A class conference, the top conference in the field of data mining, the acceptance rate of oral presentations in 2020 is 5.8%).

The problem of order fulfillment cycle time (OFCT: Order Fulfillment Cycle Time) is more complicated than the general time estimation problem, in which there are supply and demand relationships between restaurants and users, the unknown time of restaurant delivery, and the uncertainty of rider behavior issues such as sex. In this paper, we introduced the problem of forecasting delivery delivery time to the academic community for the first time in detail, and gave an effective solution, which was unanimously approved by the reviewers.

By gradually dismantling the entire delivery fulfillment process (contract fulfillment: the Ele.me platform guarantees that riders can deliver food deliveries to users on time), we analyzed how the delivery fulfillment time estimate compares with other common delivery time issues (such as taxi-hailing) Significant differences are explained and explained for the characteristics that affect the length of time for compliance. For users, it may only be to see how long it takes for the takeaway to be eaten, but behind this, we need to extract a wealth of influencing factors to ensure the accuracy of the performance time estimate. We input these influencing factors into the deep neural network to infer the relationship between them and the fulfillment time, and we further introduce hidden vectors of restaurants, user addresses and riders to enhance the predictive performance of the model. Finally, we propose a novel post-processing neural network operator to improve the convergence speed and accuracy of the model. The model we introduced has been actually deployed in Ele.me, serving tens of millions of users every day.

background introduction

The performance time estimation model estimates the time from when the user places an order to when the rider delivers the order to the user (that is, the estimated delivery time). The Ele.me platform generates tens of millions of orders every day. As a part of real-time delivery, time estimation not only affects the user experience but also involves the rider's performance. Therefore, its accuracy is very important to the platform, and it cannot be estimated. It is too long (affecting user experience), and it cannot be estimated too short (riders cannot complete the delivery on time). The figure below shows the various links involved in time estimation.

The main links include:

•User: From placing an order to when the order is delivered to the user. For every user, it is definitely hoped that they can get the ordered meals on time.

•Restaurant: From accepting orders to preparing meals in restaurants. The restaurant needs to complete the meal preparation as soon as possible, so as not to affect the rider's food pickup and delivery. If the rider has to wait for a long time to pick up the meal when he arrives at the restaurant, the rider is prone to anxiety, and some users will also be hungry. Riders are urged on the App.

•Rider: The rider receives the order and completes the delivery. This includes the rider arriving at the restaurant and picking up the order from the restaurant. At the same time, the rider may pick up multiple meals from the restaurant, so the rider needs to wait for all orders before leaving and delivering.

•Platform: The Ele.me platform needs to coordinate users, restaurants, riders and take delivery efficiency into consideration. This includes order assignment and route planning. Order assignment refers to assigning orders to suitable riders nearby, while route planning refers to recommending reasonable pick-up and delivery routes to riders. This route needs to consider both the delivery distance of riders and the risk of order overtime.

The picture below is the information that you can see when you order takeaway on Ele.me, and the delivery time is calculated by our fulfillment time estimation model.

The difference between delivery fulfillment time and ETA
Estimated Time of Arrival (ETA) is "estimated time of arrival". Generally, it is estimated the time from the departure point to the destination. The estimated time of arrival in the taxi scene is a typical ETA problem.

The takeaway performance time estimation model proposed in this paper estimates the time it takes from when the user places an order to when the rider delivers the food to the user. After the user orders takeaway on Ele.me, the order begins to circulate on the platform. As shown below.

Compared with the estimated delivery time, the estimated delivery time is more special, which is mainly reflected in the following two aspects:

1 More influencing factors need to be considered

The general estimated delivery time problem only needs to consider weather, traffic conditions, space-time information, and route information, while the problem of food delivery delivery time estimation needs to consider not only such information, but also the geographical location of the restaurant and the preparation time of the restaurant order. As well as information such as dispatching system orders.

2 Unable to obtain key information

Ele.me has already estimated the expected delivery time for the user when the user placed the order successfully, but the order has not been accepted by the rider at this time, and the rider needs to be assigned by the system to start picking up and delivering the meal, so we cannot obtain the rider's information in advance and its actual delivery route.

The difference between the above two aspects brings great challenges to the accuracy of the prediction of delivery delivery time.

What features are generally required for delivery time prediction

In order to model delivery delivery time, it is generally necessary to make full use of data related to order information, including:

• Spatial features: including a large number of id features, such as the user's area id, restaurant id, city id, and grid id.
• Time characteristics: including the hour and moment, whether the day is a working day, etc., as shown in the figure (a) below.
•Characteristics describing the size of the order: including the quantity of dishes corresponding to the order and the price of the order, etc.
You should be wondering how the order price will affect the delivery time? When the amount of the user's order is high, the weight or volume of the meal is usually relatively large. For example, the user ordered a cake or ordered many cups of milk tea collectively. This kind of order with a high total amount is difficult for the rider to deliver. Therefore, It takes a long time to fulfill the contract. Figure (b) below shows this correlation. It can be seen that the order price can to a certain extent describe the implicit information of whether the order is difficult to deliver.

The impact of supply and demand on performance time

From the perspective of the platform, the amount of orders placed by users and orders received by restaurants are changing drastically at different times. This change in the dimension of supply and demand will have a great impact on the actual delivery time.

Before introducing the work of supply and demand feature construction, let me introduce the concept of "wave" in food delivery: for a group of orders on riders, group a given set of order pick-up order to ensure that all related orders in each group The pick-up and delivery behaviors of the order are all in this group, and this group is the current delivery wave of the rider. For changes in supply and demand, we constructed features such as time-based supply-demand ratios and completion rates. When the supply-demand ratio is higher, the average length of the wave will be longer, and the fulfillment time will be longer at this time.

On the other hand, when the completion rate is higher, it can be inferred that the rider completes the delivery of more orders, and at this time the rider can continue to undertake the next order assigned by the system.

In addition, we describe the busyness of the restaurant by the number of orders currently waiting to be picked up by the restaurant (the number of orders waiting for the rider to pick up after the restaurant receives the order). When the number of orders received by the restaurant increases and the capacity is limited, it will lead to a backlog of orders. If the rider has already arrived at the restaurant, it will take a long time to get the meal. Correspondingly, when the restaurant becomes busy, the fulfillment time estimated by the model will become longer.

restaurant dining hours
The delivery time of the order is an important factor in the prediction model of the delivery delivery time. This feature is obtained by aggregating the historical delivery times of restaurants. However, the existing difficult problems have brought great challenges to the accuracy of the meal time calculation, mainly including:

•The restaurant lacks the manpower to click on the delivery button one by one after the meal preparation is completed, resulting in our platform not being able to fully collect the real value of the restaurant's delivery, so we currently mainly rely on the rider's click delivery data collected by the system to mark the restaurant's real delivery meal time.

• The Ele.me platform currently mainly calculates the orders generated by restaurants on the Ele.me App, and lacks data on orders generated by restaurants through other channels or dine-in orders, so it is difficult to obtain the actual supply and demand of restaurants.

• The real meal delivery time of the restaurant is relatively random. For example, restaurants may prepare meals in advance for certain meals, and these pre-prepared meals can be served immediately. For the meals that the restaurant needs to make fresh when the user places an order, the rider may have to wait for a while to pick up the meal after arriving at the restaurant. The actual delivery time of this part of the fresh order will be longer.

• The order of orders does not necessarily indicate the order in which restaurants serve meals. Due to the limited number of stoves in the restaurant, the corresponding stoves will only handle fixed dishes. Therefore, if the same dishes appear in a batch of orders, the back kitchen will choose to cook them together. In this case, the meal delivery time of some orders will be obviously skewed. short.

In actual use, we calculate the merchant's real meal delivery time based on the time when the merchant receives the order to the time when the rider actually clicks to pick up the meal, and there are some noise data:

•Click to arrive at the restaurant immediately after the rider receives the order
• Immediately after the rider receives the order, click the pick-up button

In addition, for some training samples, we believe that the restaurant has already prepared the meal when the rider picks up the meal, for example, the rider picks up the meal late or the rider clicks to pick up multiple meals at the same time. For these data, we have eliminated a certain proportion when calculating the characteristics of the dining time of the restaurant.

How to make reasonable use of rider information

From the perspective of the platform, Ele.me divides each city into different areas with "grid" as the smallest unit. The riders in each Hummingbird delivery site will serve several fixed grids around the site. The riders Familiarity with the commercial districts or communities in the grid radiated by the site determines its delivery efficiency. As you can see from the picture below, because the rider is familiar with the location of the restaurant and the community where the user is located, there is no detour during the process of picking up or delivering the meal.

When the user successfully places an order, the Ele.me App will immediately display the estimated delivery time for the user. At this time, it is unknown which rider the order will be assigned to deliver. In order to make full use of the influencing factors related to the rider, we characterize each rider who may receive an order according to the rider’s distance from the rider, how many orders the rider currently receives, and then encode the sequence of riders who may receive the order. Into the delivery time prediction model, and then use the attention mechanism to extract rider sequence information, so as to enhance the prediction ability of the model.

Shipping Segment ETA for Similar Orders in Multiple Dimensions
The ETA of the delivery section refers to the estimated time it takes for the rider to get off the car near the destination (the location of the user) and deliver the food to the user, which is the final link of the rider's delivery.

In order to estimate the ETA of the delivery section, we can theoretically directly use the regression model to learn, but the commonly used regression model usually converts the input into a series of features, and finds the relationship between these influencing factors and the output target through supervised learning, in order to It is convenient to learn and improve the generalization ability of the model. These relationships are usually parameterized as a smooth function based on the neural network and the ensemble tree model. However, the disadvantage of this smooth assumption is that it cannot handle long-tail irregular cases well, which may affect users. experience. For example, when riders need to take high-rise elevators to deliver meals, they may have to wait for a long time during peak hours, and it is difficult for the system to achieve this kind of real-time prediction. As can be seen from the picture below, the rider spent 7.6 minutes in the building when delivering the meal.

In order to partially alleviate this problem, we borrowed the idea of the recent memory-based language model [1], and used historical orders as the corpus for forecasting delivery time, and represented each historical order by constructing multi-dimensional features. When a new order is generated At this time, we search for several historical orders similar to the new order based on K-nearest neighbors, and then make a weighted average of the real delivery time of these similar orders, which is used as the estimated delivery time of the new order. Finally, we will use the estimated delivery time based on the K-nearest neighbor search as a feature input into the delivery delivery time estimation model.

How to deal with long tail data
Time estimation is essentially a regression problem. In the process of training the model, we found that the model converged slowly and the performance of cross-validation deviated from expectations. By analyzing the reasons, we found that the data distribution of the model fitting and the distribution of the actual performance time have deviated , the real fulfillment time is actually a distribution with a long tail to the right, which means that a small number of orders have a long real delivery time and the model has not learned it. To solve this problem, we propose a novel post-processing neural network in this paper. The operator is used to scale and transform the fitting results of the delivery delivery time prediction model to improve the convergence speed and accuracy of the model. The post-processing operator can be described as:

After offline training and verification, the post-processing operator can effectively improve the convergence speed and accuracy of the delivery delivery time prediction model.

Recently, we have explored a new post-processing operator: adaptive Box-Cox inverse transform. Compared with the post-processing operator proposed in this paper, the adaptive Box-Cox inverse transform operator is more able to fit long-tail data The distribution further improves the effect of the model. At present, this operator has been applied to online inference.

Experimental effect

The takeaway performance time estimation model we proposed uses "coding and prediction" as the main structure of the model, and the specific structure is shown in the figure below.

Among them, the Nearest Courier Index module implements the rider information encoding introduced earlier. This module allows the model to make full use of the rider information that may receive orders; Postprocessing is the post-processing operator. This operator allows the model to converge faster and also Improve the accuracy of the model.

Before we proposed the delivery time prediction model, the online time prediction model had been running stably for a period of time, so we conducted an AB experiment with the existing online model as the baseline. The experimental data in the figure below shows that compared with the original model, the MAE of the takeaway fulfillment time prediction model is relatively reduced by 9.8%, the user complaint rate is relatively reduced by 19.3%, and the prediction error and user complaint rate are significantly improved, which has a significant impact on user experience. positive effect.

Summary and Outlook

In this article, we introduce Ele.me's takeaway fulfillment time prediction model that is actually running online and serving users, and its effectiveness has been proved through offline evaluation and online testing.

In the future, we will mainly focus on the following two aspects to continue research:

• Meal delivery time is very important as one of the influencing factors of the takeaway fulfillment time prediction model, but the processing of meal delivery time is relatively simple at present, so there is considerable room for improvement.

• In addition, we will develop a general model framework for multi-task learning for meal delivery time and fulfillment time.