On the Use of Human-Guided Evolutionary Algorithms for Tackling 2D Packing Problems - Foundations on Natural and Artificial Computation - page 353

On the Use of Human-Guided Evolutionary
Algorithms for Tackling 2D Packing Problems

Javier Espinar, Carlos Cotta, and Antonio J. Fernandez Leiva

Dept. Lenguajes y Ciencias de la Computacion, ETSI Informatica,
Campus de Teatinos, Universidad de Malaga,
29071 Malaga - Spain
{ ccottap,afdez } @lcc.uma.es

Abstract. We consider a 2D packing problem in which a collection of
rectangular objects have to be arranged within a larger rectangular area
of fixed width, such that its height is minimized. This problem is tackled
using evolutionary algorithms that combine permutational decoders and
GRASP-based principles. It is shown that this approach can be improved
by allowing the user interact with the algorithm, tuning the greediness
of the genotype-to-phenotype decoding. Experiments are presented on
three different problem instances with sizes ranging from 19 up to 49
objects.

1 Introduction

Cutting and packing (C&P) problems are common in many industrial applica-
tions. Albeit under different formulations, this kind of problems share the need
of finding a dense arrangement of a collection of objects, in order to minimize
the material needed for producing them or the cost of wrapping and shipping
them, just to cite a couple of examples [1]. Problems in this area range from 1D
C&P (e.g., cutting large wooden boards into shorter pieces) to 3D C&P (e.g.,
container loading), including mixed versions thereof. We specifically consider 2D
C&P problems in this work, and more precisely the case in which objects have
rectangular shape. Such problems naturally arise in manufacturing processes of
wood, glass and paper industries [2].
In general problems in this area cannot be eciently solved with complete
algorithms (in fact, note that several classical problems such as the knapsack
problem or vector packing [3] can be formulated as C&P problems, and hence
they are in general NP-hard). For this reason, heuristic and metaheuristics have
been often used to solve this kind of problems - see [4] for a review. In this sense,
it is well-known that in order to attain effective (meta)heuristic solvers, problem
knowledge must be exploited [5,6]. Optimization tools can be endowed of this
problem-knowledge in many ways: ad hoc representations, specialized operators,
or combination with other problem-specific techniques, just to cite a few [7]. We
present an algorithmic approach that incorporates some commonly-used heuris-
tic in the area, driven by GRASP-like procedure [8]. Our main focus is however