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

Autor(es)

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

• Tipo de documento: Artigo Científico
• Fonte: EXPERT SYSTEMS WITH APPLICATIONS; v. 220, p. 16-pg., 2023-02-24.

Resumo

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)

• Processo FAPESP: 10/18913-4 - Estudo sobre translações aplicadas a polígonos de obstrução para que operações booleanas não regularizadas criem regiões de obstrução degeneradas
• Beneficiário: Marcos de Sales Guerra Tsuzuki
• Modalidade de apoio: Auxílio à Pesquisa - Regular
• Processo FAPESP: 10/19646-0 - Translações Aplicadas a Polígonos de Obstrução para que Regiões Livres de Colisão Degeneradas Sejam Criadas por Operações Booleanas Não Regularizadas
• Beneficiário: André Kubagawa Sato
• Modalidade de apoio: Bolsas no Brasil - Doutorado
• Processo FAPESP: 13/26532-9 - Desenvolvimento de algoritmo massivamente paralelo com GPGPU para criar a região obstrutiva montanhosa discreta
• Beneficiário: Marcos de Sales Guerra Tsuzuki
• Modalidade de apoio: Auxílio à Pesquisa - Regular