

A novel packing heuristic based on rigid body simulation
The
Vistaprint Tech Challenge 2014
(archived details)
asked:
Given a collection of Vistaprint products, what is the smallest
shipping box that can contain them? And how should they be packed
into that box?
This is a
packing problem.
According to the typology it is a threedimensional rectangular
open dimension problem (ODP) with three variable dimensions.
Notably, it allows arbitrary, nonorthogonal rotations,
and the target is low surface area.
Such problems are
NPcomplete,
and N=100 is a nontrivial size.
Hence, guaranteed optimal solutions are out of reach, instead a good
heuristic
is sought.
Specifically, it should be fast enough to be
run "tens of thousands of times every day", i.e. running time should
be less than one second.
In a novel approach, a heuristic algorithm based on solid body dynamics
was written in ~350 lines of C++ using the
Open Dynamics Engine
(ODE) library.
Interestingly, the implementation is
embarrasingly parallel,
and the quality of the result increases with parallel runs
(Monte Carlo method).
Submitted October 13th 2014, results announced
(archive) December 3rd 2014.
Congratulations to Lars Szuwalski!
Description
Imagine that you are holding in your hands a special shipping box, one
that you can resize and rotate at will. You start with a large box and
randomly place all products into it. You rotate it so one corner points
towards the floor. The products will fall into this corner and form a
loose pile.
When they have stopped moving, you shrink the box as much as possible,
so each side touches the pile of products. Then you rotate the box so
another corner faces downwards.
You keep repeating these three steps (rotate, wait, and shrink) while
the box shrinks around ever tighter piles. At the end, you simply
measure the products' positions within the box.
This program simulates the entire process using rigid body dynamics:
 instead of rotating the shipping box, the gravity vector is changed
 the shipping box is always placed in the corner of the first octant,
the three planes x==0, y==0, and z==0 form three sides of the
shipping box and they never move
 the other three sides of the box are planes x==C1, y==C2, z==C3,
where the constants are found by determining the maximum x, y, and z
coordinates among all products' corners
 the shipping box never moves or rotates, only three sides of it are
moved: tighter (closer to the origin) or looser (further away)
 products are represented by a combination of bodies and geoms:
bodies are points with mass and geoms have shape (used for collision
detection), both share a position (the center of the boxshaped
geom)
 initial placement of the products is random
 products are considered lying still when the bounding box of their
most outward coordinates does not change for some time
 global coordinates of products' corners are determined by first
calculating their positions relative to the geom (using length,
width, and height) and then transforming relative to global
coordinates
 when geoms collide, a temporary joint is added between them which
resolves penetration, causing the geoms to bounce off each other
and off the walls
 the simulation goes through two phases: first the shrinking of the
shipping box with low temporal resolution and high mass (higher
speed, but allows more penetration), second a slight loosening of
the shipping box with high temporal resolution and low mass (until
all penetration is resolved)
 the shrinking phase ends when shrinking fails for some time
 the shrinking phase can be repeated (with new random placement of
products) and the program keeps track of the shipping box with the
minimal surface area seen so far
 the loosening phase is only done once, at the end, for this minimum
Results
Solutions found for random N=100 input #58;
left after 200 iterations with surface 100767 (+20.82%),
right after 10000 iterations with surface 98117 (+17.64%).
You can paste your own input files and watch them get
solved online within seconds (eight nodes with eight parallel processes each, not always available).
If you have a
WebGL
enabled browser, you can view three interactive examples:
webgl58,
webgl67, and
webgl92.
Rotate, pan, and zoom by dragging the mouse while pressing mouse buttons.
Running the program with 20 iterations on a set of 100 randomly generated
input files,
the following
results
are observed:
# N lower_bound surface percent
1 21 37782.40 45677.10 20.90
2 55 53923.93 66931.08 24.12
3 45 45721.45 56909.28 24.47
4 74 68462.11 84810.88 23.88
5 97 83046.84 101588.70 22.33
6 88 73128.25 90770.97 24.13
7 4 11040.81 13281.28 20.29
...
99 48 42622.16 54123.19 26.98
100 97 84242.29 103193.38 22.50
A simple lower bound is based on the sum of volumes of inputs;
in a perfect case, the output would be a cube with exactly the same volume.
The fifth column is defined as
(surface  lower_bound) * 100.0 / lower_bound,
i.e. how much larger, in percent, the output surface is than the lower bound.
$ ministat C 5 results.txt
x results.txt
++
 x 
 x 
 x 
 x 
 x 
 xx 
 xx 
 xx 
 xxxx 
 xxxx 
 xxxxx 
 xxxxx 
 xxxxx 
 xxxxx 
 xxxxxx x 
 xxxxxxxx 
 xxxxxxxxx 
 xxxxxxxxx 
 x xxxxxxxxxx 
