F. Parreño Torres, R. Alvarez-Valdes, M. T. Alonso Martínez
El problema del corte del vidrio propuesto para el desafío ROADEF 2018 incluye algunas restricciones que impiden la aplicación directa de los procedimientos desarrollados para los problemas clásicos de corte. Por un lado, los tableros a cortar tienen defectos que los hacen únicos y deben ser utilizados en un orden determinado. Por otro lado, las piezas son agrupados en pilas y las piezas de cada pila deben ser cortadas en orden. Otro requisito adicional es que los cortes deben ser de tipo guillotina en tres etapas.
Hemos desarrollado un algoritmo de búsqueda acotado "beam search", utilizando una estructura de árbol en la que en cada nivel la solución parcial se incrementa añadiendo nuevos elementos a la solución hasta que se construye una solución completa. Hemos desarrollado un algoritmo constructivo y hemos explorado varias alternativas para la evaluación local y global de las soluciones. El estudio computacional muestra la eficacia del algoritmo propuesto en la competición.
Keywords: Beam Search, corte y empaquetamiento, optimización, heurísticas
Scheduled
GT9-2 Heuristics
September 4, 2019 12:00 PM
I3L9. Georgina Blanes building