3 dimensional bin packing algorithms

40
votes

I'm faced with a 3 dimensional bin 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 exact solvers? Branch and Bound? What problem instance sizes can I expect to solve with reasonable computing resources?
2) what are the best heuristic solvers?
3) What off-the-shelf solutions exist to conduct some experiments with?

6
algorithmlanguage-agnosticmathematical-optimizationnp-hardbin-packing
Are you packing boxes into box-shaped bins? Can you rotate boxes to make them fit? – Jason Orendorff
Karpreduction, skip unsolved steps ("perfect") isomorphy sure tricky we can – Niklas Rosencrantz
stackoverflow.com/questions/1563271/3d-bin-packing-algorithm – Brad Gilbert
No rotation. Yes, I'm packing boxes in box shaped bins. Thanks Brad, I do know about that question but didn't find the answers or the question satisfactory. – BuschnicK
BK, I just looked at our version of MaxLoadPro. You can define your own "vehicle" or "tote" and are not restricted by any pre-defined dimensions. Of course, the software uses a heuristic, but it does allow you to move stuff around after it has recommended a solution. – Grembo

6 Answers

7
votes

As far as off the shelf solutions, check out MAXLOADPRO for loading trucks. It may be able to be configured to load any rectangular volume, but I haven't tried that yet. In general 3d bin-packing problems have the added complication that the objects can be rotated into different positions so for any object with a given length, width and height, you effectively have to create three variables representing each position, but you only use one in the solution.

In general, stand-alone MIP formulations (or branch and bound) don't work well for the 2d or 3d problem but constraint programming has met with some success producing exact solutions for the 2d problem. Check out this abstract. Without looking at the paper, I like the decomposition approach for the problem where you're trying to minimize the number of same-sized bins. I haven't seen as many results for the 3d problem, but let us know if you find any that are implementable.

Good luck !

4
votes

I've written a program which tests three various algorithms. Also this is a good source of information: A Thousand Ways to Pack the Bin - A Practical Approach to Two-Dimensional Rectangle Bin Packing. It is for two-dimensional rectangle bin, but you can always transform it to 3D.

2
votes

From wikipedia:

Although these simple strategies are often good enough, efficient approximation algorithms have been demonstrated that can solve the bin packing problem within any fixed percentage of the optimal solution for sufficiently large inputs

Here are the two sources they give for this:

1
votes

Best exact solver: Use dynamic programming.

State variables:

  1. Items you have packed and discarded.
  2. Space filled in the container.

If the container is a parallelepiped grid, and the items "fit" in exact cells of the grid, you can use a 3-dimensional array to represent state variable 2. Otherwise, you will have to use more complex data structures.

Best heuristic solvers

I don't know. Perhaps Variable Neighborhood Search. There are some similarities between your problem and the timetable construction problem (which I'm working on), so the same heuristic might be good for both.

Off-the-shelf solutions to conduct experiments

I'm sorry, I don't even have a clue.

0
votes

You question is similar to: 3d bin packing algorithm

Although, because you dis-allow rotation, you can get pretty good results. I suggest looking more towards a FIRST-FIT-DECREASING solution.

0
votes

3dbinpacking is a commercial solution (not an algorithm) exposing an API to consume with nice visualization. It offers:

  • Single bin packing
  • Multi bin packing
  • Find third dimension
  • Find a bin dimensions