Stacking Algorithm - Stack 3d objects in smallest area possible

Question

I'm trying to solve the problem of stacking objects into the most convenient size for postage. The size and shape of objects will be varied. Length, width and height of all objects is known.

For example a customer may order a (length x width x height) 200x100x10cm object (wide, long and flat) along with 2 50x50x50cm objects (cubes). If i was to pack this i would put the flat wide object on the bottom and the 2 cubes on top, side by side.

Does anybody have, or know of, a reasonably efficient algorithmic solution to this? Or even an approach to the way i should be thinking about solving this. I've been coding all week, it's late and my brain is fried. I'm not desperate yet but I just want to have a day off tomorrow.

The way I envisage it would be to create an array representing a 3d space, each array element representing 1 square/cm in that space. The 3d space length and width would be based on the longest object and the widest objects. Then you just work from the biggest object down to the smallest object, finding sufficient 'holes' and filling them up as you go.

Although i'm certain there would be a mathematical formula which does this a lot more effieiently.

Any ideas?

Answer 1

First advice -- step away from the keyboard, stop coding, start thinking !

Second advice -- your proposed approach (largest first, then next largest) is a well respected and much used heuristic for this problem. And, unless you have huge numbers of things to pack, or huge numbers of packings to do, don't be too concerned with execution efficiency, development efficiency should probably be your first priority.

Third advice -- Google for bin-packing but be warned, there's a huge amount of literature on this.

Finally, don't be so certain that there is a mathematical formula for this :-)