Multi-Item Order Fulfillment Revisited: LP Formulation and Prophet Inequality
研究了电商平台多仓库有限库存下多商品订单履行的动态问题，提出结合随机履行、先知不等式和次梯度方法的策略，证明其近似最优性，并给出网络收益管理的新边界。
In this work, we revisit the multi-item order fulfillment model introduced by Jasin and Sinha (2015). Specifically, we study a dynamic setting in which an e-commerce platform (or online retailer) with multiple warehouses and finite inventory faces the problem of fulfilling orders that may contain multiple items. The platform’s goal is to minimize the expected cost incurred from the fulfillment process, subject to warehouses’ inventory constraints. Differing from the classical literature on multi-item fulfillment, we use the method-based formulation to design a class of dynamic policies that combine ideas from randomized fulfillment, prophet inequalities, and subgradient methods for the general multi-item fulfillment model. Specifically, by establishing connections between the fulfillment and prophet inequality literature, we prove that our algorithm has strong approximation guarantees in nonasymptotic settings, which also happens to be asymptotically optimal. Our result shows that there is a simple and near-optimal procedure for solving multi-item fulfillment problems once the online retailer has enough inventory, independent of other problem parameters. To the best of our knowledge, this is the first result of this type in the context of multi-item order fulfillment. In addition, and of independent interest, our analysis also leads to new asymptotically optimal bounds for network revenue management problems. This paper was accepted by Omar Besbes, market design, platform, and demand analytics. Supplemental Material: The online appendix and data files are available at https://doi.org/10.1287/mnsc.2023.00357 .