Solución al problema de empaquetamiento bidimensional usando un algoritmo híbrido constructivo de búsqueda en vecindad variable y recocido simulado
DOI:
https://doi.org/10.17533/udea.redin.17935Palabras clave:
empaquetamiento bidimensional, vecindad variableResumen
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.
Descargas
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
Cómo citar
Número
Sección
Licencia
Los artículos disponibles en la Revista Facultad de Ingeniería, Universidad de Antioquia están bajo la licencia Creative Commons Attribution BY-NC-SA 4.0.
Eres libre de:
Compartir — copiar y redistribuir el material en cualquier medio o formato
Adaptar : remezclar, transformar y construir sobre el material.
Bajo los siguientes términos:
Reconocimiento : debe otorgar el crédito correspondiente , proporcionar un enlace a la licencia e indicar si se realizaron cambios . Puede hacerlo de cualquier manera razonable, pero no de ninguna manera que sugiera que el licenciante lo respalda a usted o su uso.
No comercial : no puede utilizar el material con fines comerciales .
Compartir igual : si remezcla, transforma o construye a partir del material, debe distribuir sus contribuciones bajo la misma licencia que el original.
El material publicado por la revista puede ser distribuido, copiado y exhibido por terceros si se dan los respectivos créditos a la revista, sin ningún costo. No se puede obtener ningún beneficio comercial y las obras derivadas tienen que estar bajo los mismos términos de licencia que el trabajo original.
Twitter