Joint Placement, Delivery Promise and Fulfillment in Online Retail

We consider placement, delivery promise and fulfillment decisions faced by an online retailer. We have a set of products with given numbers of units to be placed at different fulfillment centers with capacity constraints. Once we make the placement decisions, we face random demand for the products from different demand regions. In response to each demand, we pick a delivery promise to offer, which determines the probability that the demand converts into sale, as well as choose a fulfillment center to use to serve the demand. Our goal is to decide where to place the units to maximize the total expected profit from the sales over a finite selling horizon. We give a general approximation framework for this joint placement, delivery promise and fulfillment problem. Our framework is based on constructing two surrogate functions that approximate the total expected profit from the delivery promise and fulfillment policy when viewed as a function of the placement decisions. The first surrogate upper bounds the total expected profit obtained by the optimal policy, whereas the second surrogate lower bounds the total expected profit obtained by an approximate policy. The key is to construct the two surrogates such that they are within a constant factor of each other. We make the placement decisions by maximizing the first surrogate subject to capacity constraints at the fulfillment centers, whereas we make the delivery promise and fulfillment decisions by following the approximate policy. We show that we can obtain a performance guarantee by using this general framework. To instantiate our framework, we give two possible surrogates such that each can be used as our first or second surrogate. Using the two surrogates in different combinations yields four different approaches for our problem, the best of which provides 1/(4 +\epsilon)-approximation for any \epsilon > 0. We use synthetically generated datasets, as well as datasets based on an online retailer, to test the practical performance of our framework.