Two dimensional packing problem using a hybrid constructive algorithm of variable neighborhood search and simulated annealing

Authors

  • Eliana Mirledy Toro Universidad Tecnológica de Pereira
  • Alejandro Garcés Universidad Tecnológica de Pereira
  • Hugo Ruiz Universidad Tecnológica de Pereira

Keywords:

Guillotine, two-dimensional cutting, variable neighborhood search, optimization

Abstract


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.

|Abstract
= 74 veces | PDF (ESPAÑOL (ESPAÑA))
= 34 veces|

Downloads

Download data is not yet available.

Author Biographies

Eliana Mirledy Toro, Universidad Tecnológica de Pereira

Facultad de Ingeniería Industrial

Alejandro Garcés, Universidad Tecnológica de Pereira

Programa de Ingeniería Eléctrica

Hugo Ruiz, Universidad Tecnológica de Pereira

Programa de Ingeniería Eléctrica

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.

N. Christofides, A. Whitlock. “An algorithm for twodimensional cutting problems”. Operational Research. Vol. 25. 1977. pp. 30-44.

P. C. Gilmore, R.E. Gomory. “The theory and computation of knapsack functions”. Operations Research. Vol 15. 1967. pp. 1045-1074.

P. Wang. “Two algorithms for constrained twodimensional cutting stock problems”. Operations Research. Vol. 31. 1983. pp. 573-586.

F. A. Vasko. “Computational improvement to Wang’s two-dimensional cutting stock algorithm”. Computers and Industrial Engineering. Vol. 16. 1989. pp. 109-115.

J. F. Oliveira, J. S. Ferreira. “An improved version of Wang’s algorithm for two - dimensional Cutting Problems”. EJOR 44. 1990. pp. 256-266.

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.

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.

J. E. Beasley. “A population heuristic for constrained two-dimensional non guillotine cutting”. European Journal of Operational Research. Vol. 156. 2004. pp. 601-627.

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.

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.

Published

2013-12-11

How to Cite

Toro, E. M., Garcés, A., & Ruiz , H. (2013). Two dimensional packing problem using a hybrid constructive algorithm of variable neighborhood search and simulated annealing. Revista Facultad De Ingeniería Universidad De Antioquia, (46), 119–131. Retrieved from https://revistas.udea.edu.co/index.php/ingenieria/article/view/17935