An innovative data structure to handle the geometry of nesting problems

Author(s)

Cherri, Luiz Henrique ^[1] ; Cherri, Adriana Cristina ^[2] ; Carravilla, Maria Antonia ^[3] ; Oliveira, Jose Fernando ^[3] ; Bragion Toledo, Franklina Maria ^[1] ; Goncalves Vianna, Andrea Carla ^[2]

Affiliation

^[1] Univ Sao Paulo, Inst Ciencias Matemat & Comp, Sao Carlos, SP - Brazil

^[2] Univ Estadual Paulista, UNESP, Fac Ciencias, Bauru - Brazil

^[3] Univ Porto, INESC TEC, Fac Engn, Porto - Portugal

• Document type: Journal article
• Source: INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH; v. 56, n. 23, p. 7085-7102, 2018.
• Web of Science Citations: 1

Abstract

As in many other combinatorial optimisation problems, research on nesting problems (aka irregular packing problems) has evolved around the dichotomy between continuous (time consuming) and discrete (memory consuming) representations of the solution space. Recent research has been devoting increasing attention to discrete representations for the geometric layer of nesting problems, namely in mathematical programming-based approaches. These approaches employ conventional regular meshes, and an increase in their precision has a high computational cost. In this paper, we propose a data structure to represent non-regular meshes, based on the geometry of each piece. It supports non-regular discrete geometric representations of the shapes, and by means of the proposed data structure, the discretisation can be easily adapted to the instances, thus overcoming the precision loss associated with discrete representations and consequently allowing for a more efficient implementation of search methods for the nesting problem. Experiments are conducted with the dotted-board model - a recently published mesh-based binary programming model for nesting problems. In the light of both the scale of the instances, which are now solvable, and the quality of the solutions obtained, the results are very promising. (AU)

• FAPESP's process: 10/10133-0 - Cutting, packing, lot-sizing and scheduling problems and their integration in industrial and logistics settings
• Grantee: Reinaldo Morabito Neto
• Support Opportunities: Research Projects - Thematic Grants
• FAPESP's process: 12/18653-8 - Nesting problem
• Grantee: Luiz Henrique Cherri
• Support Opportunities: Scholarships in Brazil - Doctorate
• FAPESP's process: 14/10740-4 - Nesting Problem
• Grantee: Luiz Henrique Cherri
• Support Opportunities: Scholarships abroad - Research Internship - Doctorate