Problema de empacotamento de retângulos: avaliação de métodos de solução baseados em bottom-left

Abstract

Problemas de empacotamento consistem em alocar um conjunto de itens I em uma caixa B. No problema de empacotamento da mochila, foco deste trabalho, cada item é associado a um valor e busca-se uma solução que maximize a soma dos valores dos itens alocados. Este trabalho compara 40 métodos de solução criados com base na heurística construtiva bottom-left para o problema de empacotamento de retângulos. A escolha dessa heurística se deve a sua simplicidade e a dificuldade de usar métodos exatos para resolução do problema em tempo hábil. Os métodos criados são uma combinação de diferentes formas de ordenação dos itens e criação de regiões, as quais evitam as sobreposições e o domínio contínuo presentes no problema. Algoritmos foram implementados em Python e testados com instâncias da literatura, dados como qualidade de solução, porcentagem de itens alocados e tempo de execução foram coletados. O principal resultado foi a alta competitividade de diferentes modos de ordenação, não sendo a área a única relevante, com o perímetro obtendo os melhores resultados.

Packing problems consist of allocating a set of items I into a box B. In the knapsack packing problem, the focus of this work, each item is associated with a value and a solution is sought that maximizes the sum of the values of the allocated items. This work compare 40 created solution methods based on bottom-left constructive heuristic for the rectangle packing problem. The choice of this heuristic is due to its simplicity and the difficulty of using exact methods to solve the problem in a timely manner. The methods created are a combination of different ways of ordering items and creating regions, which avoid superposition and continuous domain present in the problem. Algorithms were implemented in Python and tested with instances from the literature, data such as solution quality, percentage of allocated items and execution time were collected. The main result was the high competitiveness of different ordering modes, the area not being the only relevant one, with the perimeter obtaining the best results.