Research Background
The explosive growth of online meal delivery services has made them an essential part of daily life. However, the high rate of order cancellations due to unaccepted orders by crowdsourcing drivers is a significant challenge. This problem not only affects customer satisfaction but also impacts the reputation and financial health of meal delivery platforms.
The core issue addressed in this paper is the high number of order cancellations on the Meituan meal delivery platform. Specifically, about 165,000 orders are canceled daily because they are not accepted by drivers. These “No-Accept” (NA) canceled orders lead to a 55% negative rating of the platform, resulting in substantial financial losses and a decrease in customer trust. The primary reason for these cancellations is that the delivery price is not attractive enough to motivate drivers to accept the orders.
In the context of the supply chain and AI decision-making, effective bonus allocation can significantly improve the efficiency and reliability of the delivery service. Prior approaches, such as single-stage bonus allocation, have been limited in their effectiveness. These methods often allocate bonuses based on empirical rules, which fail to consider the dynamic nature of the order acceptance process. For example, a fixed bonus amount is provided for orders unaccepted within a certain time frame, without considering the overall budget constraints or the varying acceptance probabilities at different stages.
The shortcomings of prior approaches include:
- Lack of global planning: Single-stage methods do not account for the multi-stage nature of the order life cycle, leading to suboptimal bonus allocations.
- Inefficient use of funds: Fixed bonus amounts do not adapt to the changing conditions and may result in either over-spending or under-utilization of the budget.
- Slow decision-making: Previous methods often require significant computational resources, making real-time decisions challenging.
In the meal delivery industry, the ability to make quick and informed decisions is crucial. The high volume of orders and the need for rapid response times mean that any delay in decision-making can lead to a significant increase in cancellations. Additionally, the dynamic nature of the market, with fluctuating demand and supply, requires a more flexible and adaptive approach to bonus allocation. The MSBA framework aims to address these challenges by providing a more sophisticated and efficient method for bonus allocation.
Key Findings
Multi-Stage Bonus Allocation Framework
The proposed Multi-Stage Bonus Allocation (MSBA) framework aims to maximize the number of accepted orders within a limited bonus budget. The framework consists of three main components: a semi-black-box acceptance probability model, a Lagrangian dual-based dynamic programming (LDDP) algorithm, and an online allocation algorithm.
The semi-black-box acceptance probability model forecasts the relationship between the bonus allocated to an order and its acceptance probability. This model uses a logistic function to predict the acceptance probability, given by:
[ p_i,t(c_i,t) = frac{1}{1 + e^{-alpha_i,t c_i,t – beta_i,t}} ]
where ( alpha_i,t ) and ( beta_i,t ) are parameters learned from historical data. The model is trained using a combination of bonus batches (with ( c_i,t > 0 )) and normal batches (with ( c_i,t = 0 )), allowing for more accurate predictions.
The LDDP algorithm calculates the empirical Lagrangian multiplier for each allocation stage offline. This multiplier is used to infer the bonus allocation decisions online, ensuring that the total budget constraint is met. The online allocation algorithm then uses the results from the offline part to calculate a proper delivery bonus for each order in real-time, with a computational complexity of O(1).
Experimental results show that the MSBA framework can reduce the total order cancellations by 25% compared to single-stage bonus allocation. Additionally, the framework saves 30% of the compensation paid to restaurants for food waste. These findings highlight the effectiveness of the MSBA framework in improving the overall performance of the meal delivery platform.
To further validate the effectiveness of the MSBA framework, the authors conducted both offline experiments and online A/B tests. In the offline experiments, the framework was tested on a large dataset of historical orders, and the results showed a significant improvement in the number of accepted orders. The online A/B tests, conducted on the Meituan meal delivery platform, confirmed the practical benefits of the framework. The tests involved comparing the performance of the MSBA framework with a single-stage bonus allocation method, and the results showed a consistent reduction in the number of canceled orders.
Acceptance Probability Model
The acceptance probability model is a critical component of the MSBA framework. It predicts the likelihood of an order being accepted by a driver based on the bonus allocated and contextual features. The logistic function used in the model is:
[ p_i,t(c_i,t) = frac{1}{1 + e^{-alpha_i,t c_i,t – beta_i,t}} ]
where ( alpha_i,t ) and ( beta_i,t ) are learned from historical data. The model is trained using a combination of bonus batches (with ( c_i,t > 0 )) and normal batches (with ( c_i,t = 0 )). This approach ensures that the model can accurately predict the acceptance probability for both scenarios.
The experimental setup involved training the model on a large dataset of historical orders. The results showed that the model achieved a high accuracy in predicting acceptance probabilities, with a mean absolute error (MAE) of 0.08. This level of accuracy is crucial for making informed bonus allocation decisions in real-time.
Compared to related work, the acceptance probability model in the MSBA framework offers several advantages. Unlike previous models that learn ( alpha_i,t ) and ( beta_i,t ) separately, the MSBA framework learns these parameters simultaneously but with different hidden layers. This approach allows for more efficient and accurate predictions, especially when dealing with imbalanced datasets.
The training process involves splitting the historical data into two types of batches: bonus batches and normal batches. The bonus batches contain orders with a non-zero bonus, while the normal batches contain orders with no bonus. This approach ensures that the model can learn the relationship between the bonus and the acceptance probability effectively. The model’s architecture includes different hidden layers for learning ( alpha_i,t ) and ( beta_i,t ), which helps in capturing the complex interactions between the bonus and contextual features.
Online Allocation Algorithm
The online allocation algorithm is designed to make fast and efficient bonus allocation decisions in real-time. It uses the results from the offline LDDP algorithm to calculate the optimal bonus for each order. The algorithm operates with a computational complexity of O(1), ensuring that decisions can be made within milliseconds.
The experimental setup involved conducting online A/B tests on the Meituan meal delivery platform. The results showed that the online allocation algorithm significantly reduced the number of canceled orders. Compared to the single-stage bonus allocation method, the number of canceled orders was reduced by 25%. Additionally, the algorithm saved 30% of the compensation paid to restaurants for food waste.
Compared to related work, the online allocation algorithm in the MSBA framework offers several advantages. It is highly efficient, with a computational complexity of O(1), making it suitable for real-time applications. Additionally, the algorithm dynamically adjusts the bonus allocation strategy based on the current state of the system, ensuring that the total budget constraint is met.
The online allocation algorithm works by first calculating the Lagrangian multipliers offline using the LDDP algorithm. These multipliers are then used to infer the bonus allocation decisions in real-time. The algorithm takes into account the remaining budget and the current set of orders, ensuring that the bonus allocation is both efficient and effective. The real-time nature of the algorithm makes it particularly well-suited for the dynamic environment of meal delivery platforms, where orders are constantly being placed and canceled.
Limitations
Model Complexity and Training Data
One limitation of the MSBA framework is the complexity of the acceptance probability model. The model requires a large amount of historical data to train, which may not always be available. Additionally, the model’s accuracy depends on the quality and representativeness of the training data. If the training data is biased or incomplete, the model’s predictions may be inaccurate.
To mitigate this limitation, the framework could incorporate additional data sources and use more advanced techniques for data preprocessing and feature engineering. Additionally, regular updates to the model based on new data can help improve its accuracy over time. The authors suggest that future work could focus on developing more robust data collection and preprocessing methods to ensure that the model is trained on high-quality, representative data.
Another potential solution is to use transfer learning techniques to leverage data from other similar platforms or regions. This can help in situations where the available historical data is limited or biased. By transferring knowledge from one domain to another, the model can be trained more effectively and achieve better performance.
Dynamic Nature of the Problem
Another limitation is the dynamic nature of the problem. The total amount of available bonuses is limited to a predetermined monthly budget, but the orders placed within a month cannot be obtained beforehand. This makes it challenging to effectively use historical information to make current decisions and to dynamically adjust the strategy based on the randomly placed orders.
To address this, the framework could incorporate more sophisticated forecasting techniques to predict future order patterns. Additionally, periodic control strategies can be used to adapt the remaining budget and order set dynamically, ensuring that the cost meets the total budget constraint. The authors propose using periodic control strategies to adjust the bonus allocation based on the current state of the system. This can help in managing the budget more effectively and ensuring that the bonus allocation remains within the predefined limits.
Another approach is to use reinforcement learning techniques to continuously update the bonus allocation strategy based on the feedback from the system. This can help in adapting to the changing conditions and making more informed decisions in real-time. The reinforcement learning agent can learn from the outcomes of the bonus allocation decisions and adjust the strategy accordingly, leading to better performance over time.
Computational Resources
While the online allocation algorithm is designed to operate with a computational complexity of O(1), it still requires significant computational resources to handle the large volume of orders. In some cases, the algorithm may struggle to make decisions within the required time frame, especially during peak hours.
To mitigate this, the framework could be optimized further to reduce its computational requirements. This could involve using more efficient algorithms, parallel processing, or distributed computing. Additionally, the framework could be deployed on more powerful hardware to ensure that it can handle the computational load. The authors suggest that future work could focus on optimizing the algorithm to reduce its computational complexity and improve its performance during peak hours.
Another potential solution is to use edge computing to distribute the computational load across multiple devices. This can help in reducing the latency and improving the responsiveness of the system. By offloading some of the computations to edge devices, the central server can focus on more critical tasks, leading to better overall performance.
Practical Implications
Improved Customer Satisfaction
The MSBA framework can significantly improve customer satisfaction by reducing the number of canceled orders. With fewer cancellations, customers are more likely to have a positive experience with the meal delivery platform, leading to higher repurchase rates and better reviews. This, in turn, can enhance the platform’s reputation and attract more users.
For example, a 25% reduction in canceled orders can translate to a significant improvement in customer satisfaction. Customers who have a positive experience with the platform are more likely to leave positive reviews and recommend the service to others. This can lead to a virtuous cycle of increased customer loyalty and higher user engagement, ultimately benefiting the platform’s growth and profitability.
Cost Savings for Restaurants
By reducing the number of canceled orders, the MSBA framework can save restaurants a significant amount of money. The framework saves 30% of the compensation paid to restaurants for food waste, which can be a substantial cost savings. This can help improve the financial health of restaurants and strengthen their relationship with the meal delivery platform.
Restaurants can benefit from the reduced food waste and lower compensation costs. For instance, if a restaurant typically spends $10,000 per month on compensation for food waste, a 30% reduction would result in a savings of $3,000 per month. Over time, these savings can add up, helping the restaurant to invest in other areas of the business and improve its overall financial performance.
Enhanced Driver Motivation
The MSBA framework can also enhance driver motivation by providing more attractive bonuses. By optimizing the bonus allocation, the framework can ensure that drivers are motivated to accept more orders, leading to a more efficient and reliable delivery service. This can help improve the overall performance of the meal delivery platform and ensure that it can meet the growing demand for online meal delivery services.
Drivers are more likely to accept orders when the bonus is attractive, and the MSBA framework can help in achieving this. For example, if the average bonus for an order is $5, and the MSBA framework increases this to $7 for orders that are at risk of cancellation, drivers are more likely to accept these orders. This can lead to a more balanced distribution of orders and a more efficient delivery process, ultimately benefiting both the drivers and the platform.
Paper Reference
Title: A Framework for Multi-stage Bonus Allocation in Meal Delivery Platform
Authors: Zhuolin Wu, Li Wang, Fangsheng Huang, Linjun Zhou, Yu Song, Chengpeng Ye, Pengyu Nie, Hao Ren, Jinghua Hao, Renqing He, Zhizhao Sun
Venue: 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD ’22)
Link: https://arxiv.org/abs/2202.10695
Source: https://arxiv.org/abs/2202.10695
