9
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ dynamic programming might work well on instances which are not too big, IMHO $\endgroup$ Mar 26, 2015 at 14:25
  • $\begingroup$ Which rotations are the obvious ones? All of them? Or only those $4$ leaving the base on the bottom, as you would pack actual boxes? $\endgroup$ Mar 26, 2015 at 16:24
  • $\begingroup$ @ZackWolske: In the paper I cited below, they consider all $90^\circ$ rotations: "We consider orthogonal packings where ninety-degree rotations are allowed." $\endgroup$ Mar 26, 2015 at 18:46
  • $\begingroup$ With "obvious" rotations I meant those that keep edges parallel to coordinate axes...in other words: multiples of 90 degrees. $\endgroup$ Mar 26, 2015 at 21:49

2 Answers 2

8
$\begingroup$

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


$\endgroup$
5
  • $\begingroup$ Looking either figure, it's easy to imagine a long, narrow box lying diagonally on the top. $\endgroup$ Mar 26, 2015 at 20:26
  • $\begingroup$ @SteveHuntsman: Yes, both algorithms only pack "orthogonally," but permitting all $90^\circ$ rotations. $\endgroup$ Mar 26, 2015 at 20:40
  • $\begingroup$ @SteveHuntsman: See my comment above. Rotations should leave edges of boxes parallel to coordinate axes. $\endgroup$ Mar 26, 2015 at 21:50
  • $\begingroup$ @RaymondHemmecke: That is the assumption in both papers I cited. $\endgroup$ Mar 26, 2015 at 22:58
  • 1
    $\begingroup$ Yes. But as Steve talked about "boxes lying diagonally" and as there was a question on what I meant with "obvious rotations", I clarified it here, too. $\endgroup$ Mar 26, 2015 at 23:04
5
$\begingroup$

It would probably take some work to turn this into an algorithm that can deal with rotations of the boxes, but you might be able to modify the three weight algorithm (a variation of ADMM) by Derbinsky, Bento, Elser, and Yedidia, which is a fairly simple algorithm that has recently beaten various records for circle and sphere packing in boxes.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.