A random-key genetic algorithm for solving the nesting problem

作者：Pinheiro Placido R^*; Amaro Junior Bonfim; Saraiva Rommel D

来源：International Journal of Computer Integrated Manufacturing, 2016, 29(11): 1159-1165.

DOI：10.1080/0951192X.2015.1036522

• cutting and packing
• nesting problem
• irregular packing
• genetic algorithm
• random keys

This article presents a random-key genetic algorithm (RKGA) for the nesting problem, a particular case of cutting and packing problems in which a collection of items (or polygons) has to be packed onto a rectangular object with the aim of minimising its length. In general, our approach prescribes the integration of the aforementioned metaheuristic and well-known placement rules (e.g. bottom-left). Furthermore, a shrinking algorithm - that operates within the RKGA - is also proposed to improve partial solutions. To assess the potentials of the proposed methodology, computational experiments performed on a set of difficult benchmark instances of the nesting problem are discussed here for evaluation purposes, showing that our algorithm is able to compete with previous successful studies in some particular problem instances.

• 出版日期2016