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

This is not an easy problem and I guess it's even NP-hard. You seem to have some nice ideas though! I would recommend reading about the Knapsack problem to get some more theory and new ideas.

Answer 2

I don't think this is trivial. I believe the proper name for this is bin packing, and Google searches reveal a lot of academic papers, but no simple algorithms (especially in 3-D, which is what you want).

How many objects are you looking to handle in practice ? If it's relatively few (i.e. not hundreds into a TEU shipping container, but perhaps a few into a cardboard box for Fedexing), then perhaps a simple brute force approach for a local maxima solution may be the best approach.

Answer 3

Hi

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 :-)

Regards

Mark

Answer 4

I'm not an expert but I think it's not currently possible to find the optimal result without using a brute force approach, but I can suggest some things though:

1) If you start packing the object with the greatest volume on the first container and the second biggest object on the second container, third biggest on the first container ad infinitum, the result will be at most 14% (or is it 34%? Can't remember exactly!) worst than the optimal result. I've read this somewhere on the book "The Man Who Loved Only Numbers" by Paul Hoffman.

2) A genetic algorithm should provide you relatively better results at the cost of some performance.

There is also some companies like Logen Solutions and MaxLoad that do this for a living, so if you are willing to pay you can also use their web services.

Answer 5

this is is code i'm working on now but i'm at the very begining. Please help!

     function __construct($product, $package) {
 // Product
 for ($i = 0; $i < count($product); $i++) {
  $product[$i]['volume'] = $product[$i]['length'] * $product[$i]['width'] * $product[$i]['height'];

  $dimensions = array($product[$i]['length'], $product[$i]['width'], $product[$i]['height']);

  sort($dimensions);

  foreach($dimensions as $key => $value) {
   if ($key == 0) {
    $product[$i]['x'] = $value; 
   }

   if ($key == 1) {
    $product[$i]['y'] = $value; 
   }

   if ($key == 2) {
    $product[$i]['z'] = $value; 
   }
  }
 }

 for ($i = 0; $i < count($package); $i++) {
  $package[$i]['volume'] = $package[$i]['length'] * $package[$i]['width'] * $package[$i]['height'];

  $dimensions = array($package[$i]['length'], $package[$i]['width'], $package[$i]['height']);

  sort($dimensions);

  foreach($dimensions as $key => $value) {
   if ($key == 0) { 
    $package[$i]['x'] = $value; 
   }

   if ($key == 1) {
    $package[$i]['y'] = $value;
   }

   if ($key == 2) {
    $package[$i]['z'] = $value;
   }
  }
 }

 $boxes = $this->packProducts($product, $package);

 for ($i = 0; $i < count($boxes); $i++) {
  $this->addItem($boxes[$i]['length'], $boxes[$i]['width'], $boxes[$i]['height'], $boxes[$i]['current_weight'], $boxes[$i]['price']);
 }
}