Uma Heurística Iterativa Baseada em Perturbação e Busca Local para o Variable Sized Bin-Packing Problem

O Variable Sized Bin-Packing Problem (VSBPP) é um problema de otimização combinatória NP-difícil que consiste em alocar itens em bins (caixas), minimizando o custo total de empacotamento. Os itens são caracterizados por seus pesos, enquanto os bins, por suas capacidades e custos. Este trabalho propõe uma heurística iterativa baseada em perturbação da ordem dos itens e busca local em múltiplas vizinhanças, incluindo redução de tipos de bins, união de bins e refinamento de pares adjacentes. Os experimentos foram realizados em 199 instâncias da literatura, utilizando como referência os resultados do estado da arte. Os resultados demonstram que a abordagem é promissora, visto que foram encontradas sete novas soluções melhores, com destaque para as instâncias de custo convexo, nas quais o algoritmo igualou ou superou o estado da arte em todas as instâncias testadas.