Online meal delivery is undergoing explosive growth, as this service is
becoming increasingly popular. A meal delivery platform aims to provide
excellent and stable services for customers and restaurants. However, in
reality, several hundred thousand orders are canceled per day in the Meituan
meal delivery platform since they are not accepted by the crowd soucing
drivers. The cancellation of the orders is incredibly detrimental to the
customer's repurchase rate and the reputation of the Meituan meal delivery
platform. To solve this problem, a certain amount of specific funds is provided
by Meituan's business managers to encourage the crowdsourcing drivers to accept
more orders. To make better use of the funds, in this work, we propose a
framework to deal with the multi-stage bonus allocation problem for a meal
delivery platform. The objective of this framework is to maximize the number of
accepted orders within a limited bonus budget. This framework consists of a
semi-black-box acceptance probability model, a Lagrangian dual-based dynamic
programming algorithm, and an online allocation algorithm. The semi-black-box
acceptance probability model is employed to forecast the relationship between
the bonus allocated to order and its acceptance probability, the Lagrangian
dual-based dynamic programming algorithm aims to calculate the empirical
Lagrangian multiplier for each allocation stage offline based on the historical
data set, and the online allocation algorithm uses the results attained in the
offline part to calculate a proper delivery bonus for each order. To verify the
effectiveness and efficiency of our framework, both offline experiments on a
real-world data set and online A/B tests on the Meituan meal delivery platform
are conducted. Our results show that using the proposed framework, the total
order cancellations can be decreased by more than 25\% in reality.

提出一个为餐饮外卖平台解决订单被取消问题的方案，通过 Lagrangian 双重动态规划算法和在线分配算法来实现在有限奖金预算内最大化接受的订单数量，实现了 25% 以上的订单取消减少。