Chapter 1
Introduction
The main subject of this thesis is the so-called nesting problem, which (in short) is the problem
of packing arbitrary two-dimensional shapes within the boundaries of some container. The
objective can vary e.g. minimizing the size of a rectangular container or maximizing the number
of shapes in the container, but the core problem is to pack the shapes tightly without any
overlap. An example of a tight packing is shown in Figure 1.1.
A substantial amount of literature has been written about this problem, where most of it has
been written within the past decade. A survey of the existing literature is given in Chapter 2
along a detailed description of different problem types and various geometric approaches to
these problems. At the end of the chapter a three-dimensional variant of the problem is
described and the more limited amount of literature in this area is also discussed.
The rest of the thesis is focused on solving the nesting problem with a meta heuristic
method called Guided Local Search (GLS). It is a continuation of the work presented in a
written report (in Danish) by Jens Egeblad and ourselves [28], which again is a continuation
of the work presented in an article by Færø et al. [32]. Throughout this thesis we will often
refer to the work done by Jens Egeblad and ourselves (Egeblad et al. [28]).
Chapter 3 presents GLS and some other issues regarding the basics of our solution method.
Most importantly the neighborhood for the local search is presented — it is a fast search of
this neighborhood which is the major strength of our approach to the nesting problem.
Færø et al. successfully applied the GLS meta heuristic to the rectangular bin packing
problem in both two and three dimensions. The speed of their approach was especially due to
a simple and very fast translation algorithm which could find the optimal (minimum overlap)
axis-aligned placement of a given box. Egeblad et al. [28] realized that a similar algorithm was
possible for translating arbitrary polygons. However, they did not prove the correctness of the
algorithm.
A major part of this thesis (Chapter 4) is dedicated to such a proof. The proof is stated
in general terms and translation and polygons are introduced at a very late stage. By doing
this it is simultaneously shown that the algorithm could be useful for other transformations
or other shapes. At the end of the chapter some additional work is done to adapt the general
scheme to an algorithm for rotation of polygons.
Although not explicitly proven it is easy to see that the fast translation and rotation
algorithms are also possible for three dimensions. A description of how to do this in practice
for translation is given separately in Chapter 6.
The two-dimensional nesting problem appears in a range of different industries and quite
5
