Meta-heurísticas para o problema de empacotamento 2D e 3D - Moraes, Anderson Zudio de (2018)
O problema de empacotamento consiste em empacotar, ortogonalmente e sem sobreposição, um conjunto de itens na menor quantidade de caixas possível. As versões bi e tridimensional do problema generalizam o caso bem conhecido unidimensional, um dos primeiros problemas da classe NP-Difícil. Esta dissertação estuda a versão clássica dos problemas de empacotamento bidimensional e tridimensional, considerando os casos com itens de orientação fixa e com rotação. O problema tem várias aplicações industriais, e o caso de orientação fixa se relaciona a outros problemas complexos como os de corte, repartição e agendamento. Várias heurísticas são propostas e combinadas com metaheurísticas para resolver instâncias de grande porte do problema com soluções de boa qualidade. Extensivos testes computacionais são realizados com 820 instâncias padrões utilizadas em vários trabalhos na literatura. Os resultados computacionais obtidos pela melhor abordagem deste trabalho, denominada BRKGA-VCD, demonstram que o método proposto obtém soluções de qualidade superior ou equivalente aos algoritmos estado da arte encontrados na literatura, melhorando o melhor resultado conhecido para este conjunto de instâncias