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.

Improve this question
$\endgroup$
4
  • $\begingroup$ dynamic programming might work well on instances which are not too big, IMHO $\endgroup$
    – Dima Pasechnik
    Commented 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$
    – Zack Wolske
    Commented 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$
    – Joseph O'Rourke
    Commented 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$
    – Raymond Hemmecke
    Commented Mar 26, 2015 at 21:49

2 Answers 2

Reset to default
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

Improve this answer
$\endgroup$
5
  • $\begingroup$ Looking either figure, it's easy to imagine a long, narrow box lying diagonally on the top. $\endgroup$
    – Steve Huntsman
    Commented Mar 26, 2015 at 20:26
  • $\begingroup$ @SteveHuntsman: Yes, both algorithms only pack "orthogonally," but permitting all $90^\circ$ rotations. $\endgroup$
    – Joseph O'Rourke
    Commented Mar 26, 2015 at 20:40
  • $\begingroup$ @SteveHuntsman: See my comment above. Rotations should leave edges of boxes parallel to coordinate axes. $\endgroup$
    – Raymond Hemmecke
    Commented Mar 26, 2015 at 21:50
  • $\begingroup$ @RaymondHemmecke: That is the assumption in both papers I cited. $\endgroup$
    – Joseph O'Rourke
    Commented 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$
    – Raymond Hemmecke
    Commented 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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .