Real-Time Omnichannel Fulfillment Optimization

To successfully implement an omnichannel fulfillment strategy, it is important to protect offline customers from stock-outs due to over-fulfillment of online customers. A natural question is when to fulfill online orders by using in-store inventory. In practice, retailers usually implement a so-called booking limit algorithm that imposes a threshold (i.e., booking limit) on the maximum number of online orders of a product that can be fulfilled from stores, and this booking limit is usually static. In this paper, we aim to theoretically quantify the performance of online booking limit algorithms in the context of omnichannel fulfillment. We first prove that for the continuous version of the problem where partial fulfillment is allowed, a booking limit algorithm with static booking limits can achieve tight competitive ratio when initial inventory is identical across stores, which extends the celebrated tightness result of booking limit algorithms in the context of single-leg two-fare revenue management studied by Ball and Queyranne (2009) from one dimension to higher dimensions. We then show that static booking limit algorithms cannot achieve tight competitive ratio when initial inventory is non-identical even for the two-store setting, and develop a more sophisticated algorithm where booking limits can be adjusted over time based on realized demands via solving a math program. This adaptive booking limit algorithm can achieve tight competitive ratio. To extend our analysis and algorithm to the discrete setting, we propose a novel online rounding scheme, and prove that the expected profit of this “randomized booking limit” algorithm exactly matches the corresponding deterministic fractional algorithm. Finally, we conduct a concise numerical study to demonstrate the performance of booking limit algorithms under realistic (non-worst-case) demand sequences