Problemas de empacotamento aparecem com freqüência em várias situações operacionais da atualidade. O transporte de mercadorias, empacotamento de produtos, alocação de contêineres e a indústria têxtil, entre outros, possuem tais problemas. Um problema de empacotamento consiste em determinar disposições de um determinado (não necessariamente fixo) número de itens em um objeto, de forma que os itens não se sobreponham entre si e estejam contidos no objeto. Neste trabalho, dado um número fixo N de itens circulares ou esféricos, com raios quaisquer, desejamos encontrar o objeto bidimensional com menor área ou tridimensional com menor volume, respectivamente, que os contenha sem que eles se sobreponham dois a dois.

Foram desenvolvidos modelos não lineares para os problemas associados a cada objeto. Para resolver os modelos, foi utilizado um algoritmo baseado em Lagrangeanos Aumentados (denominado ALGENCAN). Como estes modelos possuem diversos minimizadores locais (soluções viáveis cujo valor encontrado não é o menor possível) uma estratégia denominada multi-start foi utilizada, que consiste em resolver uma mesma instância do problema com diversos pontos iniciais distintos e escolher aquele com o menor valor. Visando maior eficiência na avaliação da sobreposição entre itens, foi utilizada uma técnica que diminui o custo de tal avaliação de O(N²) para, em média, O(N). Dessa maneira, problemas com um maior número de itens foram resolvidos. Todos os modelos foram implementados na linguagem de programação Fortran 77.

Os modelos foram resolvidos em um computados AMD Athlon 64 3200+ com 2202.87MHz e 1GB de memória RAM. O critério de parada para cada instância do problema foi o tempo de uso da CPU. Para problemas bidimensionais (itens circulares) todos os resultados obtidos que puderam ser comparados com aqueles existentes na literatura foram iguais. Além disso resolvemos problemas com um grande número de itens que não aparecem na literatura. Os resultados em 3D também são inéditos.

Todos os problemas foram modelados e resolvidos, e seus resultados foram comparados com aqueles encontrados na literatura. As comparações mostraram a eficácia da abordagem não linear para problemas de empacotamento. Utilizando a técnica para melhorar a eficiência da avaliação das sobreposições, foi possível resolver problemas com um número maior de itens.

Instituição de fomento: CNPq

Trabalho de Iniciação Científica