Heurísticas para o Problema do Empacotamento Colorido

Vol 54, 2022 - 151395
Trabalho completo (oral)
Favoritar este trabalho
Como citar esse trabalho?
Resumo

O Problema do Empacotamento Colorido (CBPP) consiste em empacotar um conjunto de itens, cada um com tamanho e uma cor, em recipientes de capacidade limitada, de modo a minimizar a quantidade de recipientes utilizados e a satisfazer a restrição que dois itens de mesma cor não podem ser empacotados em sequência em um mesmo recipiente. Em um estudo preliminar, propomos para o CBPP algumas heurísticas e uma abordagem meta-heurística baseada na Variable Neighborhood Search (VNS). Já neste artigo, trazemos alguns detalhes de implementação dos algoritmos apresentados na versão preliminar, e também propormos uma abordagem math-heurística que mescla programação linear e as meta-heurísticas VNS e Greedy Randomized Adaptive Search (GRASP). Os resultados computacionais indicam que a nossa math-heurística é superior à VNS, e que ambas as abordagens conseguem encontrar boas soluções mesmo para instâncias do problema com grande quantidade de itens.

Compartilhe suas ideias ou dúvidas com os autores!

Sabia que o maior estímulo no desenvolvimento científico e cultural é a curiosidade? Deixe seus questionamentos ou sugestões para o autor!

Faça login para interagir

Tem uma dúvida ou sugestão? Compartilhe seu feedback com os autores!

Instituições
  • 1 Universidade Estadual de Campinas
Eixo Temático
  • 14 - OC – Otimização Combinatória
Palavras-chave
Corte e empacotamento
meta-heurística
Math-heurística