Técnicas de solução exata para problemas de carregamento de contêineres

Abstract

Resumo: Esta tese apresenta técnicas exatas de resolução de problemas de carregamento de contêineres. Tais problemas consistem em determinar um arranjo de caixas no interior de uma unidade de transporte de carga, de modo que os itens sejam alocados de modo ortogonal e sem sobreposição, otimizando uma função objetivo, que em geral busca maximizar o valor associado à carga ou definir a menor quantidade de contêineres necessários para efetuar o transporte dos itens. Formulações matemáticas para resolução destes problemas são apresentadas nesta tese. Quatro técnicas para determinar a posição que as caixas podem ocupar no interior do contêiner foram avaliadas. Estratégias para obtenção de bounds também foram apresentadas e testadas. As restrições de estabilidade de carga, orientação de caixas e separação de itens, comuns em situações reais de carregamento, foram incorporadas aos modelos apresentados neste trabalho. Testes computacionais em instâncias clássicas foram efetuados, e a comparação com outras abordagens da literatura de carregamento de contêineres mostrou que as técnicas apresentadas nesta tese foram capazes de obter soluções ótimas e aprimorar a melhor solução conhecida em diversas instâncias dos problemas abordados. Palavras-chaves: Problema de carregamento de contêineres. Considerações práticas. Formulações matemáticas. Discretizações.

Abstract: This thesis presents exact techniques for solving container loading problems. Such problems consist in determining an arrangement of boxes within a cargo transport unit, so that items are placed orthogonally and without overlapping, optimizing an objective function, which generally seeks to maximize the value associated with the cargo or define the smallest number of containers needed to transport the items. Mathematical formulations for solving these problems are presented in this thesis. Four techniques for determining the position of boxes inside the container were evaluated. The constraints of loading stability, box orientation and separation of items, common in actual loading situations, were incorporated into the models presented in this work. Computational tests in classical instances were performed, and comparison with other approaches in the container loading literature showed that the techniques presented in this thesis were able to obtain optimal solutions and to improve the best known solution in several instances of the problems addressed. Key-words: Container loading problem. Practical considerations. Mathematical formulations. Discretizations