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

Stefanus Jasin () and Amitabh Sinha ()
Additional contact information
Stefanus Jasin: Stephen M. Ross School of Business, University of Michigan, Ann Arbor, Michigan 48109
Amitabh Sinha: Stephen M. Ross School of Business, University of Michigan, Ann Arbor, Michigan 48109

Operations Research, 2015, vol. 63, issue 6, 1336-1351

Abstract: 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.

Keywords: inventory management; ecommerce; asymptotic analysis (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (18)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2015.1441 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:63:y:2015:i:6:p:1336-1351

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().