[Math] How to pack 3D boxes into a bigger box

packing-and-covering

Given a box of given size $L\times M\times N$ and a list of smaller boxes of given sizes $(l_i,m_i,n_i)$, decide whether the smaller boxes altogether fit into the big box (and produce such a packing if possible).

The problem is NP-complete…so I am looking for a good heuristic algorithm…the algorithm should allow for (the obvious possible) rotations of the boxes.

What are currently good/best heuristic algorithms and codes? Links to papers or webpages are also welcome.

Best Answer

Here are two sources, the first of which is the more substantive. The problem is even hard to approximate, but algorithms are available that achieve about $2\frac{1}{2} \times$ the optimal packing.

(1) Miyazawa, Flavio Keidi, and Yoshiko Wakabayashi. "Three-dimensional packings with rotations." Computers & Operations Research. 36.10 (2009): 2801-2815. (PDF download.)


  BinPacking1


(2) E. Dube, L.R. Kanavathy. "Optimizing three-dimensional bin packing through simulation." Proc. Modeling, Simulation, Optimization. 2006. (PDF download


          BinPacking2