3d Bin Packing Algorithms

Question

Does anyone know of any 3D Bin Packing algorithms? I know of LAFF(Large Area Fits First); However, I'm in need of one where the constraint is that the tray has a fixed WIDTH and LENGTH (Height is inifinite). In the LAFF implementation, it searches through the boxes and finds the largest value of length and height, then makes this the fixed tray.

LAFF Algorithm

Answer 1

There is nothing stopping you from using LAFF with fixed xy-dimensions with infinite z-dimension. LAFF fits boxes in 2D level by level to become 3D.

I've created a LAFF open source project which you should be able to modify - alternatively run with the current code, just set the container height to Integer.MAX_VALUE. Infinite in a computer is really not infinite ;)

Answer 2

The guillotine cut heuristic (see for example this paper) is imprecise but fast - when you add a box to the container then the container is split into three disjoint sub-containers, for example if you had a 12x12x12 container and added an 8x8x8 box then you would be left with a 12x12x4 container, a 12x8x4 container, and an 8x8x4 container. The imprecision is owing to the fact that there are some legal (according to the laws of physics) packings that are disallowed by this space partitioning (for example, if you had a 12x12x12 container and four 12x8x4 boxes then a guillotine cut would partition the container so that you could only fit in three of the 12x8x4 boxes).

I used a randomized best-fit-decreasing algorithm when I implemented this - boxes were sorted first by volume in decreasing order and then by perimeter in increasing order (so more cube-like boxes get sorted first, e.g. an 8x8x8 box will precede a 4x8x16 box). I then randomized this box queue by assigning a sort key to each box equal to Random.nextFloat(1.0 / (itemIndex + 1)), so e.g. the first box will have a sort key between 0 and 1.0, the second box will have a sort key between 0 and 0.5, etc. Likewise when partitioning a container after inserting a box I favored partitioning the container into more-or-less equally sized sub-containers (i.e. the partitioning with the smallest perimeter) but included a random element so that occasionally the partitioner would generate one large sub-container and two smaller sub-containers.

I then ran this a dozen times in parallel and chose the best result. Note however that my task was just to come up with an estimator - it was more important for the algorithm to be consistent and fast than to be accurate.

A more complicated but more precise algorithm that I considered was the extreme points algorithm. I went with the guillotine cut algorithm due to it being faster and easier to implement/maintain.