Um algoritmo de Branch-and-Cut para o Problema do Empacotamento Bidimensional em Contêineres na Presença de Conflitos

Resumo

Nesse artigo apresentamos o Problema do Empacotamento Bidimensional em Contêineres na Presença de Conflitos, que consiste em alocar um conjunto de itens de tamanhos variados no menor número possível de recipientes idênticos, respeitando as restrições de conflito entre os itens. Apresentamos um algoritmo de Branch-and-Cut que utiliza um modelo em Programação Linear Inteira. Também apresentamos diversos fortalecimentos do modelo e quebras de simetrias.

Além disso, para resolver o problema de decidir se um conjunto de itens pode ser empacotado em um contêiner utilizamos um modelo de Programação por Restrição com melhorias adaptadas da literatura. Testes computacionais foram realizados em instâncias adaptadas da literatura e os resultados foram muito significativos. As melhorias implementadas reduziram o tempo de execução de algumas instâncias de 3600 segundos para 0,02 segundos.