3 dimensional bin packing algorithms

Question

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?

Nijinsky

Are you packing boxes into box-shaped bins? Can you rotate boxes to make them fit? – Harping

Karpreduction, skip unsolved steps ("perfect") isomorphy sure tricky we can – Cavort

https://mcmap.net/q/391129/-3d-bin-packing-algorithm-closed – Hussey

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. – Nijinsky

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. – Capacitor

Answer 1

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 !

Capacitor

Answer 2

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.

Easterner

Answer 3

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:

• Approximation Algorithms
• Bin packing can be solved within 1 + ε in linear time

Swale

Note that at least the "1 + ε" paper is referring to the one-dimensional bin packing problem, while the question is about three-dimensional packing (of boxes, I assume). The simple strategies trivially generalize to three dimensions; I'm not sure about the more sophisticated ones. – Harping

"(of boxes, I assume)" - close but not quite. I'm dealing with wooden trusses which get pressed together into larger beams and shapes. Since the pressing process is the longest running and most expensive part of the production the question is how to optimally load the machine. – Nijinsky

Answer 4

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.

Mastic

what are examples of more complex data structures ? – Kin

Answer 5

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.

Dear

Answer 6

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

Eelgrass