Optimizing Inventory Placement for a Downstream Online Matching Problem

Boris Epstein, Will Ma

Abstract

We study the inventory placement problem of splitting $Q$ units of a single item across warehouses, in advance of a downstream online matching problem that represents the dynamic fulfillment decisions of an e-commerce retailer. This is a challenging problem both in theory, because the downstream matching problem itself is computationally hard, and in practice, because the fulfillment team is constantly updating its algorithm and the placement team cannot directly evaluate how a placement decision would perform. We compare the performance of three placement procedures based on optimizing surrogate functions that have been studied and applied: Offline, Myopic, and Fluid placement. On the theory side, we show that optimizing inventory placement for the Offline surrogate leads to a $(1-(1-1/d)^d)/2$-approximation for the joint placement and fulfillment problem. We assume $d$ is an upper bound on how many warehouses can serve any demand location and that stochastic arrivals satisfy either temporal or spatial independence. The crux of our theoretical contribution is to use randomized rounding to derive a tight $(1-(1-1/d)^d)$-approximation for the integer programming problem of optimizing the Offline surrogate. We use statistical learning to show that rounding after optimizing a sample-average Offline surrogate, which is necessary due to the exponentially-sized support, does indeed have vanishing loss. On the experimental side, we extract real-world sequences of customer orders from publicly-available JD.com data and evaluate different combinations of placement and fulfillment procedures. Optimizing the Offline surrogate performs best overall, even compared to simulation procedures, corroborating our theory.

Introduction

In large-scale e-commerce, retailers face a critical two-stage decision process. First, they must distribute a fixed amount of inventory ($Q$ units) across a network of warehouses—a task known as Inventory Placement. Subsequently, as customer orders arrive dynamically, they must decide which warehouse should ship each order—Online Fulfillment.

These decisions are deeply coupled: optimal placement depends on future fulfillment, while fulfillment is constrained by prior placement. Jointly optimizing both is NP-hard and practically difficult, as placement and fulfillment are often managed by separate teams. To bridge this gap, placement teams typically use "surrogate functions"—simplified models of future demand—to guide their decisions. This research investigates which surrogate is most effective and provides theoretical foundations for the most promising approach.

Comparison of Placement Procedures

The study evaluates three primary placement procedures based on different surrogate models:

  1. Fluid Placement (FLU): A deterministic model that replaces random demand with its expected value. While computationally fast, it can be brittle in high-inventory regimes.
  2. Myopic Placement (MYO): A pessimistic model assuming fulfillment will simply select the closest available unit without considering future demand.
  3. Offline Placement (OFF): An optimistic model assuming the fulfillment team has "perfect hindsight" (knowledge of all demand in advance).

The trade-offs between these procedures are summarized in Table 1.

Table 1: Comparison of Offline, Myopic, and Fluid placement procedures across information requirements, computational complexity, and theoretical guarantees.

Theoretical Contributions

The core technical contribution is a randomized rounding algorithm for the Offline surrogate. Since inventory must be placed in integer units but optimization is more tractable with fractions, the authors developed a two-iteration rounding scheme based on dependent rounding techniques.

Approximation Guarantees

The paper establishes a tight $(1 - (1-1/d)^d)$-approximation for the Offline surrogate, where $d$ represents the maximum number of warehouses serving any single demand location. This guarantee improves as network flexibility decreases. For instance, with $d=2$, the guarantee is $0.75$, outperforming the standard $1-1/e \approx 0.63$ typically found in general matching problems.

Statistical Learning and Multi-SKU Settings

Using statistical learning theory (Rademacher complexity), the authors prove that sampling a manageable number of demand scenarios allows the Offline surrogate to generalize effectively, even with exponentially large demand supports. Furthermore, the rounding technique extends to multi-SKU settings, improving the best-known approximation ratio from $1/2$ to $1-1/e$.

Empirical Evaluation

The researchers tested these procedures using 90 synthetic instances mirroring real-world logistics (e.g., Long-chain and RDC-FDC networks) and real-world customer order sequences from JD.com.

Key Results

  • Empirical Dominance: Offline Placement combined with Offline Shadow Price fulfillment achieved a competitive ratio exceeding 0.98 in most scenarios.
  • Robustness: Offline placement consistently outperformed Myopic and Fluid approaches across various network geometries and demand volatilities.
  • Fluid Degeneracy: Fluid placement was found to be particularly brittle when inventory levels exceed expected demand, leading to arbitrary and poor decisions.

Conclusion and Future Work

The "Offline" surrogate proves to be the most robust guide for inventory placement. If the fulfillment team is competent, the placement team should assume they are perfect.

Future research directions include:

  • Endogenous Demand: Accounting for how faster shipping (enabled by better placement) might drive higher customer demand.
  • Dynamic Placement: Moving from a single inventory "drop" to dynamic replenishment or redistribution throughout a season.
  • Joint Stocking and Placement: Integrating the decision of how much to buy with where to place it.

Summary updated

Abstract

We study the inventory placement problem of splitting $Q$ units of a single item across warehouses, in advance of a downstream online matching problem that represents the dynamic fulfillment decisions of an e-commerce retailer. This is a challenging problem both in theory, because the downstream matching problem itself is computationally hard, and in practice, because the fulfillment team is constantly updating its algorithm and the placement team cannot directly evaluate how a placement decision would perform. We compare the performance of three placement procedures based on optimizing surrogate functions that have been studied and applied: Offline, Myopic, and Fluid placement. On the theory side, we show that optimizing inventory placement for the Offline surrogate leads to a $(1-(1-1/d)^d)/2$-approximation for the joint placement and fulfillment problem. We assume $d$ is an upper bound on how many warehouses can serve any demand location and that stochastic arrivals satisfy either temporal or spatial independence. The crux of our theoretical contribution is to use randomized rounding to derive a tight $(1-(1-1/d)^d)$-approximation for the integer programming problem of optimizing the Offline surrogate. We use statistical learning to show that rounding after optimizing a sample-average Offline surrogate, which is necessary due to the exponentially-sized support, does indeed have vanishing loss. On the experimental side, we extract real-world sequences of customer orders from publicly-available JD.com data and evaluate different combinations of placement and fulfillment procedures. Optimizing the Offline surrogate performs best overall, even compared to simulation procedures, corroborating our theory.
BibTeX
@misc{epstein2024optimizing,
  author = {Boris Epstein and Will Ma},
  title = {{Optimizing Inventory Placement for a Downstream Online Matching Problem}},
  year = {2024},
  eprint = {2403.04598},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2403.04598},
}
Figure