Simulated Annealing aplicado ao problema de Bin Packing com Conflitos

Este trabalho aborda o Problema de Empacotamento com Conflitos, ou Bin Packing Problem with Conflicts (BPPC). Este problema é uma variante do clássico Problema de Empacotamento, do inglês Bin Packing Problem (BPP). No BPPC, uma série de itens devem ser empacotados no menor número de bins possíveis, respeitando as restrições de capacidade e lidando com itens que apresentam conflito entre si e, portanto, não podem ser alocados ao mesmo bin. O método Simulated Annealing com uma solução inicial aleatória e quatro estruturas de vizinhanças é proposto para resolver o BPPC. O algoritmo é testado em 2.160 instâncias de teste da literatura e os resultados demonstram que foram obtidas soluções de alta qualidade. O desvio relativo médio em relação as melhores soluções conhecidas foi de apenas 4,81%, e a otimalidade foi alcançada em 24,21% dos casos.