A Heuristic Approach for Nesting of 2D Shapes

In several manufacturing processes, the cutting of 2D parts from sheets is an important task. The arrangement of the parts in the sheets, supported by computers, is called nesting and is addressed to minimize the wasted material. In literature some approaches are proposed, based on genetic or heuristic algorithms which emphasize different characteristics, e. g. the time complexity or the wasted material. In shipbuilding the parts to be arranged have significantly different sizes, which are often difficult to pack in a fast way using the standard methods in literature. In this work an approach is proposed, able to arrange parts with very different dimensions, which is based on the identification of a suitable starting rotation that ensures a solution in a reasonable time. The main steps are: a) importation of the model files of the parts to be packed, b) identification of a preliminary orientation and sorting of the parts (starting position), c) optimization of the position of the parts, ensuring a minimum distance between them. For the starting rotation, three different orientations are considered: i) the original orientation, ii) the x axis coincident with the minimum inertia axis, iii) the x axis aligned with the maximum edge. The orientation is selected in order to obtain the minimum area of the bounding box. The implementaiton of the method has been investigated and the results show the advantages of the approach: reduction of waste material and time for performing the nesting.