Algoritmo Genético para o Problema de Empacotamento 2D Clássico

O problema de empacotamento consiste em empacotar ortogonalmente um conjunto de itens na menor quantidade de caixas possível sem sobreposição. O caso bidimensional generaliza o problema de empacotamento unidimensional clássico amplamente difundido na literatura, portanto, é da classe NP-Difícil. Este trabalho apresenta um algoritmo genético de chaves aleatórias viciadas (BRKGA) para o problema de empacotamento bidimensional, considerando que os itens podem ser alocados com rotação ou orientação fixa. O problema tem várias aplicações industriais, relacionando-se a outros problemas complexos. O algoritmo proposto usa uma estratégia chamada Variable Cross Descent (VCD), que acelera o processo evolutivo do BRKGA. O resultado computacional realizado com 500 instâncias da literatura demonstram que o método proposto, denominado BRKGA/VCD, é capaz de obter soluções de qualidade superior ou equivalente aos algoritmos estado da arte encontrados na literatura.