Resolução do problema do empacotamento tridimensional utilizando o algoritmo de otimização da colônia de formigas e o método de geração de colunas

Abstract

O presente trabalho tem como objetivo apresentar um método de solução para o Problema do Empacotamento Tridimensional com rotação. Este problema apresenta uma aplicação prática no carregamento de contêineres, caminhões, depósitos e no corte de estoque tridimensional não guilhotinado. Por se tratar de um problema NP-Hard, muitas vezes não é possível encontrar sua solução ótima em tempo razoável. A resolução proposta é a utilização do Algoritmo de Otimização da Colônia de Formigas combinado com o Método de Geração de Colunas para a resolução do problema. Testes com instâncias da literatura demonstram que esta meta-heurística possui potencial para resolver o problema com eficiência e eficácia.

This study aims to present solution method for Tridimensional Bin Packing Problem with rotation. This problem has a practical application in containers, truck and deposits loading and non-guillotined cutting-stock problems. In fact of problem been a NP-Hard, in many cases are not possible find the optimal solution in reasonable time. The proposal solution is the utilization of Ant Colony Optimization Algorithm combined with Column Generation Method to solve this problem. Tests with instances from the literature demonstrate that this metaheuristic has the potencial to solve the problem efficiently and effectively.