Definição de uma heurística para problemas de empacotamento tridimensional

Abstract

Esse trabalho de conclusão se propõem a desenvolver uma solução ao problema de empacota- mento tridimensional. Este problema é encontrado em diversas aplicações no mundo real, apre- sentando escalas consideráveis e criticidade temporal para a solução. Por exemplo, o encontramos no ramo de transporte marítimo em pelo menos duas aplicações distintas: no empacotamento de paletes dentro de contêineres e na distribuição destes contêineres nos navios cargueiros. Além disso, é computacionalmente difícil, formulando assim um problema interessante no contexto de computação como ciência. Assim, nosso trabalho irá propor e implementar uma solução heurística paralela, tomando como objetivo principal o aprimoramento do tempo de execução dos algoritmos utilizados para solução deste problema. Para isto, utilizaremos uma estratégia de dividir e conquistar para a quebra do volume disponível em espaços menores, que serão por sua vez empacotados com itens e utilizados para a composição da solução final. A heurística foi implementada em Go, utilizando ferramentas e metodologias de programação simultânea. Foi testada utilizando benchmarks estabelecidos na academia contra o próprio algoritmo de empacotamento utilizado pela heurística. Como principal resultado, atingimos uma melhora na performance de 270%, em troca de uma redução de volume utilizado de 6.5%.

This tesis proposes to develop a solution to the three-dimensional packing problem. This problem is found in several applications in the real world, presenting considerable scales and temporal criticality for the solution. For example, we find it in the maritime transport sector in at least two different applications: in the packaging of pallets inside containers and in the distribution of these containers on cargo ships. Furthermore, it is computationally difficult, thus formulating an interesting problem in the context of computer science. Thus, our work will propose and implement a parallel heuristic solution, with the main objective of improving the execution time of the algorithms used to solve this problem. For this, we will use a divide and conquer strategy to break the available volume into smaller spaces, which will in turn be packed with items and used to compose the final solution. The heuristic was implemented in Go, utilizing tools and methodologies from concurrent programming. It was tested using benchmarks established in the academia against the packing algorithm used in the heuristic itself. As the main result, we got a performance enhancement of 270%, in exchange of a 6.5% volume reduction.