Introduction
In the modern e-commerce landscape, the efficiency of the fulfillment process is a critical driver of profitability and customer satisfaction. When a customer places an order containing multiple items, the retailer faces a complex optimization problem: how to assign these items to fulfillment centers (FCs) to minimize shipping costs. The primary cost driver is often the "fixed" cost associated with each shipment—the box, the label, and the labor required for packing. Consequently, the goal is to consolidate as many items as possible into a single box from a single FC.
However, inventory is distributed across a vast network of warehouses. To manage this, retailers typically solve a Large-Scale Linear Program (LP) that determines the probability $u_{ki}$ with which item $i$ should be sourced from FC $k$. The challenge lies in the implementation: how can we randomly select an FC for each item such that the marginal probabilities $u_{ki}$ are strictly respected, while maximizing the probability that all items in an order are assigned to the same FC? This is known as the correlated rounding problem.
The Correlated Rounding Challenge
Previous approaches to correlated rounding in fulfillment systems suffered from two main drawbacks. First, many were computationally intensive, making them difficult to deploy in real-time environments where decisions must be made in milliseconds. Second, their theoretical performance guarantees were often poor. Specifically, the existing benchmark—the Jasin and Sinha (JS) scheme—provided a competitive guarantee that grew linearly with the number of items in an order ($q$). As order sizes increased, the gap between the rounding scheme's performance and the theoretical optimum widened significantly.
This paper introduces two new algorithms, Dilate and ForceOpen, which bridge this gap by achieving order-optimal guarantees with significantly lower computational overhead.
Methodology: The Dilate and ForceOpen Schemes
The core innovation of this research is the use of a "time dilation" intuition, leveraging the properties of the Poisson process to induce positive correlation between item assignments.
1. The Dilate Scheme
The Dilate scheme provides a $(1 + \ln q)$-competitive guarantee. The algorithm operates by imagining that each FC $k$ "opens" at a random time $E_k$, determined by a Poisson clock. Each item $i$ in the order observes these clocks through a unique, dilated lens: it perceives FC $k$ as opening at a delayed time proportional to $1/u_{ki}$. The item is then assigned to the first FC it perceives as being open.
Because an FC that opens early in the global Poisson process is likely to be the first one "seen" by multiple items, the items naturally cluster into the same shipment. This approach uses the memoryless property of Exponential distributions to ensure that the marginal probabilities $u_{ki}$ are perfectly satisfied while maximizing the overlap between items.
2. The ForceOpen Scheme
In scenarios where the fulfillment network is sparse—meaning an item is only stocked in a small number of FCs ($d$)—the author proposes the ForceOpen scheme. This variation ensures that FCs are "forced" to open by a specific deadline. This provides a competitive guarantee based on the network's sparsity ($d$) rather than the total number of items, offering a robust alternative for specific inventory configurations.
Theoretical Insights
A significant contribution of this work is the formal connection established between the fulfillment rounding problem and the classic Set Cover problem in computer science. By proving this link, the author demonstrates that a logarithmic guarantee ($1 + \ln q$) is the best achievable performance for any polynomial-time rounding scheme. This proves that the Dilate scheme is not just an improvement, but is theoretically order-optimal.
Empirical Evaluation and Results
The proposed schemes were tested in a simulated environment modeled after real-world e-commerce constraints, using the 99 largest US metropolitan areas and the 10 largest Amazon fulfillment centers (as of 2015). Costs were calculated using real-world estimates for fixed packaging ($8.759 per box) and variable shipping distances.
Key Findings:
- Computational Efficiency: The Dilate algorithm is remarkably simple, requiring approximately 10 lines of code compared to the 100+ lines required for previous state-of-the-art methods. In large-scale simulations, the new schemes achieved a 10x speedup, running in 14–18 seconds per instance compared to over 160 seconds for the previous standard.
- Reduction in Split Shipments: The Dilate scheme consistently resulted in fewer boxes per order. For an order of 20 items, the theoretical improvement moves from a linear factor of 5 to a logarithmic factor of approximately 3.
- Cost Savings: Across almost all tested scenarios, the Dilate scheme produced lower total fulfillment costs than the JS benchmark, particularly as the maximum number of items per order ($n_{max}$) increased.
Conclusion
By reframing the correlated rounding problem through the lens of Poisson processes, this paper provides a simple, elegant, and mathematically optimal solution to a major bottleneck in e-commerce logistics. The Dilate and ForceOpen schemes offer a rare combination of theoretical optimality and practical speed, making them ideal candidates for high-volume, real-time fulfillment systems. Future work may involve integrating these schemes with more complex LPs that account for real-time inventory shocks and volatile backorder costs.
Summary updated