Um refinamento do algoritmo tabu de Dowsland para o problema de carregamento de paletes do produtor
A refinement of Dowsland's tabu search algorithm for the manufacturer's pallet loading problem
Yamassaki, Cinthia A.; Pureza, Vitoria
http://dx.doi.org/10.1590/S0103-65132003000300002
Prod, vol.13, n3, p.6-17, 2003
Resumo
O Problema de Carregamento de Paletes do Produtor consiste em arranjar, ortogonalmente e sem sobreposição, o máximo número de caixas retangulares idênticas de dimensões (l,w) sobre um palete (L,W). Este problema vem sendo tratado com sucesso por heurísticas de blocos, as quais constroem padrões de carregamento com um ou mais blocos, cujas caixas possuem a mesma orientação. Os arranjos gerados por estes métodos estão limitados aos chamados padrões não-guilhotinados de primeira ordem. Neste trabalho, foi elaborada uma implementação baseada no algoritmo de busca tabu de Dowsland, que, ao contrário das heurísticas de blocos, provê arranjos não limitados a padrões particulares de empacotamento. Experimentos computacionais com um conjunto de 34 exemplos extraídos da literatura e de contextos reais indicam que a abordagem é capaz de resolver otimamente a maioria dos exemplos; para os exemplos não resolvidos, é proposto um procedimento adicional simples, cuja aplicação resultou na obtenção de padrões ótimos.
Palavras-chave
Problema de carregamento de paletes, busca tabu, otimização combinatória
Abstract
The Manufacturer's Pallet Loading Problem (MPLP) consists in arranging, orthogonally and without overlapping, the maximum number of rectangular and identical pieces of sizes (l, w) onto a pallet (L, W). The MPLP has been successfully handled by block heuristics, which generate loading patterns with one or more blocks where the pieces have the same orientation. The resulting patterns produced by these methods are limited to the so-called 1st order non-guillotine patterns. In this work we present a tabu search implementation based on the algorithm proposed by Dowsland to solve the MPLP; differently than block heuristics, the solutions are not limited to particular loading patterns. Computational experiments with a set of 34 instances extracted from the literature as well as from practical contexts indicate that this approach is capable to solve most of the examples. For the unsolved instances, we propose a simple additional procedure, which resulted in optimal patterns.
Keywords
Pallet loading problem, tabu search, combinatorial optimization
References
ARENALES, M.; MORABITO, R. An and/or-graph approach to the solution of two-dimensional non-guillotine cutting problems. European Journal of Operational Research, vol. 84, p. 599-617, 1995.
ARENALES, M.; MORABITO, R.; YANASSE, H. Special issue: Cutting and packing problems. Pesquisa Operacional, vol. 19, n. 2, p. 109-284, 1999.
BEASLEY, J. E. An exact two-dimensional non-guillotine cutting tree search procedure. Operations Research, vol. 33, n. 1, pp. 49-64, 1985.
BALASUBRAMANIAN, R. The pallet loading problem: A survey. International Journal of Production Economics, vol. 28, p. 217-225, 1992.
BHATTACHARYA, S.; ROY, R.; BHATTACHARYA, S. An exact depth-first algorithm for the pallet loading problem. European Journal of Operational Research, vol. 110, n. 3, p. 612-625, 1998.
BISCHOFF, E.; DOWSLAND, W. B. An application of the micro product design and distribution. Journal of Operational Research, vol. 84, n. 3, p. 271-280, 1982.
BISCHOFF, E.; RATCLIFF, M. Loading multiple pallets. Journal of the Operational Research Society, vol. 46, p. 1322-1336, 1995.
BISCHOFF, E.; WAESCHER, G. Special issue on cutting and packing. European Journal of Operational Research, vol. 84, n. 3, p. 503-712, 1995.
DYCKHOFF, H. A typology of cutting and packing problems. European Journal of Operational Research, vol. 44, p. 145-159, 1990.
DYCKHOFF, H.; FINKE, U. Cutting and packing in production and distribution: Typology and bibliography. Springler-Verlag Co, Heildelberg, 1992.
DYCKHOFF, H.; SCHEITHAUER, G.; TERNO, J. Cutting and packing. In: M. AMICO; F. MAFFIOLI; S. MARTELLO: Annotated bibliographies in combinatorial optimisation, John Wiley & Sons, New York, NY, p. 393-414, 1997.
DOWSLAND, K. The three-dimensional pallet chart: an analysis of the factors affecting the set of feasible layouts for a class of two-dimensional packing problems. Journal of the Operational Research Society, vol. 35, p. 895-905, 1984
DOWSLAND, K. An exact algorithm for the pallet loading problem. European Journal of Operational Research, vol. 31, p. 78-84, 1987.
DOWSLAND, K. Some experiments with simulated annealing techniques for packing problems. European Journal of Operational Research, vol. 68, p. 389-399, 1993.
DOWSLAND, K. Simple tabu thresholding and the pallet loading problem. In: I. H. OSMAN, I. H.; KELLY J. P: Metaheuristics: Theory and Applications, Kluwer Academic Publishers, p. 379-406, 1996.
DOWSLAND, K.; DOWSLAND, W. Packing problems. European Journal of Operational Research, vol. 56, p. 2-14, 1992.
FARAGO, R.; MORABITO, R. Um método heurístico baseado em relaxação Lagrangiana para resolver o problema de carregamento de paletes do produtor. Pesquisa Operacional, vol. 12, n. 2, p. 197-212, 2000.
FEO, T.; RESENDE M. G. C. Greedy randomized adaptive search procedures. Journal of Global Optimization, vol. 6, p. 109-133, 1995.
GLOVER, F.; LAGUNA, M. Tabu Search, Kluwer Academic Pub., 1997.
HADJICONSTANTINOU, E.; CHRISTOFIDES, N. An exact algorithm for general, orthogonal, two-dimensional knapsack problems. European Journal of Operational Research, vol. 83, p. 39-56, 1995.
HERBERT E.; DOWSLAND K. A family of genetic algorithms for the pallet loading problem. Annals of Operations Research, vol. 63 - Metaheuristics in Combinatorial Optimization, 1996.
HIFI, M. Special issue: cutting and packing problems. Studia Informatica Universalis, vol. 2, n. 1, p. 1-161, 2002.
HODGSON, T. A combined approach to the pallet loading problem. IIE Transactions, vol. 14, n. 3, p. 176-182, 1982.
HOLLAND, J. H. Adaptation in Natural and Artificial Systems. Ann Arbor, University of Michigan Press, 1975.
KIRKPATRICK, S.; GELLAT, C. D.; VECCHI, M. P. Optimization by simulated annealing. Science, vol. 220, p. 671-680, 1983.
LETCHFORD, A.; AMARAL, A. Analysis of upper bounds for the pallet loading problem. European Journal of Operational Research, n. 132, p. 582-593, 2001.
LINS, L.; LINS, S.; MORABITO, R. An L-approach for packing (l, w)-rectangles into rectangular and L-shaped pieces. Aceito para publicação em Journal of the Operational Research Society, 2003.
MARTELLO, S. Special issue: knapsack, packing and cutting, Part II: Multidimensional knapsack and cutting stock problems. INFOR, vol. 32, n. 4, 1994.
MARTINS, G. H. Packing in two and three dimensions. Ph.D. Dissertation. Naval Postgraduate School, Monterey, CA, EUA, 2002.
MORABITO, R.; ARENALES, M. An and/or-graph approach to the container loading problem. International Transactions in Operational Research, vol. 1, n. 1, p. 59-73, 1994.
MORABITO, R.; FARAGO, R. A tight lagrangean relaxation bound for the manufacturer's pallet loading problem. Studia Informatica Universalis, vol. 2, n. 1, p. 57-76, 2002.
MORABITO, R.; MORALES, S. R. A simple and effective heuristic to solve the manufacturer's pallet loading problem. Journal of the Operational Research Society, n. 48, p. 819-828, 1998.
NELISSEN, J. How to use structural constraints to compute an upper bound for the pallet loading problems. European Journal of Operational Research, n. 84, p. 662-680, 1995.
PUREZA, V.; MORABITO, R. Uma heurística de busca tabu simples para o problema de carregamento de paletes do produtor. Pesquisa Operacional, vol. 23, n. 2, p. 359-378, 2003.
SCHEITHAUER, G.; TERNO, J. The G4 heuristic for the pallet loading problem. Journal of the Operational Research Society, n. 47, p. 511-522, 1996.
SMITH, A.; DE CANI, P. An algorithm to optimize the layout of boxes in pallets. Journal of the Operational Research Society, n. 31, p. 573-578, 1980.
STEUDEL, H. Generating pallet loading patterns: a special case of the two-dimensional cutting stock problem. Management Science, n. 10, p. 997-1004, 1979.
SWEENEY, P.; PATERNOSTER, E. Cutting and packing problems: a categorized, application-oriented research bibliography. Journal of the Operational Research Society, n. 43, p. 691-706, 1992.
TARNOWSKI, A.; TERNO, J.; SCHEITHAUER, G. A polynomial-time algorithm for the guillotine pallet loading problem. INFOR, vol. 32, n. 4, p. 275-287, 1994.
TSAI, R.; MALSTROM, E.; KUO, W. Three-dimensional palletization of mixed box sizes. IEE Transactions, vol. 25, p. 64-75, 1993.
WANG, P.; WAESCHER, G. Special issue on cutting and packing. European Journal of Operational Research, vol. 141, n. 2, p. 239-469, 2002.
Facebook
Google+
Twitter
LinkedIn
Mendeley
StumbleUpon
CiteULike
Reddit
Email