A A new genotype-phenotype genetic algorithm for the two-dimensional strip packing problem with rotation of 90°
Published
Dec 7, 2015
Almetrics
Dimensions
Google Scholar
##plugins.themes.bootstrap3.article.details##
Abstract
Given a set of rectangular pieces and a fixed width with infinite length, the strip-packing problem (SPP) of two dimensions (2D), with a rotation of pieces in 90° consists of orthogonally placing all the pieces on the strip, without overlapping them, minimizing the height of the strip used. Several algorithms have been proposed to solve this problem, being Genetic Algorithms one of the most popular approach due to it effectiveness solving NP-Hard problems. In this paper, three binary representations, and classic crossover and mutation operators are introduced. A comparison of the three binary representations on a subset of benchmarking instances is performed. The representation R2 outperforms the results obtained by representation R1 and R3. Indeed, some of the bestknown results found by previous published approaches are improved.
Keywords
strip packing problem, genotype-phenotype, genetic algorithm, phenotype generationStrip Packing Problem, Genotipo-Fenotipo, Algoritmos Genéticos, Metaheurística, Algoritmo de colocación.
References
[1] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NPCompleteness. San Francisco, LA: Freeman, 1979.
[2] R. Álvarez-Valdés, F. Parreño, and J. M. Tamarit, “Reactive grasp for the strip-packing problem,” Computers & Operations Research, vol. 35, no. 4, pp. 1065-1083, 2008.
[3] T. Buchwald and G. Scheithauer, “Upper bounds for heuristic approaches to the strip packing problem,” International Transactions in Operational Research, vol. 23, no. 1-2, pp. 93- 119, 2014.
[4] A. Lodi, S. Martello, and D. Vigo, “Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems,” INFORMS Journal on Computing, vol. 11, no. 4, pp. 345-357, 1999.
[5] M. Kenmochi, T. Imamichi, K. Nnobe, M. Yagiura, and H. Nagamochi, “Exact algorithms for the 2-dimensional strip packing problem with and without rotations,” European Journal of Operational Research, vol. 198, no. 1, pp. 73-83, 2009.
[6] R. Álvarez-Valdés, F. Parreno, and J. Tamarit, “A branch and bound algorithm for the strip packing problem,” OR Spectrum, vol. 31, no. 2, pp. 431-459, 2009.
[7] Y. Arahori, T. Imamichi, and H. Nagamochi, “An exact strip packing algorithm based on canonical forms,” Computers & Operations Research, vol. 39, no. 12, pp. 2991-3011, 2012.
[8] S. C. Leung, D. Zhang, and K. M. Sim, “A two-stage intelligent search algorithm for the two-dimensional strip packing problem,” European Journal of Operational Research, vol. 215, no. 1, pp. 57-69, 2011.
[9] D. Chen, Y. Fu, M. Shang, and W. Huang, “A quasi-human heuristic algorithm for the 2D rectangular strip packing problem,” in Information Science and Engineering, 2008. ISISE’08. International Symposium on, vol. 2, pp. 392-396, IEEE, 2008.
[10] L. Wei, W.C. Oon, W. Zhu, and A. Lim, “A skyline heuristic for the 2D rectangular packing and strip packing problems,” European Journal of Operational Research, vol. 215, no. 2, pp. 337-346, 2011.
[11] R. Álvarez-Valdés, F. Parreño, and J. M. Tamarit, “A Tabu search algorithm for a twodimensional non-guillotine cutting problem,” European Journal of Operational Research, vol. 183, no. 3, pp. 1167-1182, 2007.
[12] G. Gómez-Villouta, J.-P. Hamiez, and J.-K. Hao, “Tabu search with consistent neighbourhood for strip packing,” in Trends in Applied Intelligent Systems. New York: Springer, 2010, pp. 1-10.
[13] E. Hopper and B. C. Turton, “An empirical investigation of metaheuristic and heuristic algorithms for a 2D packing problem,” European Journal of Operational Research, vol. 128, no. 1, pp. 34-57, 2001.
[14] E. K. Burke, M. R. Hyde, and G. Kendall, “A squeaky wheel optimisation methodology for two-dimensional strip packing,” Computers & Operations Research, vol. 38, no. 7, pp. 1035-1044, 2011.
[15] G. Belov, G. Scheithauer, and E. Mukhacheva, “One-dimensional heuristics adapted for two-dimensional rectangular strip packing,” Journal of the Operational Research Society, vol. 59, no. 6, pp. 823- 832, 2008.
[16] S. Yang, S. Han, and W. Ye, “A simple randomized algorithm for two-dimensional strip packing,” Computers & Operations Research, vol. 40, no. 1, pp. 1-8, 2013.
[17] E. G. Talbi, Metaheuristics: From Design to Implementation, vol. 74. New York: John Wiley & Sons, 2009.
[18] E. Hopper and B. Turton, “A genetic algorithm for a 2D industrial packing problem,” Computers & Industrial Engineering, vol. 37, no. 1, pp. 375-378, 1999.
[19] S. Jakobs, “On genetic algorithms for the packing of polygons,” European Journal of Operational Research, vol. 88, no. 1, pp. 165-181, 1996.
[20] D. E. Goldberg, Genetic algorithms in search, optimization, and machine learning. Boston: Addison Wesley, 1989.
[21] G. Syswerda, “Schedule optimization using genetic algorithms,” in Handbook of Genetic Algorithms, New York: Van Nostrand Reinhold, 1991.
[22] A. Bortfeldt, “A genetic algorithm for the two-dimensional strip packing problem with rectangular pieces,” European Journal of Operational Research, vol. 172, no. 3, pp. 814-837, 2006.
[23] M. Affenzeller, S. Wagner, S. Winkler, and A. Beham, Genetic Algorithms and Genetic Programming: Modern Concepts and Practical Applications. Boca Raton: CRC Press, 2009.
[24] A. Bortfeldt, Ein Genetischer Algorithmus fur das Zweidimensionale Strip-Packing-Problem. Planen, Lernen: Optimieren, 2003.
[25] R. García-Cáceres, C. Vega-Mejía, and J. Caballero-Villalobos, Integral Optimization of the Container Loading Problem. INTECH Open Access Publisher, 2011.
[26] K. He, Y. Jin, and W. Huang, “Heuristics for two-dimensional strip packing problema with 90 rotations,” Expert Systems with Applications, vol. 40, no. 14, pp. 5542-5550, 2013.
[27] R. Harren, K. Jansen, L. Pradel, and R. Van Stee, “A (5/3+ ε) - approximation for strip packing,” Computational Geometry, vol. 47, no. 2, pp. 248-267, 2014.
[28] J. L. da Silveira, E. C. Xavier, and F. K. Miyazawa, “Two-dimensional strip packing with unloading constraints,” Discrete Applied Mathematics, vol. 164, pp. 512-521, 2014.
[29] J. Thomas and N. S. Chaudhari, “A new metaheuristic genetic-based placement algorithm for 2D strip packing,” Journal of Industrial Engineering International, vol. 10, no. 1, pp. 1-16, 2014.
[30] S. Grandcolas and C. Pinto, “A new search procedure for the two- dimensional ortogonal packing problem,” Journal of Mathematical Modelling and Algorithms in Operations Research, pp. 1-19, 2015.
[31] E. Falkenauer, Genetic Algorithms and Grouping Problems. New York: John Wiley & Sons, 1998.
[32] E. Alba, Parallel Metaheuristics: A New Class of Algorithms. New Jersey: John Wiley & Sons, 2005.
[33] F. Rothlauf, “Representations for genetic and evolutionary algorithms,” Journal of Operational Research Society, vol. 54, no. 10, pp. 1112-1112, 2003.
[34] E. K. Burke, G. Kendall, and G. Whitwell, “A new placement heuristic for the ortogonal stock-cutting problem,” Operations Research, vol. 52, no. 4, pp. 655-671, 2004.
[35] V. Mancapa, T. Van Niekerk, and T. Hua, “A genetic algorithm for two dimensional strip packing problems,” South African Journal of Industrial Engineering, vol. 20, no. 2, pp. 145- 162, 2009.
[36] M. Matayoshi, “The 2D strip packing problem: a new approach with verification by EA,” in Systems Man and Cybernetics (SMC), 2010 IEEE International Conference on, pp. 2492-2499, IEEE, 2010.
[37] V. M. Kotov and D. Cao, “A heuristic algorithm for the non-oriented 2D rectangular strip packing problem,” Buletinul Academiei de Stiinte a Republicii Moldova. Matematica, no. 2, pp. 81-88, 2011.
[38] S. P. Coy, B. L. Golden, G. C. Runger, and E. A. Wasil, “Using experimental design to find effective parameter settings for heuristics,” Journal of Heuristics, vol. 7, no. 1, pp. 77-97, 2001.
[39] W. Huang and D. Chen, “An efficient heuristic algorithm for rectangle - packing problem,” Simulation Modelling Practice and Theory, vol. 15, no. 10, pp. 1356-1365, 2007.
[2] R. Álvarez-Valdés, F. Parreño, and J. M. Tamarit, “Reactive grasp for the strip-packing problem,” Computers & Operations Research, vol. 35, no. 4, pp. 1065-1083, 2008.
[3] T. Buchwald and G. Scheithauer, “Upper bounds for heuristic approaches to the strip packing problem,” International Transactions in Operational Research, vol. 23, no. 1-2, pp. 93- 119, 2014.
[4] A. Lodi, S. Martello, and D. Vigo, “Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems,” INFORMS Journal on Computing, vol. 11, no. 4, pp. 345-357, 1999.
[5] M. Kenmochi, T. Imamichi, K. Nnobe, M. Yagiura, and H. Nagamochi, “Exact algorithms for the 2-dimensional strip packing problem with and without rotations,” European Journal of Operational Research, vol. 198, no. 1, pp. 73-83, 2009.
[6] R. Álvarez-Valdés, F. Parreno, and J. Tamarit, “A branch and bound algorithm for the strip packing problem,” OR Spectrum, vol. 31, no. 2, pp. 431-459, 2009.
[7] Y. Arahori, T. Imamichi, and H. Nagamochi, “An exact strip packing algorithm based on canonical forms,” Computers & Operations Research, vol. 39, no. 12, pp. 2991-3011, 2012.
[8] S. C. Leung, D. Zhang, and K. M. Sim, “A two-stage intelligent search algorithm for the two-dimensional strip packing problem,” European Journal of Operational Research, vol. 215, no. 1, pp. 57-69, 2011.
[9] D. Chen, Y. Fu, M. Shang, and W. Huang, “A quasi-human heuristic algorithm for the 2D rectangular strip packing problem,” in Information Science and Engineering, 2008. ISISE’08. International Symposium on, vol. 2, pp. 392-396, IEEE, 2008.
[10] L. Wei, W.C. Oon, W. Zhu, and A. Lim, “A skyline heuristic for the 2D rectangular packing and strip packing problems,” European Journal of Operational Research, vol. 215, no. 2, pp. 337-346, 2011.
[11] R. Álvarez-Valdés, F. Parreño, and J. M. Tamarit, “A Tabu search algorithm for a twodimensional non-guillotine cutting problem,” European Journal of Operational Research, vol. 183, no. 3, pp. 1167-1182, 2007.
[12] G. Gómez-Villouta, J.-P. Hamiez, and J.-K. Hao, “Tabu search with consistent neighbourhood for strip packing,” in Trends in Applied Intelligent Systems. New York: Springer, 2010, pp. 1-10.
[13] E. Hopper and B. C. Turton, “An empirical investigation of metaheuristic and heuristic algorithms for a 2D packing problem,” European Journal of Operational Research, vol. 128, no. 1, pp. 34-57, 2001.
[14] E. K. Burke, M. R. Hyde, and G. Kendall, “A squeaky wheel optimisation methodology for two-dimensional strip packing,” Computers & Operations Research, vol. 38, no. 7, pp. 1035-1044, 2011.
[15] G. Belov, G. Scheithauer, and E. Mukhacheva, “One-dimensional heuristics adapted for two-dimensional rectangular strip packing,” Journal of the Operational Research Society, vol. 59, no. 6, pp. 823- 832, 2008.
[16] S. Yang, S. Han, and W. Ye, “A simple randomized algorithm for two-dimensional strip packing,” Computers & Operations Research, vol. 40, no. 1, pp. 1-8, 2013.
[17] E. G. Talbi, Metaheuristics: From Design to Implementation, vol. 74. New York: John Wiley & Sons, 2009.
[18] E. Hopper and B. Turton, “A genetic algorithm for a 2D industrial packing problem,” Computers & Industrial Engineering, vol. 37, no. 1, pp. 375-378, 1999.
[19] S. Jakobs, “On genetic algorithms for the packing of polygons,” European Journal of Operational Research, vol. 88, no. 1, pp. 165-181, 1996.
[20] D. E. Goldberg, Genetic algorithms in search, optimization, and machine learning. Boston: Addison Wesley, 1989.
[21] G. Syswerda, “Schedule optimization using genetic algorithms,” in Handbook of Genetic Algorithms, New York: Van Nostrand Reinhold, 1991.
[22] A. Bortfeldt, “A genetic algorithm for the two-dimensional strip packing problem with rectangular pieces,” European Journal of Operational Research, vol. 172, no. 3, pp. 814-837, 2006.
[23] M. Affenzeller, S. Wagner, S. Winkler, and A. Beham, Genetic Algorithms and Genetic Programming: Modern Concepts and Practical Applications. Boca Raton: CRC Press, 2009.
[24] A. Bortfeldt, Ein Genetischer Algorithmus fur das Zweidimensionale Strip-Packing-Problem. Planen, Lernen: Optimieren, 2003.
[25] R. García-Cáceres, C. Vega-Mejía, and J. Caballero-Villalobos, Integral Optimization of the Container Loading Problem. INTECH Open Access Publisher, 2011.
[26] K. He, Y. Jin, and W. Huang, “Heuristics for two-dimensional strip packing problema with 90 rotations,” Expert Systems with Applications, vol. 40, no. 14, pp. 5542-5550, 2013.
[27] R. Harren, K. Jansen, L. Pradel, and R. Van Stee, “A (5/3+ ε) - approximation for strip packing,” Computational Geometry, vol. 47, no. 2, pp. 248-267, 2014.
[28] J. L. da Silveira, E. C. Xavier, and F. K. Miyazawa, “Two-dimensional strip packing with unloading constraints,” Discrete Applied Mathematics, vol. 164, pp. 512-521, 2014.
[29] J. Thomas and N. S. Chaudhari, “A new metaheuristic genetic-based placement algorithm for 2D strip packing,” Journal of Industrial Engineering International, vol. 10, no. 1, pp. 1-16, 2014.
[30] S. Grandcolas and C. Pinto, “A new search procedure for the two- dimensional ortogonal packing problem,” Journal of Mathematical Modelling and Algorithms in Operations Research, pp. 1-19, 2015.
[31] E. Falkenauer, Genetic Algorithms and Grouping Problems. New York: John Wiley & Sons, 1998.
[32] E. Alba, Parallel Metaheuristics: A New Class of Algorithms. New Jersey: John Wiley & Sons, 2005.
[33] F. Rothlauf, “Representations for genetic and evolutionary algorithms,” Journal of Operational Research Society, vol. 54, no. 10, pp. 1112-1112, 2003.
[34] E. K. Burke, G. Kendall, and G. Whitwell, “A new placement heuristic for the ortogonal stock-cutting problem,” Operations Research, vol. 52, no. 4, pp. 655-671, 2004.
[35] V. Mancapa, T. Van Niekerk, and T. Hua, “A genetic algorithm for two dimensional strip packing problems,” South African Journal of Industrial Engineering, vol. 20, no. 2, pp. 145- 162, 2009.
[36] M. Matayoshi, “The 2D strip packing problem: a new approach with verification by EA,” in Systems Man and Cybernetics (SMC), 2010 IEEE International Conference on, pp. 2492-2499, IEEE, 2010.
[37] V. M. Kotov and D. Cao, “A heuristic algorithm for the non-oriented 2D rectangular strip packing problem,” Buletinul Academiei de Stiinte a Republicii Moldova. Matematica, no. 2, pp. 81-88, 2011.
[38] S. P. Coy, B. L. Golden, G. C. Runger, and E. A. Wasil, “Using experimental design to find effective parameter settings for heuristics,” Journal of Heuristics, vol. 7, no. 1, pp. 77-97, 2001.
[39] W. Huang and D. Chen, “An efficient heuristic algorithm for rectangle - packing problem,” Simulation Modelling Practice and Theory, vol. 15, no. 10, pp. 1356-1365, 2007.
How to Cite
Gatica, G., Villagrán, G., Contreras-Bolton, C., Linfati, R., & Escobar-Velásquez, J. W. (2015). A A new genotype-phenotype genetic algorithm for the two-dimensional strip packing problem with rotation of 90°. Ingeniería Y Universidad, 20(1), 119–138. https://doi.org/10.11144/Javeriana.iyu20-1.ngpg
Section
Industrial and systems engineering