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$
  • $\begingroup$ dynamic programming might work well on instances which are not too big, IMHO $\endgroup$ – Dima Pasechnik Mar 26 '15 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$ – Zack Wolske Mar 26 '15 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$ – Joseph O'Rourke Mar 26 '15 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$ – Raymond Hemmecke Mar 26 '15 at 21:49
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$
  • $\begingroup$ Looking either figure, it's easy to imagine a long, narrow box lying diagonally on the top. $\endgroup$ – Steve Huntsman Mar 26 '15 at 20:26
  • $\begingroup$ @SteveHuntsman: Yes, both algorithms only pack "orthogonally," but permitting all $90^\circ$ rotations. $\endgroup$ – Joseph O'Rourke Mar 26 '15 at 20:40
  • $\begingroup$ @SteveHuntsman: See my comment above. Rotations should leave edges of boxes parallel to coordinate axes. $\endgroup$ – Raymond Hemmecke Mar 26 '15 at 21:50
  • $\begingroup$ @RaymondHemmecke: That is the assumption in both papers I cited. $\endgroup$ – Joseph O'Rourke Mar 26 '15 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$ – Raymond Hemmecke Mar 26 '15 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, privacy policy and cookie policy

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