Aplicación de CMSA al problema de empaquetado con desbordamiento

Resumen

En este trabajo se presenta una primera aplicación del algoritmo Construct, Merge, Solve & Adapt (CMSA) al problema de empaquetado con desbordamiento (OBPP, del inglés Overflowing Bin Packing Problem), un problema de optimización combinatoria recientemente introducido en el que el objetivo es minimizar la suma total de la infrautilización y sobreutilización de un conjunto de contenedores con capacidades heterogéneas. Para la resolución de las subinstancias generadas por CMSA se emplea el modelo de flujo en red (arcflow) propuesto por Martinovic y Strasdat, que constituye el estado del arte en resolución exacta del problema. El ajuste de parámetros se realiza mediante la herramienta irace sobre un subconjunto de instancias representativas extraídas de los conjuntos de referencia más competitivos. Los resultados computacionales obtenidos sobre un amplio conjunto de benchmarks muestran que CMSA alcanza la solución óptima en la totalidad de las instancias de los conjuntos Crainic, Dragone y Hemmelmayr, mientras que los conjuntos Belov, MS1 y MS2, caracterizados por su mayor tamaño y dificultad, suponen un reto significativo con desviaciones considerables respecto a los valores óptimos conocidos. Estos resultados sugieren que el modelo de flujo, aunque teóricamente robusto, puede resultar excesivamente complejo para la resolución eficiente de subinstancias dentro de CMSA, lo que motiva como trabajo futuro su sustitución por una formulación basada en cobertura de conjuntos, así como el diseño de operadores de búsqueda local específicos para el problema.

Publicación
XVII Congreso Español de Metaheurísticas, Algoritmos Evolutivos y Bioinspirados (MAEB 2026), XXI Conferencia de la Asociación Española para la Inteligencia Artificial