Anticipatory Packing

Problem definition: Order fulfillment plays a pivotal role in shaping the competitiveness and profitability of online retailers. However, the erratic nature of order arrivals at fulfillment centers leads to imbalanced workloads and soaring operational costs. To tackle this challenge, we investigate the practice of anticipatory packing as a potential solution. Anticipatory packing involves strategically preparing packages during non-peak periods to fulfill orders during subsequent peak periods. In the face of order arrival uncertainties, our objective is to optimize the selection of packages to be packed during these non-peak periods. Methodology/results: We develop a two-stage sample-average approximation model using recent order data to enable effective anticipatory packing. For the second-stage problem, which optimizes the usage of prepacked packages, we design a constant-factor approximation algorithm. The first-stage problem is shown to be NP-hard to approximate within a factor of $\Omega ({(\max \{\sqrt{T},\Delta \})}^{1-\mathrm{ϵ}})$ asymptotically, where $T$ is the sample size and $\Delta$ is a measure for the inherent order structures. To address this, we propose general approximation algorithms with an approximation ratio of $O(\min \{TK,\Delta \})$, where $K$ is the maximum size of prepackages. For orders with laminar structures, the approximation ratio improves to $\lceil {\log }_2(K+1)\rceil$. To enhance practical performance, we introduce a refined integer programming reformulation and an efficient subgradient descent method for solving the associated Lagrangian dual. Experimental results with real-world data demonstrate that anticipatory packing can reduce operational costs by over 7% while significantly lowering fixed investment expenses. Managerial implications: We showcase the significant potential of anticipatory packing as an analytics-driven operational strategy. Its widespread adoption could lead to substantial reductions in both operating expenses and fixed investment costs.