A biased random key genetic algorithm for open dimension nesting problems using no-fit raster

作者：Mundim Leandro R^*; Andretta Marina; de Queiroz Thiago Alves

来源：Expert Systems with Applications, 2017, 81: 358-371.

DOI：10.1016/j.eswa.2017.03.059

• Nesting problems
• Open dimension problems
• No-fit raster
• Bottom-left
• Biased random key genetic algorithm

We consider two NP-hard open dimension nesting problems for which a set of items has to be packed without overlapping into a two-dimensional bin in order to minimize one or both dimensions of this bin. These problems are faced by real-life applications, such as textile, footwear and automotive industries. Therefore, there is a need for specialized systems to help in a decision making process. Bearing this in mind, we derive new concepts as the no-fit raster, which can be used to check overlapping between any two-dimensional generic-shaped items. We also use a biased random key genetic algorithm to determine the sequence in which items are packed. Once the sequence of items is determined, we propose two heuristics based on bottom-left moves and the no-fit raster concept, which are in turn used to arrange these items into the given bin observing the objective criteria. As far as we know, the problem with two open dimensions is being solved for the first time in the context of nesting problems and we present the first whole quadratic model for this problem. Computational experiments conducted on benchmark instances from the literature (some from the textile industry and others including circles, convex, and non-convex polygons) show the competitiveness of the approaches developed as they were able to calculate the best results for 74.14% of the instances. It can be observed that these results show new directions in terms of solving nesting problems whereby approaches can be coupled in existing intelligent systems to support decision makers in this field.

• 出版日期2017-9-15