Solución al problema de empaquetamiento bidimensional usando un algoritmo híbrido constructivo de búsqueda en vecindad variable y recocido simulado

Autores/as

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

DOI:

https://doi.org/10.17533/udea.redin.17935

Palabras clave:

empaquetamiento bidimensional, vecindad variable

Resumen

En este trabajo, se modela el empaquetamiento de rectángulos con base en divisiones del área disponible, se utiliza una codificación de árbol binario para disponer las piezas de forma que se garantice el corte de tipo guillotina y se propone un algoritmo dividido en tres etapas que trabajan con estrategias individuales inspiradas en algoritmos de vecindad variable, recocido simulado y técnicas constructivas para lograr la solución del problema. Se comparan las respuestas obtenidas con base en la función objetivo que cuantifica el área utilizada y el porcentaje de utilización del material disponible para cincuenta casos de prueba de la literatura especializada frente a sus respectivas respuestas reportadas obteniéndose excelentes resultados.

|Resumen
= 130 veces | PDF
= 67 veces|

Descargas

Los datos de descargas todavía no están disponibles.

Biografía del autor/a

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

Citas

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.

Descargas

Publicado

2013-12-11

Cómo citar

Toro, E. M., Garcés, A., & Ruiz , H. (2013). Solución al problema de empaquetamiento bidimensional usando un algoritmo híbrido constructivo de búsqueda en vecindad variable y recocido simulado. Revista Facultad De Ingeniería Universidad De Antioquia, (46), 119–131. https://doi.org/10.17533/udea.redin.17935