Simulated Annealing aplicado ao problema de Bin Packing com Conflitos

Abstract

Este trabalho aborda o Problema de Empacotamento com Conflitos, ou Bin Packing Problem with Conflicts (BPPC), derivado do clássico Problema de Empacotamento, do inglês Bin Packing Problem (BPP). No problema original, uma série de itens devem ser empacotados no menor número de bins possíveis, respeitando as restrições de capacidade. O BPPC possui o mesmo objetivo do BPP, porém lidando com itens que apresentam conflito entre si e, portanto, não podem ser empacotados no mesmo bin. Esta classe de problemas possui aplicações em contextos de logística, transporte, alocação de recursos, computação paralela e nas indústrias de corte e empacotamento. Devido a característica combinatorial do problema, o método Simulated Annealing e quatro estruturas de vizinhanças são propostas para resolver o BPPC. O algoritmo é testado em instâncias de teste da literatura e o seu desempenho é satisfatório, no geral. A solução ótima foi encontrada em 17,5% das instâncias totais.