Abril 2015 vol. 1 num. 1 - Congresso Nacional de Matemática Aplicada à Indústria

Artigo Completo - Open Access.

Idioma principal | Segundo idioma

APLICANDO O ALGORITMO GENÉTICO DE CHAVES ALEATO´ RIAS VICIADAS EM UM PROBLEMA DE CORTE COM ITENS IRREGULARES

APLLYING THE BIASED RANDOM-KEY GENETIC ALGORITHM IN A CUTTING PROBLEM WITH IRREGULAR SHAPED ITEMS

Mundim, Leandro Resende ; Andretta, Marina ; Queiroz, Thiago Alves de ;

Artigo Completo:

Um dos problemas que ainda tem sido pouco explorado na literatura de corte de itens irregulares (polígonos convexos e não convexos) é o problema da mochila 0-1 (2PMI). No 2PMI é requerido que um subconjunto de itens seja empacotado em um recipiente retangular, com o objetivo de maximizar a ocupação da área. Os itens devem estar totalmente contidos no recipiente e nenhum deles pode se sobrepor com algum outro. Neste trabalho propomos uma abor- dagem baseada no algoritmo genético de chaves aleatórias viciadas partindo de um framework proposto na literatura. O diferencial está na técnica de alocação, que combina os cantos da mochila, utilizando o canto inferior esquerdo ou o canto superior esquerdo. Para encontrar posições viáveis e evitar a sobreposição, utilizamos uma malha de pontos ex- tráıda da técnica de no-fit polygon. Os experimentos computacionais mostraram que o algoritmo proposto é competitivo, conseguindo melhorar resultados da literatura.

Artigo Completo:

A problem with few references in the literature of nesting problems is the 0-1 knapsack problem with irregular shaped items (2PMI). In the 2PMI, it is required that a subset of items has to be packed in a rectangular bin aiming to maximize the occupied area. In this paper we use a framework proposed in the literature, which implements a biased random-key genetic algorithm. The main contribution of this paper is the allocation technique that considers the bottomleft or top-left corner of the bin. In order to find feasible positions and avoid overlapping between items, we use a mesh over a grid of no-fit polygons. The computational experiments validate the proposed algorithm showing that it is competitive, since it improved results from the recent literature.

Download (PDF)

Palavras-chave: Problemas de corte bidimensional, Problema da mochila 0-1, Itens irregulares, Algoritmo genético, Chaves viciadas, No-fit polygon., Two-dimensional cutting problems,

Palavras-chave: ,

DOI: 10.5151/mathpro-cnmai-0039

Referências bibliográficas
  • [1] Bean, J. C. 1994. Genetic algorithms and random keys for sequencing and optimization. ORSA journal on computing, 6(2), 154-160.
  • [2] Bennell, J. A. e Oliveira, J. F. 2008. The geometry of nesting problems: A tutorial. European Journal of Operational Research, 184, 397–415.
  • [3] Burke, E., Hellier, R., Kendall, G. e Whitwell, G. 2006. A new bottom-left-fill heuristic algorithm for the two-dimensional irregular packing problem. Operations research, 54(3), 587–601.
  • [4] Carravilla, M. A., Ribeiro, C. e Oliveira, J. F. 2003. Solving nesting problems with non-convex polygons by constraint logic programming. International Transactions in Operational Research, 10(6), 651–663.
  • [5] Cuninghame-Green, R. 1989. Geometry, shoemaking and the milk tray problem. New Scientist, 123, 6–20.
  • [6] Dalalah, D., Khrais, S. e Bataineh, K. 2014. Waste minimization in irregular stock cutting. Journal of Manufacturing Systems, 33, 27–40.
  • [7] Del Valle, A. M. 2010. Problema da mochila com itens irregulares. Dissertac¸ ˜ao de Mestrado, Universidade Estadual de Campinas (Unicamp) - SP.
  • [8] Del Valle, A. M., Queiroz, T. A., Miyazawa, F. K. e Xavier, E. C. 2012. Heuristics for two-dimensional knapsack and cutting stock problems with items of irregular shape. Expert Systems with Applications, 39, 12589–1259
  • [9] Dowsland, K. A., Vaid, S. e Dowsland, W. B. 2002. An algorithm for polygon placement using a bottom-left strategy. European Journal of Operational Research, 141, 371–381.
  • [10] Elkeran, A. 2013. A new approach for sheet nesting problem using guided cuckoo search and pairwise clustering. European Journal of Operational Research, 231, 757–769.
  • [11] Fischetti, M. e Luzzi, I. 2009. Mixed-integer programming models for nesting problems. Journal of Heuristics, 15(3), 201–226.
  • [12] Garey, M. R. e Johnson, D. S. 1979. Computers and intractability: a guide to the theory of np-hardness. Freeman, San Francisco. 124–127.
  • [13] Gomes, A. M. e Oliveira, J. F. 2006. Solving irregular strip packing problems by hybridising simulated annealing and linear programming. Journal of the Operational Research Society, 171, 811–829.
  • [14] Gonc¸alves, J. F. e Resende, M. G. 2011. Biased random-key genetic algorithms for combinatorial optimization. Journal of Heuristics, 17(5), 487–525.
  • [15] Holland, J.H. 1975. Adaptation in natural and artificial systems. University of Michigan Press.
  • [16] Jakobs, S. 1996. On genetic algorithms for the packing of polygons. European Journal of Operational Research, 88, 165–181.
  • [17] Mundim, L. R. e Queiroz, T. A. 2012. A hybrid heuristic for the 0-1 knapsack problem with items of irregular shape. In Informatica (CLEI), 2012 XXXVIII Conferˆencia Latino-americana. , 1–6.
  • [18] Oliveira, J. F., Gomes, A. M. e Ferreira, J. S. 2000. Topos - A new constructive algorithm for nesting problems. OR Spectrum, 22/, 263–284. O’Rourke, J. 1998 Computational Geometry in C. Cambridge. 33–43.
  • [19] Silveira, T. 2013. Problemas de empacotamento com itens irregulares: Heur´ısticas e avaliac¸ ˜ao de construtores de NFP. Dissertac¸ ˜ao de Mestrado, Universidade Estadual de Campinas (Unicamp) - SP.
  • [20] Toledo, F. M., Carravilla, M. A., Ribeiro, C., Oliveira, J. F. e Gomes, A. M. 2013. The dotted-board model: A new MIP model for nesting irregular shapes. International Journal of Production Economics, 145(2), 478–487.
  • [21] Toso, R. F. e Resende M. G. C. A C++ application programming interface for bised random-key genetic algorithms. ATandT Labs Research Technical Report.
  • [22] Yang, X. S. e Deb, S. 2010. Cuckoo search via L´evy flights World congress on nature and biologically inspired computing (NaBIC), 210–214.
Como citar:

Mundim, Leandro Resende; Andretta, Marina; Queiroz, Thiago Alves de; "APLICANDO O ALGORITMO GENÉTICO DE CHAVES ALEATO´ RIAS VICIADAS EM UM PROBLEMA DE CORTE COM ITENS IRREGULARES", p. 195-203 . In: Anais do Congresso Nacional de Matemática Aplicada à Indústria [= Blucher Mathematical Proceedings, v.1, n.1]. São Paulo: Blucher, 2015.
ISSN em b-reve, DOI 10.5151/mathpro-cnmai-0039

últimos 30 dias | último ano | desde a publicação


downloads


visualizações


indexações