An LP-Based Correlated Rounding Scheme for Multi-Item Ecommerce Order Fulfillment

We consider an online multi-item retailer with multiple fulfillment facilities and finite inventory. The challenge faced by the retailer is to construct a fulfillment policy to decide from which facility each of the items in the arriving order should be fulfilled, in a way that minimizes the expected total shipping costs of fulfilling customer orders over a finite horizon. Shipping costs are linear in the size of the package shipped as well as the distance from the facility to the customer. We approximate the stochastic control formulation, which is computationally intractable, with a deterministic linear program (DLP) whose size is polynomial in the size of the input. We then study the performance of two fulfillment heuristics derived from the solution of the DLP. The first heuristic implements the solution of the DLP as fulfillment probability for each item. Since fulfillment decision for each item is made independently of fulfillment decision of other items in the same order, this heuristic does not have a satisfactory performance. The second heuristic improves the first heuristic by allowing fulfillment consolidation across different items in the same order. We do this by modifying the DLP solution through a carefully constructed correlated rounding (or coupling) among the decision variables. We provide a theoretical upper bound on the asymptotic competitive ratio of both heuristics with respect to the optimal policy. Our numerical experiments show that the second heuristic performs very close to optimal for a wide range of problem parameters.