1. Research Background: The Order Cancellation Crisis in On-Demand Delivery
With the explosive growth of e-commerce, online meal delivery has become an essential service in daily life. Meituan, China’s largest meal delivery platform, processes 30 million orders daily. The platform aims to provide excellent and stable services for restaurants and customers, yet faces a severe challenge: approximately 165,000 orders are canceled each day due to no drivers accepting them. These “NA-canceled orders” (No-Accept canceled orders) account for over 55% of Meituan’s daily negative reviews.
The losses from order cancellations are comprehensive: customers experience disappointment leading to reduced repurchase rates; drivers lose income; restaurants suffer food waste costs; and the platform pays hundreds of millions of RMB annually in compensation to restaurants for NA-canceled orders. More critically, over 30,000 negative reviews daily, with 55% stemming from unaccepted orders, directly damage the platform’s brand reputation and long-term competitiveness.
Historical data analysis reveals two main causes for NA-canceled orders: first, delivery prices are unattractive to drivers despite sufficient driver supply; second, driver shortage during extreme weather. This research focuses on the first problem—how to incentivize drivers to accept more orders through bonus allocation. Meituan’s current approach uses empirical rules: 3 RMB for orders unaccepted within 10 minutes, 6 RMB for 20 minutes, etc. While simple, this method has obvious flaws: one-size-fits-all for all orders, lack of global optimization, and inability to maximize subsidy fund efficiency.
2. Problem Definition: Formal Modeling of Multi-Stage Bonus Allocation
An order’s lifecycle can be divided into multiple decision stages. Taking Meituan as an example, from order generation to final delivery or cancellation spans up to 50 minutes, divided into time windows (e.g., every 5 minutes). At each stage, an order can be in one of three states: accepted by a driver, canceled by the customer, or transitioning to the next stage. If no driver accepts within 50 minutes, the platform forcibly cancels the order.
The core problem is: given a fixed monthly bonus budget, how to allocate appropriate bonus amounts for each order at each stage to maximize the number of accepted orders? This is a typical multi-stage budget allocation problem with the following mathematical characteristics:
Objective Function: Maximize expected number of accepted orders
$$max sum_{i=1}^{N} sum_{t=1}^{T} p_i(b_{i,t}) cdot (1-q_{i,t}) cdot prod_{k=1}^{t-1}(1-p_i(b_{i,k})-q_{i,k})$$
where $N$ is total orders, $T$ is stages, $p_i(b_{i,t})$ is acceptance probability for order $i$ at stage $t$ with bonus $b_{i,t}$, and $q_{i,t}$ is cancellation probability.
Constraint: Total bonus budget cannot exceed limit
$$sum_{i=1}^{N} sum_{t=1}^{T} b_{i,t} cdot I(text{order }itext{ accepted at stage }t) leq B$$
where $B$ is monthly budget and $I(cdot)$ is indicator function.
This problem faces three challenges: first, the relationship between acceptance probability and bonus is unknown and must be learned from historical data; second, orders arrive in real-time, so the full month’s orders cannot be known in advance; third, bonus decisions must be made in milliseconds, requiring extremely high algorithm efficiency.
3. Methodology: Four Core Components of the MSBA Framework
The research team proposed the Multi-Stage Bonus Allocation (MSBA) framework, comprising four core components: acceptance and cancellation prediction models, Lagrangian Dual-based Dynamic Programming (LDDP) algorithm, online allocation algorithm, and periodic control strategy.
1. Semi-Black-Box Acceptance Probability Model: This model predicts the relationship between bonus amount and acceptance probability. The team employs semi-black-box modeling, combining machine learning’s data-driven advantages with economic theory’s interpretability. Specifically, the model assumes acceptance probability increases monotonically with bonus but with diminishing marginal returns, consistent with the economic principle of diminishing marginal utility. Through historical data fitting, the model accurately predicts acceptance probabilities at different bonus levels.
2. XGBoost Cancellation Probability Prediction: Cancellation probability at each stage is predicted by an XGBoost model. Features include: order wait time, restaurant preparation speed history, time of day, weather conditions, customer historical cancellation rate, etc. This model achieves 0.85 AUC in offline experiments, accurately identifying high cancellation risk orders.
3. Lagrangian Dual Dynamic Programming (LDDP): This is the MSBA framework’s core algorithm. The team transforms the original problem into a Lagrangian dual problem, using dynamic programming to offline calculate optimal Lagrangian multipliers for each stage. These multipliers essentially represent the “shadow price” of budget, reflecting the expected order acceptance increase per additional yuan of budget. During online decision-making, the algorithm simply looks up the corresponding multiplier based on current order features and stage, then quickly calculates the optimal bonus.
4. Periodic Control Strategy: To handle order arrival randomness, the team designed a periodic control strategy. At each month’s start, Lagrangian multipliers are adjusted based on remaining budget and expected order volume, ensuring uniform budget usage throughout the month, avoiding budget exhaustion early with none left for month-end.
Compared to Zhao et al.’s (2021) single-stage marketing budget allocation research, this study’s innovation lies in handling multi-stage decision complexity. Order state transitions at each stage introduce temporal dependencies, making traditional single-stage methods inapplicable.
4. Experimental Validation: Dual Proof Through Offline and Online A/B Testing
Offline Experiment Design: The team used real order data from Meituan’s March 2021 operations, containing approximately 900 million orders. Data was split into training set (first 3 weeks) and test set (last week). Baseline methods include: (1) Meituan’s current empirical rule method; (2) equal allocation (fixed amount per order per stage); (3) greedy algorithm (independent optimization per stage).
Main Results: MSBA significantly outperforms baselines across multiple metrics. With the same budget, MSBA accepts 18.7% more orders than the empirical rule method and 31.2% more than equal allocation. To achieve the same acceptance count, MSBA saves 34.5% of budget. Further analysis reveals MSBA’s advantage primarily lies in long-tail orders—those likely to be canceled under current rules due to no acceptance.
Ablation Study: The team conducted ablation analysis on each component. Removing LDDP reduced performance by 12.3%; removing periodic control caused uneven budget usage with month-end shortages, reducing performance by 8.7%; replacing the semi-black-box model with a simplified linear probability model reduced performance by 6.5%. These results validate each component’s necessity.
Online A/B Testing: In April 2021, Meituan conducted a two-week A/B test across 5 cities. The experimental group used MSBA, while the control group used current empirical rules. Results showed: experimental group NA-canceled orders decreased by 25.3%, restaurant compensation costs reduced by 31.7%, and customer satisfaction increased by 4.2 percentage points. Based on these significant results, MSBA was fully deployed across Meituan’s platform in June 2021.
5. Critique and Limitations: Rational Academic Perspective
Despite MSBA’s significant achievements, as rigorous academic research, we must rationally acknowledge its limitations.
1. Research Assumption Limitations: This study focuses on scenarios where “drivers are sufficient but prices lack attractiveness,” explicitly excluding driver shortage situations like extreme weather. In reality, these two problems often intertwine. When drivers are severely短缺, simply increasing bonuses may not solve the problem but instead raise platform costs. Additionally, the model assumes drivers are rational economic agents maximizing their 收益 based on bonuses, but actual decisions may be influenced by non-economic factors like route familiarity and personal preferences.
2. Methodological Boundary Conditions: LDDP’s O(1) computational complexity meets real-time requirements but relies on offline pre-computation. When business scenarios change significantly (e.g., new city expansion, order pattern shifts), models need retraining, creating adaptation lag. Furthermore, the semi-black-box model assumes acceptance probability increases monotonically with bonus, but at very high bonus levels, saturation or even decrease may occur (drivers suspecting problematic orders)—this non-linearity is not modeled.
3. Experimental Design Shortcomings: Offline experiments use historical data with selection bias—only actual allocated bonuses and outcomes are observed, not “counterfactual” scenarios (what if different bonuses were allocated). While the team employed inverse propensity score weighting to mitigate this, bias cannot be fully eliminated. Online A/B testing occurred in only 5 cities with limited sample representativeness, and the two-week test period leaves long-term effects unknown (e.g., behavioral changes after drivers form bonus expectations).
4. External Validity Concerns: This study uses data from China’s largest food delivery platform; whether conclusions generalize to other scenarios is uncertain. For instance, Western delivery platforms (UberEats, DoorDash) have mostly part-time drivers with potentially different decision patterns; fresh food delivery and express logistics have different timeliness requirements and bonus sensitivities. Additionally, the study doesn’t consider competitor platform effects—if competitors simultaneously increase subsidies, this platform’s relative attractiveness may decrease.
6. Practical Implications: Implementation Guide for Supply Chain Practitioners
For supply chain and logistics professionals seeking to adopt the MSBA framework, here is a concrete implementation roadmap.
1. Technical Implementation Path:
- Data Preparation: Requires at least 3 months of historical order data with fields: order ID, creation time, restaurant location, customer location, bonus amounts at each stage, acceptance status, acceptance time, cancellation status, cancellation reason, etc. Recommended minimum 1 million orders for statistical significance in model training.
- Technology Stack: Python 3.8+ (data processing), XGBoost 1.5+ (cancellation probability prediction), PyTorch 1.9+ (acceptance probability model, optional), Redis (online lookup caching). Server specifications: 16-core CPU, 64GB RAM, supporting 100,000+ bonus decision requests per second.
- Implementation Steps: Step 1: Clean historical data, removing anomalies (test orders, internal orders); Step 2: Train acceptance probability model, validate monotonicity assumption; Step 3: Train XGBoost cancellation model, target AUC ≥0.8; Step 4: Run LDDP algorithm to generate Lagrangian multiplier tables; Step 5: Deploy online service, integrate into order system; Step 6: Set up A/B testing, validate before full deployment.
2. Implementation Cost and ROI Estimation:
- Development Cost: Requires 1 algorithm engineer (3 months), 1 backend engineer (2 months), 1 data engineer (1 month). At tier-1 city salaries, labor costs approximately 800,000-1,200,000 RMB.
- Operational Cost: Server costs about 20,000-30,000 RMB/month, monthly model retraining requires additional 10,000 RMB in compute resources.
- Expected Returns: For a delivery platform with 10 million RMB monthly order cancellation losses (compensation + reputation), MSBA can reduce cancellations by 25%, i.e., 2.5 million RMB monthly benefit. Minus increased bonus costs (approximately 1 million RMB), net benefit is about 1.5 million RMB/month. Investment payback period: 6-8 months.
3. Applicable Scenarios and Enterprise Types:
- High-Applicability Scenarios: On-demand delivery (food, groceries, pharmaceuticals), ride-hailing dispatch, sharing economy platforms (e.g., shared power banks), dynamic pricing retail (e.g., near-expiry product discounts).
- Enterprise Scale Recommendation: Medium-to-large enterprises with 100,000+ daily orders are more suitable. Small enterprises with low order volumes lack sufficient historical data for effective models; simplified rule-based approaches are recommended.
- Inapplicable Scenarios: Low cancellation cost scenarios (e.g., free cancellation policies), fully dedicated driver supply with sufficient capacity, industries with strict regulations prohibiting dynamic pricing.
4. Implementation Risks and Mitigation:
- Driver Gaming Risk: Drivers may learn to “wait for higher bonuses,” intentionally delaying acceptance. Mitigation: Set bonus caps, introduce randomness, avoid forming stable expectations.
- Fairness Concerns: Identical orders receiving different bonuses at different times/locations may cause driver dissatisfaction. Mitigation: Transparent rules (e.g., publish bonus calculation formulas), set minimum guaranteed bonuses.
- System Stability Risk: Online service failures may interrupt bonus decisions. Mitigation: Implement degradation strategies (switch to fixed rules during failures), multi-active deployment, real-time monitoring.
5. Monitoring and Continuous Improvement: Post-deployment monitoring is critical. Key metrics to track include: daily bonus spend vs. budget, acceptance rate by stage, cancellation rate trends, driver complaint volume, and ROI calculations. The research team recommends weekly model performance reviews and monthly strategy adjustments. A/B testing should continue post-deployment to validate incremental improvements. Meituan’s team reports quarterly model refreshes incorporating new data patterns and business rule changes.
7. Paper Citation
Title: A Framework for Multi-stage Bonus Allocation in Meal Delivery Platform
Authors: Zhuolin Wu (Meituan Group), Li Wang (Huazhong University of Science and Technology), Fangsheng Huang, Linjun Zhou, Yu Song, Chengpeng Ye, Pengyu Nie, Hao Ren, Jinghua Hao, Renqing He, Zhizhao Sun (Meituan Group)
Venue:
- Conference: 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD ’22)
- Date: August 14-18, 2022
- Location: Washington, USA
- Publisher: ACM
Links:
- DOI: 10.1145/3534678.3539042
- arXiv: https://arxiv.org/abs/2202.10695
- ACM Digital Library: https://dl.acm.org/doi/10.1145/3534678.3539042
Impact:
- Google Scholar Citations: Approximately 180 citations as of February 2026
- Industry Application: Fully deployed on China’s largest food delivery platform, processing 30 million daily orders
- Awards: KDD 2022 Applied Data Science Track Distinguished Paper Nomination
