O PROBLEMA DA MOCHILA TRIDIMENSIONAL RESOLVIDO POR UMA HEURÍSTICA

THE THREE DIMENSIONAL KNAPSACK PROBLEM SOLVED WITH A HEURISTIC APPROACH

Moura, Mirella Augusta Sousa; Queiroz, Thiago Alves de

Artigo Completo:

Problemas de empacotamento têm aparecido constantemente nas indústrias, com aplicações principalmente nas cadeias de suprimento e logística. Esta pesquisa lida com o problema da mochila ilimitado em sua versão tridimensional com o objetivo de maximizar a ocupação do recipiente. No problema em questão não há um limite quanto ao número de cópias de cada item que podem ser empacotados, porém os itens devem ser organizados sem sobreposição e respeitando as dimensões do recipiente. Apresenta-se uma heurística baseada na técnica de Recozimento Simulado, que busca diminuir o desperdício selecionando o item com a melhor aptidão para ser colocado em espaços vazios. A linguagem de programação C foi usada para a codificação dos algoritmos, em que testes computacionais usando instâncias da literatura mostraram resultados satisfatórios.

Packing problems have been used in industries constantly, mainly in supply chain and logistic organizations. This research deals with the knapsack problem in its three-dimensional version with the objective of maximize the occupied volume for a single container. We study the version of the problem in which there is no limit on the number of copies of each item that may be packed, but items must be arranged with no overlapping and respecting the container dimensions. We present a heuristic based on the Simulated Annealing metaheuristic that aims for minimize the trim loss, and that selects items with the best fitness value, considering empty spaces. The C programming language was used to code the algorithms, in which computational experiments using instances from the literature shown that the heuristic is reasonable for solve medium-sized instances, whereas it fails in some cases.

Palavras-chave:

DOI: 10.5151/mathpro-cnmai-0121

Referências bibliográficas

• [1] ANDREW L.; HONG M. The single container loading problem with axle weight constraints. International Jornal of Production Economics, 144(6): 358– 69, 2013.
• [2] ARENALES M.; ARMENTANO V.; MORABITO R.; YANASSE H. Pesquisa Operacional. Rio de Janeiro: Elsevier, 2007.
• [3] BALDI M. M.; PERBOLI G.; TADEI R. The three-dimensional knapsack problem with balancing constraints. Applied Mathematics and Computation, 218(19): 9802-9818, 2012.
• [4] BEASLEY J. E. Algorithms for unconstrained two-dimensional guillotine cutting. Journal of the Operational Research Society, 36: 297-306, 1985.
• [5] BISCHOFF E. E.; RATCLIFF M. S. W. Issues in the development of approaches to container loading. OMEGA. International Journal of Management Science, 23(4): 377–390, 1995.
• [6] BORTFELDT A.; GEHRING H.; MACK D. A parallel tabu search algorithm for solving the container loading problem. Parallel Computing, 29(5):641-62, 2003.
• [7] CHEN C. S.; LEE S. M.; SHEN Q.S. An analytical model for the container loading problem. European Journal of Operational Research, 80: 68–76, 1995.
• [8] EGEBLAD J.; PISINGER D. Heuristic approaches for the two-and three- dimensional knapsack packing problem. Computers and Operations Research; 36(4):1026-1049, 2009.
• [9] ELEY M. Solving container loading problems by block arrangement. European Journal of Operational Research, 141(2): 393-409, 2002.
• [10] GEHRING H.; BORTFELDT A. A genetic algorithm for solving the container loading problem. International Transactions in Operational Research, 401–18, 1997.
• [11] HILLIER, F. S.; LIEBERMAN, G. J. Introdução à Pesquisa Operacional. 8 ed. Porto Alegre: McGraw-Hill, 2007e. JUNQUEIRA L. Modelos de programação matemática para problemas de carregamento de caixas dentro de contêineres. Dissertação de Mestrado, Departamento de Engenharia de Produção, Universidade Federal de São Carlos, São Carlos - SP, Brasil, 2009.
• [12] JUNQUEIRA L.; MORABITO R.; YAMASHITA D. S. Modelos de otimização para problemas de carregamento de contêineres com considerações de estabilidade e de empilhamento. Pesquisa Operacional, 30: 73-98, 2010. JUNQUEIRA L.; MOROBITO R.; YAMASHITA D. S. Three-dimensional container loading models with cargo stability and load bearing constraints. Computers and Operations Research, 39(1): 74-85, 2012.
• [13] KIRKPATRICK S.; GELLAT JR C. D.; VECCHI M. P. Optimizing by simulated annealing. Science, 220(4598): 671-680, 1983.
• [14] LEUNG S. C. H.; ZHANG D.; ZHOU C.; WU T. A hybrid simulated annealing metaheuristic algorithm for the two- dimensional knapsack packing problem. Computers and Operations Research, 39: 64-73, 2012.
• [15] PISINGER D. Heuristics for the container loading problem. European Journal of Operational Research, 141: 143– 53, 2002.
• [16] QUEIROZ T. A. Algoritmos para Problemas de Corte e Empacotamento. Tese de doutorado, Instituto de Computação, Universidade Estadual de Campinas, Campinas - SP, Brasil, 2010.
• [17] WÄSCHER G.; HAUSSNER H.; SCHUMANN H. An improved typology of cutting and packing problems. European Journal of Operational Research, 183(3): 1109-1130, 2007.

Como citar:

Moura, Mirella Augusta Sousa; Queiroz, Thiago Alves de; "O PROBLEMA DA MOCHILA TRIDIMENSIONAL RESOLVIDO POR UMA HEURÍSTICA", p-686-694. In: Anais do Congresso Nacional de Matemática Aplicada à Indústria [= Blucher Mathematical Proceedings, v.1, n.1]. São Paulo: Blucher, 2015.
ISSN soon, DOI 10.5151/mathpro-cnmai-0121