Two dimensional packing problem using a hybrid constructive algorithm of variable neighborhood search and simulated annealing
DOI:
https://doi.org/10.17533/udea.redin.17935Keywords:
Guillotine, two-dimensional cutting, variable neighborhood search, optimizationAbstract
In this work, the packing of rectangles is modeled based on divisions of the available area, a binary tree codification is used to arrange the pieces so that the guillotines type cutting is guaranteed. A three stages algorithm with individual strategies inspired by algorithms of variable neighborhood search simulated annealing and constructive techniques are used to obtain the solution of the problem. The results obtained are compared using the objective function and percentage used of available area with fifty test cases of the specialized literature and their respective well-known answer with excellent results.
Downloads
References
S. Jakobs. “Theory and methodology on genetic algorithms for the packing of polygons”. European Journal of Operational Research. Vol. 88. 1996. pp. 87-100. DOI: https://doi.org/10.1016/0377-2217(94)00166-9
N. Christofides, A. Whitlock. “An algorithm for twodimensional cutting problems”. Operational Research. Vol. 25. 1977. pp. 30-44. DOI: https://doi.org/10.1287/opre.25.1.30
P. C. Gilmore, R.E. Gomory. “The theory and computation of knapsack functions”. Operations Research. Vol 15. 1967. pp. 1045-1074. DOI: https://doi.org/10.1287/opre.14.6.1045
P. Wang. “Two algorithms for constrained twodimensional cutting stock problems”. Operations Research. Vol. 31. 1983. pp. 573-586. DOI: https://doi.org/10.1287/opre.31.3.573
F. A. Vasko. “Computational improvement to Wang’s two-dimensional cutting stock algorithm”. Computers and Industrial Engineering. Vol. 16. 1989. pp. 109-115. DOI: https://doi.org/10.1016/0360-8352(89)90013-2
J. F. Oliveira, J. S. Ferreira. “An improved version of Wang’s algorithm for two - dimensional Cutting Problems”. EJOR 44. 1990. pp. 256-266. DOI: https://doi.org/10.1016/0377-2217(90)90361-E
K. Lai, J. Chan. “A evolutionary algorithm for the rectangular cutting stock problem”. International Journal of Industrial Engineering. Vol 4. 1997. pp.130-139.
V. Parada, M. Sepúlveda, A. Gómez. “Solution for the Constrained Guillotine Cutting Problem by Simulated Annealing”. Journal on computers and operations research. Vol 25. 1998. pp. 37-47. DOI: https://doi.org/10.1016/S0305-0548(98)80006-3
T. W. Leung, C. H. Yung, M. D. Troutt. “Applications of genetic search and simulated annealing to the two-dimensional non-guillotine cutting stock problem”. Computers and Industrial Engineering. Vol. 40. 2001. pp. 201-214. DOI: https://doi.org/10.1016/S0360-8352(01)00021-3
J. E. Beasley. “A population heuristic for constrained two-dimensional non guillotine cutting”. European Journal of Operational Research. Vol. 156. 2004. pp. 601-627. DOI: https://doi.org/10.1016/S0377-2217(03)00139-5
C. Yaodong. “An exact algorithm for generating homogenous T-shape cutting patterns”. Computers & Operations Research. Vol 34. 2007. pp. 1107-1120. Disponible en Internet en: http://www.gxnu.edu.cn/Personal/ydcui/English/Paper.htm. Consultada el 10 de abril de 2007. DOI: https://doi.org/10.1016/j.cor.2005.05.025
P. Hansen, M. Nenad, J. Moreno. “Búsqueda de entorno variable. Inteligencia Artificial”. Revista Iberoamericana de Inteligencia Artificial. Vol. 19. 2003. pp. 77-92.
R. Gallego, A. Escobar, R. Romero. Técnicas de optimización combinatorial. Textos universitarios. Universidad Tecnológica de Pereira. Pereira. 2006. pp. 27-47.
Downloads
Published
How to Cite
Issue
Section
License
Revista Facultad de Ingeniería, Universidad de Antioquia is licensed under the Creative Commons Attribution BY-NC-SA 4.0 license. https://creativecommons.org/licenses/by-nc-sa/4.0/deed.en
You are free to:
Share — copy and redistribute the material in any medium or format
Adapt — remix, transform, and build upon the material
Under the following terms:
Attribution — You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
NonCommercial — You may not use the material for commercial purposes.
ShareAlike — If you remix, transform, or build upon the material, you must distribute your contributions under the same license as the original.
The material published in the journal can be distributed, copied and exhibited by third parties if the respective credits are given to the journal. No commercial benefit can be obtained and derivative works must be under the same license terms as the original work.
Twitter