Multi-Item Online Order Fulfillment : A Competitive Analysis

The boom of e-commerce in the globe in recent years has expedited the expansion of fulfillment infrastructures by e-retailers. While e-retailers are building more warehouses to offer faster delivery service than ever, the associated fulfillment costs have skyrocketed over the past decade. In this paper, we study the problem of minimizing fulfillment costs, in which an e-retailer must decide which warehouse(s) to fulfill each order from, subject to warehouses' inventory constraints. The e-retailer can split an order, at an additional cost, and fulfill it from different warehouses. It is notoriously challenging to make effective real-time fulfillment decisions at the occurrence of order split, which has become a major problem for e-retailers.We focus on a two-layer distribution network that has been implemented in practice by major e-retailers. We analyze the performance of fulfillment policies that do not rely on demand forecasts. We show that, under an assumption that aligns with the practice of most e-retailers, a myopic policy achieves a constant performance ratio compared to an optimal clairvoyant algorithm. We further show that this ratio is tight. More generally, we characterize the performance guarantees of the myopic policy in terms of the cost parameters of the model. Finally, we complement our theoretical results by conducting a numerical study and demonstrate the good performance of the myopic policy