Heuristics for Multidimensional Packing Problems

In this thesis we consider solution methods for packing problems. Packing problems occur in many
different situations both directly in the industry and as sub-problems of other problems. High-quality
solutions for problems in the industrial sector may be able to reduce transportation and production
costs significantly. For packing problems in general are given a set of items and one of more containers.
The items must be placed within the container such that some objective is optimized and the items
do not overlap. Items and container may be rectangular or irregular (e.g. polygons and polyhedra)
and may be defined in any number of dimensions. Solution methods are based on theory from both
computational geometry and operations research.
The scientific contributions of this thesis are presented in the form of six papers and a section
which introduces the many problem types and recent solution methods. Two important problem variants
are the knapsack packing problem and the strip-packing problem. In the knapsack packing problem,
each item is given a profit value, and the problem asks for the subset with maximal profit that
can be placed within one container. The strip-packing problem asks for a minimum height container
required for the items. The main contributions of the thesis are three new heuristics for strip-packing
and knapsack packing problems where items are both rectangular and irregular.
In the two first papers we describe a heuristic for the multidimensional strip-packing problem that
is based on a relaxed placement principle. The heuristic starts with a random overlapping placement of
items and large container dimensions. From the overlapping placement overlap is reduced iteratively
until a non-overlapping placement is found and a new problem is solved with a smaller container size.
This is repeated until a time-limit is reached, and the smallest container for which a non-overlapping
placement was found is returned as solution. In each iteration, a single item is translated parallel to
one of the coordinate axes to the position that reduces the overlap the most. Experimental results
of this heuristic are among the best published in the literature both for two- and three-dimensional
strip-packing problems for irregular shapes.
In the third paper, we introduce a heuristic for two- and three-dimensional rectangular knapsack
packing problems. The two-dimensional heuristic uses the sequence pair representation and a novel
representation called sequence triple is introduced for the three-dimensional variant. Experiments for
the two-dimensional knapsack packing problem are on-par with the best published in the literature
and experiments for the three-dimensional variant are promising.
A heuristic for a three-dimensional knapsack packing problem involving furniture is presented in
the fourth paper. The heuristic is based on a variety of techniques including tree-search, wall-building,
and sequential placement. The solution process includes considerations regarding stability and load
bearing strength of items. The heuristic was developed in collaboration with an industrial partner and
is now being used to solve hundreds of problems every day as part of their planning process.
A simple heuristic for optimizing a placement of items with respect to balance and moment of inertia
is presented in the fifth paper. Ensuring that a loaded consignment of items are balanced throughout
a container can reduce fuel consumption and prolong the life-span of vehicles. The heuristic can be
used as a post-processing tool to reorganize an existing solution to a packing problem.
A method for optimizing the placement of cylinders with spherical ends is presented in the last
paper. The method can consider proximity constraints which can be used to describe how cylinders
should be placed relative to each other. The method is applied to problems where a placement of
capsules must be found within a minimal spherical or box-shaped container and to problems where
a placement within a given arbitrarily container must be found. The method has applications for
prediction of RNA tertiary structure.