Operational research : Shelf packing problem

[MathiasW]

Homework Statement

I'm faced with a Shelf Packing problem and am currently conducting some preliminary research as to which algorithms/heuristics are currently yielding the best results. Since the problem is NP hard I do not expect to find the optimal solution in every case, but I was wondering:

1) what are the best algorithms?
2) what are the best heuristic methods?
3) What software exists to conduct some experiments with? Can you just use Maple?

a bit more info about the problem:

You are given a rack which is 1000 mm wide, 2200 mm high and 600 mm deep. Further, you have an unlimited amount of shelves that are 1000 mm wide, 10 mm high and 600 mm deep. Each shelve has a weight limit of 50000 g and shelves can only be placed at positions that are at 50mm from each other (imagine a rack with holes every 50mm, which are possible positions for the shelves). Further, there is a set of rectangular boxes. Each box i, for i=1,…,n has a given length, height, width and weight. The goal is now to place boxes on shelves such that the total packed volume in the rack is maximized. Notice that you can decide on the number of shelves to be used and the position of these shelves in the rack. The following restrictions need to be taken into account: - Each box can be placed at most once - The size and weight capacity of the shelves can not be violated - No overhang of boxes is allowed Boxes can be placed in any orientation and on top of any other box.

How do I best approach this problem? The goal is to minimise the free space in the rack. Any ideas?

Homework Equations

none

The Attempt at a Solution

I think there should be some kind of heuristic available that does the following:
1. put 1 box in a random position at the shelf
2. check for all the other boxes for which boxes, the free space within 1 layer is minimised, concidering all constraints.
3. add that box to the shelf and go back to 2 until the layer is full.
4. check if another box on top of the exisiting layer can be added (given the contraints), if not: go to 1, if so: go to 4.
5. repeat until raack is full.

Once more the questions:
1) what are the best algorithms?
2) what are the best heuristic methods?
3) What software exists to conduct some experiments with? Can you just use Maple?

Can anyone help me in the right direction?

 

[skeptic2]

Where are the lengths, widths, heights of the boxes defined. Is each one unique or are there a limited number of different box sizes? What is the weight of the boxes?

 

[MathiasW]

Oops forgot them.

there are 100 boxes of different size, each with different l,b,w and weight.
Hope this helps!

 

[skeptic2]

The weight of each box, or at least its density needs to be known in order to determine how many shelves must be used. Obviously it would be advantageous to use as few shelves as possible.

The specific lengths, widths and heights must be known to determine how to pack them.

You are aware this problem comes under the classification of NP hard, aren't you?

http://mlug.missouri.edu/list-archives/discussion/2008-06/msg00005.php3
http://stackoverflow.com/questions/...-how-to-fit-smaller-boxes-into-a-larger-packa
http://www.mpi-inf.mpg.de/~althaus/trunk_conf.pdf
http://www.micsymposium.org/mics_2004/Sweep.pdf
http://www.scottaaronson.com/talks/anthropic.html

 

[MathiasW]

unfortunatly, I am aware it's a NP hard problem. Thanks already for your time and effort, the links look promising.

I am also thinking of just solving it by looking at it as being a Bin problem or by using a simple greedy algorithm. I really am not used to solving these kinds of problems, so any help would be very welcome!

I also added all the data for the boxes in an attachment.