A Real-Time Control Policy to Achieve Maximum Throughput of an Online Order Fulfillment Network

Several major companies operate large online order fulfillment systems to ship goods from fulfillment centers through a distribution network to customer destinations in response to purchase orders. These networks make several types of decisions in real-time to serve customers. First, when a customer places an order, when and where (which fulfillment center) is it fulfilled from? Second, once an order has been packaged, how is it moved through the network to get to the customer? Making optimal decisions can yield significant cost savings or improvements in customer service. Unfortunately, these are large optimization problems, and are furthermore subject to uncertainty in the products and destinations of customer orders and the inventory replenishment of the fulfillment centers. This uncertainty makes the problem difficult to solve to optimality. Although the problem can be modeled as a Markov decision process, solving it exactly using standard computational methods is not possible due to the curse of dimensionality. We propose an alternative approach to this problem. We define a relatively simple real-time control policy and prove that it serves all customer demand if at all possible. This proof is achieved using Lyapunov drift techniques to relate the real-time control performance to the average performance necessary to serve all customers on average. Correspondingly, we characterize the average network performance, which may be used for network topology design while the control policy adapts to real-time stochasticity. We demonstrate the performance and stability properties on a numerical example based on hundreds of Amazon facility locations in the United States. The max-pressure control and greedy policies perform similarly at low demands, but at higher demand the throughput properties of the max-pressure control manifest as improvements in throughput and customer service metrics.