Raster solution for the irregular nesting problem using the Voronoi Mountain.

Author(s)

André Kubagawa Sato

• Document type: Doctoral Thesis
• Press: São Paulo.
• Institution: Universidade de São Paulo (USP). Escola Politécnica (EP/BC)
• Defense date: 2015-08-14

Examining board members

Marcos de Sales Guerra Tsuzuki; Silvio Alexandre de Araujo; António Miguel da Fonseca Fernandes Gomes; Plácido Rogerio Pinheiro; Thiago Alves de Queiroz

• Advisor: Marcos de Sales Guerra Tsuzuki; Thiago de Castro Martins

Abstract

Irregular nesting belongs to the area of cutting and packing problems and are employed in the textile, wood and shipbuilding industries. The problem consists in determining a configuration for a set of irregular items which minimizes the length of the rectangular container in which the layout is located. The solution must be feasible, i.e., items must not overlap nor protrude the container walls. Due to practical reasons, up to four orientations are allowed for an item. The volume of wasted material is directly affected by the quality (density) of the layout. Thus, an efficient solution produces a positive economic and environmental impact. In this work, the objective is to automatically obtain layouts such that their density and the performance of the algorithm are competitive with other solutions in literature. So as to achieve this goal, two approaches are proposed. The first method uses a special sequential placement heuristic such that the algorithm maximizes exact placements, which consist of constrained positions for items. In general terms, a search is performed in the placement sequence in order to obtain a compact layout. In the second approach, which is the main subject of this work, raster methods are employed to guide the translation of items, which are free to move within the layout, and may overlap other items. The method is based on overlap minimization techniques, in which the objective is to eliminate the overlap in a fixed dimensions container. Both algorithms were tested using benchmark problems from the literature. The first strategy yielded unsatisfactory results, though it provided important information about the properties of exactly fitting placements. On the other hand, the main approach was able to produce competitive solutions. The performance was also compatible with other solutions, even in cases which the data volume was high. Moreover, as a future work, an extension for the algorithm can be developed such that items with generic geometry can be considered, which would be an important advance in research terms. (AU)

• FAPESP's process: 10/19646-0 - Translating No-Fit Polygons to Create Degenerated Collision Free Region Using Non-Regulerized Boolean Operations
• Grantee: André Kubagawa Sato
• Support Opportunities: Scholarships in Brazil - Doctorate