Warehouse Packing
1D Bin Packing
A warehouse fulfillment center must pack order items into shipping containers of fixed capacity. The goal is to minimize the number of containers used while ensuring every item is packed. This is the 1D Bin Packing Problem — one of the classic NP-hard problems in combinatorial optimization.
The Problem
Why packing optimization matters for warehouse operations
Consider a warehouse fulfillment center processing hundreds of orders daily. Each order contains items of varying sizes — books, electronics, clothing, kitchenware — that must be packed into standardized shipping containers with a fixed weight or volume capacity of Q units. Every item must be packed into exactly one container, and no container may exceed its capacity.
The objective is to minimize the total number of containers used, which directly translates to reduced shipping costs, less packaging material waste, and more efficient use of delivery vehicle space. In large-scale fulfillment operations, even a 10–15% reduction in container count can save thousands of containers per week and significantly lower transportation expenses.
This problem is strongly NP-hard: no known algorithm can guarantee an optimal solution in polynomial time. With n items, the number of possible assignments to bins grows super-exponentially. The Bin Packing Problem was studied extensively in the 1970s by Johnson (1973), who established the foundational approximation results that remain central to the field today.
subject to
Σj xij = 1 // each item i packed in exactly one bin
Σi si · xij ≤ C · yj // bin capacity not exceeded
xij ∈ {0, 1}, yj ∈ {0, 1} // binary assignment & bin usage
Where si is the size of item i, C is the container capacity, xij indicates whether item i is assigned to bin j, and yj indicates whether bin j is used.
See full Bin Packing theory and all algorithmsTry It Yourself
Pack warehouse items into shipping containers
Warehouse Packing Optimizer
8 Items · Capacity 100| Item | Size |
|---|
Ready. Click “Solve & Compare All Algorithms” to run.
| Algorithm | Bins | Utilization | Time |
|---|---|---|---|
| Click Solve & Compare All Algorithms | |||
The Algorithms
Heuristic approaches to bin packing
First Fit (FF)
O(n²)Process items in the given order. For each item, scan bins from left to right and place the item in the first bin with enough remaining capacity. If no existing bin can accommodate the item, open a new bin. Simple and fast, but sensitive to input order — a poor ordering can lead to many partially filled bins.
First Fit Decreasing (FFD)
O(n log n) | Guarantee: ≤ 11/9 · OPT + 6/9 binsSort all items by size in descending order, then apply First Fit. By placing the largest items first, FFD creates a foundation of large items that smaller items can efficiently fill around. This simple preprocessing step dramatically improves solution quality and provides a provable worst-case guarantee of at most 11/9 · OPT + 6/9 bins, established by Johnson (1973).
Best Fit Decreasing (BFD)
O(n log n)Sort all items by size in descending order. For each item, place it in the bin with the least remaining capacity that can still accommodate it (the tightest fit). If no bin fits, open a new bin. BFD tends to produce tightly packed bins by minimizing wasted space within each container, often matching or outperforming FFD in practice.
Real-World Complexity
Why warehouse packing goes beyond the 1D model
Beyond One Dimension
- 3D packing — Real containers have length, width, and height; items must physically fit in three dimensions with no overlap
- Weight limits — Containers have both volume and weight constraints; heavy items may require separate handling
- Fragility constraints — Fragile items cannot be placed beneath heavy ones; packing order matters vertically
- Stacking constraints — Some items cannot support weight on top; others have orientation requirements (e.g., “this side up”)
- Item orientation — Items may or may not be rotatable, adding combinatorial choices per item
- Multi-container-size selection — Warehouses stock multiple box sizes; choosing the right size for each group of items is itself an optimization problem
- Load balancing for shipping — Containers going to the same destination should be balanced in weight for vehicle stability and handling efficiency
Key References
Foundational works in bin packing
- (1973). “Near-optimal bin packing algorithms.” Doctoral dissertation, Massachusetts Institute of Technology.
- (2013). “Bin packing approximation algorithms: Survey and classification.” Handbook of Combinatorial Optimization, 455–531.
Need to optimize your warehouse operations?
From bin packing to inventory management and supply chain optimization, mathematical modeling can transform your fulfillment operations. Let’s discuss how Operations Research can work for you.