Lp-Based Artificial Dependency for Probabilistic Etail Order Fulfillment

Abstract

We consider an online multi-item retailer with multiple fulfillment facilities and finite inventory, with the objective of minimizing the expected shipping cost of fulfilling customer orders over a finite horizon. We approximate the stochastic dynamic programming formulation of the problem with an equivalent deterministic linear program, which we use to develop a probabilistic fulfillment heuristic that is provably optimal in the asymptotic sense. This first heuristic, however, relies on solving an LP that is exponential in the size of the input. Therefore, we subsequently provide another heuristic which solves an LP that is polynomial in the size of the input, and prove an upper bound on its asymptotic competitive ratio. This heuristic works by modifying the LP solution with artificial dependencies, with the resulting fractional variables used to probabilistically fulfill orders. A hardness result shows that asymptotically optimal policies that are computationally efficient cannot exist. Finally, we conduct numerical experiments that show that our heuristic's performance is very close to optimal for a range of parameters.