How can I programmatically determine how to fit smaller boxes into a larger package?

This is a Bin Packing problem, and it's NP-hard. For small number of objects and packages, you might be able to simply use the brute force method of trying every possibility. Beyond that, you'll need to use a heuristic of some sort. The Wikipedia article has some details, along with references to papers you probably want to check out.

The alternative, of course, is to start with a really simple algorithm (such as simply 'stacking' items) and calculate a reasonable upper-bound on shipping using that, then if your human packers can do better, you make a slight profit. Or discount your calculated prices slightly on the assumption that your packing is not ideal.


The literature on "3D Bin packing" is far and wide. You can get a good overview by tracking the publications of Professor David Pisinger. He also published one of the few high quality implementations of bin packing with sourcecode: 3dbpp.c

My own logistics toolkit pyShipping comes with a 3D Bin Packing implementation for Warehousing applications. It is basically implementing 4D Bin Packing (3D size & weigth) and gets an acceptable solution for typical order sizes (a few dozens of packages) in under a second runtime. It is used in production (meaning a warehouse) for some months now to determine the upper bound of shipping crates to be used. The warehouse workers are often able to pack somewhat more efficiently but that's OK with me.


Pisinger is one of the few academics who posts working code. In one of his papers he mentions the "Minimum Depth" problem.

Here is a practical and efficient algorithm for 3D Rectangular Box Packing that adjusts the height of the enclosing box.

And here is an implementation in php.