x xxxxxxxxxxxxxx x x
 _____MA_____ 
++
N Min Max Median Avg Stddev
x 100 0.09 76.05 23.88 24.3778 6.3712948
Running the program with 10000 iterations on the same set of input files
shows improved results:
$ ministat C 5 results.txt results10000.txt
x results.txt
+ results10000.txt
++
 + 
 + 
 + 
 + 
 + 
 + 
 + 
 + 
 + 
 + 
 + 
 + 
 + 
 + 
 + 
 ++ 
 ++ x 
 ++ x 
 ++ x 
 ++ x 
 ++ x 
 ++ xx 
 +++ xx 
 +++ xx 
 +++ xxxx 
 +++ xxxx 
 +++ xxxxx 
 + +++ xxxxx 
 + +++ xxxxx 
 +++++ xxxxx 
 +++++xxxxxx x 
 +++++xxxxxxxx 
 +++++xxxxxxxxx 
 +++++xxxxxxxxx 
 + + ++*++*xxxxxxxxx 
* ++ ++++++*****xxxxxxxxx x + x
 ___AM___MA_____ 
++
N Min Max Median Avg Stddev
x 100 0.09 76.05 23.88 24.3778 6.3712948
+ 100 0.09 47.32 18.43 17.87 4.0993298
Difference at 95.0% confidence
6.5078 +/ 1.48492
26.6956% +/ 6.09129%
(Student's t, pooled s = 5.35714)
Source code
Building
This program depends on the open source library Open Dynamics Engine
(ODE) which is available under a BSDstyle license, see
http://www.ode.org/odelicense.html
http://odewiki.org/wiki/index.php?title=Manual:_Introduction
Download the ODE source tarball from
http://downloads.sourceforge.net/project/opende/ODE/0.13/ode0.13.tar.bz2
MD5 (ode0.13.tar.bz2) = 04b32c9645c147e18caff7a597a19f84
and extract it in the same directory. The following steps can be used to
build (tested on Mac OS X 10.9.5, FreeBSD 8.4, and cygwin 1.7.28)
$ tar zxf ode0.13.tar.bz2
$ ls
CONTACT.txt README.txt ode0.13.tar.bz2
Makefile ode0.13 solve.cpp
$ cd ode0.13
$ ./configure disableasserts disablethreadingintf disabledemos
$ make
$ cd ..
$ make
On Linux you might have to install arc4random (tested on Ubuntu 12.04.3)
aptget install libbsddev
add #include <bsd/stdlib.h> to solve.cpp
add lbsd to LDFLAGS in Makefile
Discussion
Academic papers
 An improved typology of cutting and packing problems by Gerhard Waescher, Heike Haussner, Holger Schumann
 Heuristics for Multidimensional Packing Problems by Jens Egeblad
 Three Dimensional Bin Packing Problem with Variable Bin Height by Yong Wu, Wenkai Li, Mark Goh, Robert de Souza
 The ThreeDimensional Bin Packing Problem by Silvano Martello, David Pisinger, Daniele Vigo
 A global optimization approach for solving threedimensional open dimension rectangular packing problems by JungFa Tsaia, PeiChun Wanga & MingHua Lin
 A hybrid genetic algorithm with a new packing strategy for the threedimensional bin packing problem by Kyungdaw Kang, Ilkyeong Moon, Hongfeng Wang
 On the threedimensional bin packing using rotations by Ana Maria de Almeida and Marisa Figueiredo
 A biased random key genetic algorithm for 2D and 3D bin packing problems by Jose Fernando Goncalves, Mauricio G.C. Resende
 Decision Support Systems in Transport Logistics by A. L. Abramov, A. A. Kovtaniuk
 3D Nesting of Complex Shapes by E. Lutters, D. ten Dam, T. Faneker
Prior art
