![[benzedrine.ch logo]](/logo.jpg){kind=logo} |
|
|
|
A novel packing heuristic based on rigid body simulationThe 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 three-dimensional rectangular
open dimension problem (ODP) with three variable dimensions.
Such problems are
NP-complete,
and N=100 is a non-trivial size.
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.
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 box-shaped
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![[rendering of an early result]](vistaprint/N100-small.jpg)
![[rendering of a later result]](vistaprint/N100-small2.jpg) 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: webgl-58, webgl-67, and webgl-92. 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.50A 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.3712948Running 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
BuildingThis program depends on the open source library Open Dynamics Engine (ODE) which is available under a BSD-style license, see http://www.ode.org/ode-license.html http://ode-wiki.org/wiki/index.php?title=Manual:_Introduction Download the ODE source tarball from http://downloads.sourceforge.net/project/opende/ODE/0.13/ode-0.13.tar.bz2 MD5 (ode-0.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 ode-0.13.tar.bz2 $ ls CONTACT.txt README.txt ode-0.13.tar.bz2 Makefile ode-0.13 solve.cpp $ cd ode-0.13 $ ./configure --disable-asserts --disable-threading-intf --disable-demos $ make $ cd .. $ make On Linux you might have to install arc4random (tested on Ubuntu 12.04.3) apt-get install libbsd-dev add #include <bsd/stdlib.h> to solve.cpp add -lbsd to LDFLAGS in Makefile
Discussion
Academic papers
Prior art
|