Heur?sticas matem?ticas aplicadas ao problema de carregamento de cont?ineres.

Programa de P?s-Gradua??o em Ci?ncia da Computa??o. Departamento de Ci?ncia da Computa??o, Instituto de Ci?ncias Exatas e Biol?gicas, Universidade Federal de Ouro Preto.Este trabalho tem seu foco no Problema de Carregamento de Cont?ineres (CLP, do ingl?s Container Loading Problem). Neste problema, deseja-se alocar caixas de forma retangular em cont?ineres de modo que todas as caixas sejam alocadas e o volume total dos cont?ineres usados seja o menor poss?vel. Devido ao crescente n?mero de encomendas enviadas mundialmente, h? uma demanda por parte das empresas e da sociedade por m?todos para alocar caixas em cont?ineres de forma eficiente. Ao realizar o carregamento de caixas, as seguintes restri??es devem ser satisfeitas: todas as caixas devem ser alocadas; caixas n?o podem se sobrepor dentro de um cont?iner; e caixas devem ser alocadas inteiramente dentro da ?rea do cont?iner. Este trabalho prop?e duas heur?sticas matem?ticas para o CLP, baseadas em Relax-and-fix e Local Branching. As duas estrat?gias utilizam m?todos construtivos para produzir uma solu??o inicial e, em seguida, realizam uma busca local utilizando um modelo de programa??o inteira mista. Embora o Local Branching, assim como o Relax-and-fix, tenha sido capaz de encontrar uma solu??o at? pouco tempo desconhecida para uma inst?ncia, resultados indicam que o Relax-and-fix ? um m?todo mais promissor, pois ? capaz de gerar mais solu??es de qualidade, igualando por muitas vezes o melhor resultado conhecido na literatura.This paper focuses on the Container Loading Problem (CLP). In this problem, rectangular boxes must be allocated in containers so that the total volume of the used containers is as small as possible. Due to the increasing number of orders shipped worldwide, there is a demand by companies and society for methods to allocate boxes in containers efficiently. When carrying out the loading of boxes, some constraints must be observed, namely: all boxes must be allocated; boxes can not overlap within a container; and boxes should be allocated entirely within the container area. This work proposes two matheuristics for the CLP, based on Relax-and-fix and Local Branching. Both strategies employ a constructive algorithm to produce an initial solution and then perform a local search using a mixed integer programming model. Although the Local Branching, as well as the Relax-and-fix, was able to find a solution until recently unknown to an instance, results indicate that Relax-and-fix it is a more promising method, as it is capable of generating high quality solutions, often equaling the best result known in the literature