Multi-Item Order Fulfillment Revisited: LP Formulation and Prophet Inequality

• 成果类型: Article; Early Access
• 署名作者: Amil, Ayoub; Makhdoumi, Ali; Wei, Yehua
• 署名单位: Duke University
• 刊物名称: MANAGEMENT SCIENCE
• ISSN/ISSBN: 0025-1909
• DOI: 10.1287/mnsc.2023.00357
• 发表日期: 2025
• 关键词: online retailing; multi-item order fulfillment; competitive ratio analysis; prophet inequality; network revenue management

摘要

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.