Heurísticas especializadas aplicadas ao problema de carregamento de contêiner

Abstract

O problema de carregamento de contêiner consiste em carregar um número conhecido de caixas de tipos diferentes e dimensões conhecidas dentro de um contêiner, de modo a utilizar o espaco do contêiner da melhor maneira possível, ou seja, de modo a diminuir os espacos não ocupados. O problema de carregamento de contêiner e um problema NP-difícil e, portanto, muito complexo de ser resolvido de forma exata usando um modelo matemático de programacao inteira e pacotes comerciais de otimizacao baseados em técnicas tipo branch and bound. Neste trabalho e realizada a elaboracao, assim como a implementacao computacional, de dois algoritmos de otimizacao. A primeira proposta de otimizacao consiste de um algoritmo heurístico construtivo. A segunda proposta de otimizacao um algoritmo GRASP que usa, na fase construtiva, uma generalizacao do algoritmo heurístico construtivo desenvolvido neste trabalho. A metaheurística GRASP desenvolvida neste trabalho apresentou resultados promissores quando foram realizados testes usando 13 instâncias conhecidas na literatura especializada

The container loading problem is to load a known number boxes of different dimensions and known within a container, in order to use the space of the container the best way possible, ie, in order to reduce the empty spaces. The problem of container loading is NP-hard and therefore too complex to be solved using an exact mathematical model integer programming and commercial packages based on optimization techniques branch and bound type. In this work the preparation, as well as the computational implementation of two optimization algorithms. The first proposal consists of an optimization constructive heuristic algorithm. The second proposal is an optimization GRASP that uses in construction phase, a generalization of the algorithm constructive heuristic developed in this work. The GRASP developed in this work showed promising results when tests were performed using 13 known instances in the literature specialized