Formulation for the Bin Sizing Problem in E-commerce Fulfillment Centers

We study the bin dimensioning problem arising in e-commerce fulfillment centers: given a catalog of candidate bin types and a large heterogeneous inventory, select a type for each bin and assign all items so as to minimize total bin volume, subject to a limit on the number of distinct SKUs per bin, a per-SKU quantity limit, and a stacking rule that restricts placement of items of different SKUs to side-by-side placement along the bin length. The problem is motivated by the real operational needs of an American e-commerce fintech, one of the largest e-commerce platforms in the world, whose distribution centers range from a few thousand to over one million distinct SKUs.

The central contribution is a dimensional decomposition that reduces the original three-dimensional packing problem to a one-dimensional block-positioning problem. Items of the same SKU are first aggregated into blocks. The stacking constraint then implies that non-overlap between blocks of distinct SKUs reduces to a one-dimensional condition along the bin length, and the optimal X-dimension of each block for a given bin type is computed in O(1) time. This reduction transforms a geometric packing problem with quadratic non-overlap constraints into a one-dimensional capacity problem amenable to classical bin packing techniques.

Built on this decomposition, we propose three solution methods. First, a compact Mixed-Integer Linear Programming (MILP) formulation that serves as a formal problem statement. Second, a Best-Fit-Decreasing (BFD) heuristic adapted to our problem that scales to instances with up to 1.7 million blocks. Third, a column generation scheme with per-type pricing subproblems that yields tight LP lower bounds via a set partitioning reformulation.

Computational experiments are conducted on four real-world datasets provided by an e-commerce company. The BFD heuristic produces solutions in under 12 minutes for instances with up to 556,000 blocks. Column generation converged on the smallest dataset (105,765 blocks), certifying a BFD–LP optimality gap of 0.19%.