Algoritmos e modelos para problemas de corte e empacotamento

• Processo: 18/19217-3
• Modalidade de apoio: Bolsas no Exterior - Estágio de Pesquisa - Doutorado Direto
• Data de Início da vigência: 09 de fevereiro de 2019
• Data de Término da vigência: 08 de agosto de 2019
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Flávio Keidi Miyazawa
• Beneficiário: Vinícius Loti de Lima
• Supervisor: Manuel Iori
• Instituição Sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Instituição Anfitriã: Università degli Studi di Modena e Reggio Emilia, Modena (UNIMORE), Itália
• Vinculado à bolsa: 17/11831-1 - Algoritmos e modelos para problemas de corte e empacotamento, BP.DD
• Assunto(s): Problemas de corte e empacotamento Problemas de corte bidimensional Otimização combinatória Funções ortogonais
• Palavra(s)-Chave do Pesquisador: Cutting Problems | Orthogonal | Packing Problems | Three-dimensional | Two-dimensional | Otimização Combinatória

Resumo

Problemas de corte e empacotamento são frequentemente considerados como aplicações no mundo real. Ambas classes de problemas podem ser consideradas teoreticamente equivalentes, sendo que cortar um item de um recipiente pode ser equivalente a posicionar um item em um recipiente. Nesse projeto, nós consideramos problemas de empacotamento ortogonal, principalmente em suas versões bidimensionais e tridimensionais. Esses problemas consideram o posicionamento de hiper-retângulos chamados de items em hiper-retângulos maiores chamados de recipientes. Muitos dos problemas de empacotamento apresentados na literatura podem ser resolvidos por algoritmos que dependem de um problema de decisão, que determina a existência de um empacotamento de items factíveis dentro de um recipiente. Esse problema de decisão, chamado de orthogonal packing problem, é um problema NP-completo que vem sido estudado extensivamente na literatura. Ao melhor de nossos conhecimentos, a última survey em problemas de empacotamento bidimensional foi proposta a mais de uma década atrás. Desde então, a literatura mudou muito, no que diz respeito aos problemas de empacotamento bidimensional. Portanto, um dos objetivos deste projeto é propor um extenso estudo sobre problemas de empacotamento bidimensional, com o objetivo de escrever uma pesquisa abordando esses problemas. A partir deste extenso estudo, pretendemos também propor algoritmos e modelos eficientes para problemas de empacotamento bidimensionais e tridimensionais, principalmente para o orthogonal packing problem, com a motivação de que ele possa ser usado como uma sub-rotina para resolver outros problemas. Pretendemos fazer um extenso estudo computacional dos métodos propostos, para analisar sua eficiência, visando melhorar os resultados dos métodos propostos na literatura. (AU)

Publicações científicas

(Referências obtidas automaticamente do Web of Science e do SciELO, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores)

IORI, MANUEL; DE LIMA, VINICIUS L.; MARTELLO, SILVANO; MIYAZAWA, FLAVIO K.; MONACI, MICHELE. Exact solution techniques for two-dimensional cutting and packing. European Journal of Operational Research, v. 289, n. 2, p. 399-415, MAR 1 2021. (18/19217-3, 15/11937-9, 19/12728-5, 16/01860-1, 16/23552-7)