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 .