Finding the optimal 3D box sizes for a group of 3D rectangular items

Question

When I say box I am talking about shipping boxes.

I have a number of random sized, small items that I need to pack into as few boxes as possible. I need to know what box sizes are optimal.

• All items are rectangular prisms.
• It's easy to exclude a box size for an item which is too large to fit.
• I know the box sizes (they are the available box sizes which I have in-stock)
• Items can be positioned horizontally or vertically, not diagonal.
• As many boxes as required can be used. The goal is to use as few boxes as possible.
• Multiple box sizes may be used to optimally fit the varying-sized items.

What algorithm exists that allows me to calculate the box sizes I need to use for optimal space usage? To fit the most items into as few boxes as possible.

The available box sizes come from what I have available, in-stock. You can create a finite number of made up box sizes for example purposes.

Answer 1

This is a generalization of the Bin packing problem, meaning it is NP-Hard.

To see this, imagine all bins and packages have the same width and height, and additionally all bins (but not packages) have the same length. Then it is a one-dimensional problem: we have bins of size V, and packages of size a₁, a₂, ..., a_n. This simplified case is exactly the Bin-packing problem. Thus, a fast solution to your problem gives us a fast solution to bin-packing, so your problem is at least as hard; and since bin-packing is NP-Hard, so is your problem.

---

There are some approximation algorithms available though; for example, it's easy to show that the simple first-fit algorithm (put every item in the first bin that it fits into) will never do worse than 2x the optimal solution.

The similar "First Fit Decreasing" algorithm (sort the items in descending order, then put every item in the first bin it fits into) is even better, guaranteeing to be within about 25% of the optimal solution. There is also another, slightly more complicated algorithm called MFFD which guarantees to be within about 20%.

And of course, with only 7 boxes, you could always just brute-force the solution. This will require about 7ⁿ steps (where n is the number of items), so this solution is infeasible with more than a dozen or so items.