Hiperheur�?sticas para resolver el problema de empacado irregular de material en dos dimensiones

Abstract

El problema de corte y empacado de materiales en dos dimensiones tiene gran relevancia práctica; por ejemplo, en la industria textil, de lámina metálica, madera, piel, plástico y papel [1]. Es por esto que ha sido ampliamente estudiado en los últimos a ̃nos, sobretodo en lo que se refiere al corte de piezas rectangulares. El corte de figuras irregulares es más complejo por lo que es posible abordarlo desde muy distintos enfoques. La presente investigación aplica al caso de los polígonos irregulares, un método para generar hiperheurísticas basado en un algoritmo genético (AG) que ha probado ser eficaz para el problema de corte de figuras rectangulares. Este método es llamado GHH-2D y fue descrito por Terashima-Mar ́ın [28] y Farías [14].Al generalizar el modelo GHH-2D a polígonos irregulares se incrementa la complejidad geométrica; por ejemplo: el cálculo de áreas, intersecciones, desplazamientos y rotaciones. El AG usa una representación de longitud variable que evoluciona combi-naciones de reglas del tipo condición-acción. Las condiciones de cada regla representan posibles estados de un problema mediante un vector de 8 números reales. Esta representación toma en cuenta el porcentaje de piezas que faltan por acomodar, la altura, el área y la rectangularidad de las piezas que faltan por acomodar. Gomes y Oliveira[19] definen rectangularidad con base en la diferencia entre el área de la pieza y el área del rectángulo que la contiene. Las acciones de cada regla indican heurísticas simples que encuentran una solución al problema de corte y empacado de material en dos dimensiones. La función primordial del AG es la de seleccionar diferentes estados del problema y asociar cada uno de ellos con alguna de las cuarenta acciones disponibles. Se realizaron experimentos donde el AG se evolución o durante 500 ciclos o generaciones. El mejor individuo del último ciclo constituye la hiperheurística generada la cual relaciona distintos estados del problema con heurísticas simples convenientes, de tal modo que al resolver una instancia utilizando las reglas de la hiperheurística se obtienen, en promedio, mejores resultados que empleando cualquiera de las heurísticas simples de manera exclusiva. El modelo desarrollado considera instancias con polígonos convexos de tres a ocho lados que deberán acomodarse en el menor número de objetos rectangulares idénticos. Para probar el modelo propuesto se generaron aleatoriamente 540 instancias, además de una instancia documentada en la literatura que incluye sólo figuras convexas. Se realizaron cuatro experimentos donde las instancias se dividen enconjuntos de entrenamiento y prueba. En cada experimento, se desarrollo una hiperheurística a partir de los problemas de entrenamiento y posteriormente se utilizó la hiperheurística generada para resolver las instancias de prueba. Se obtuvieron muy aceptables resultados, pues la hiperheurística desarrollada resolvió las instancias de prueba utilizando en promedio 1.38 objetos menos que el promedio de las 40 eucarísticas simples consideradas.