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?