A hybrid evolutionary algorithm for the two-dimensional packing problem

作者：Kierkosz Igor^*; Luczak Maciej

来源：Central European Journal of Operations Research, 2014, 22(4): 729-753.

DOI：10.1007/s10100-013-0300-0

• Packing
• Cutting
• Evolutionary computations
• Metaheuristics

This paper presents a hybrid evolutionary algorithm for the two-dimensional non-guillotine packing problem. The problem consists of packing many rectangular pieces into a single rectangular sheet in order to maximize the total area of the pieces packed. Moreover, there is a constraint on the maximum number of times that a piece may be used in a packing pattern. The set of packing patterns is processed by an evolutionary algorithm. Three mutation operators and two types of quality functions are used in the algorithm. The best solution obtained by the evolutionary algorithm is used as the initial solution in a tree search improvement procedure. This approach is tested on a set of benchmark problems taken from the literature and compared with the results published by other authors.

• 出版日期2014-12