An innovative data structure to handle the geometry of nesting problems
Carregando...
Arquivos
Data
Orientador
Coorientador
Pós-graduação
Curso de graduação
Título da Revista
ISSN da Revista
Título de Volume
Editor
Tipo
Artigo
Direito de acesso
Acesso aberto
Resumo
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.
Descrição
Palavras-chave
computational geometry, data structures, integer programming, irregular packing, nesting problems
Idioma
Inglês
Citação
International Journal of Production Research, p. 1-18.
