A separation and compaction algorithm for the two-open dimension nesting problem using penetration-fit raster and obstruction map

Author(s)

Sato, Andre Kubagawa ; Mundim, Leandro Resende ; Martins, Thiago Castro ; Tsuzuki, Marcos Sales Guerra

• Document type: Journal article
• Source: EXPERT SYSTEMS WITH APPLICATIONS; v. 220, p. 16-pg., 2023-02-24.

Abstract

Nesting Problems, which are important subjects in the cutting and packing field, involve convex and nonconvex polygons and are common in several industries. These irregular open dimensional problems have been studied for decades, particularly the variant with one open dimension. However, in real-world applications, situations that are better suited to a two open dimensional model may arise and, in this sense, the literature is very limited. We here propose new separation and compaction algorithms for two-open dimension nesting problem. The paper develops an adaptation of the no-fit polygon to consider the penetration depth of pieces. The approach is based on an iterative compaction scheme, in which the key step is an obstruction map-based separation algorithm. The algorithms proposed found optimal solutions for artificial instances with up to 28 items within a small runtime. The results of benchmark instances indicate that the new algorithm is competitive when compared with other literature algorithms. It improved 14 of 15 benchmark instances when considering literature approaches on two open dimensions. In addition, the new algorithm achieved better occupation for some open dimension instances than the state of the art. (AU)

• FAPESP's process: 10/18913-4 - Study about no-fit polygons translations to create degenerated collision free regions through non regularized Boolean operations
• Grantee: Marcos de Sales Guerra Tsuzuki
• Support Opportunities: Regular Research Grants
• 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
• FAPESP's process: 13/26532-9 - Massive parallel algorithm development with GPGPU to create discrete obstructive region mountain
• Grantee: Marcos de Sales Guerra Tsuzuki
• Support Opportunities: Regular Research Grants