Análisis computacional de los problemas del vendedor viajero y patrones de corte

Resumen

En este artículo se presentan los resultados de un análisis computacional que evalúa el impacto de las formulaciones y estrategias de solución sobre el desempeño algorítmico en dos problemas clásicos de optimización: el problema del vendedor viajero y el problema de patrones de corte. Para analizar el desempeño algorítmico de las formulaciones en ambos problemas, se usan tres variables dependientes: calidad de la solución, tiempo de cómputo y número de iteraciones. Los resultados obtenidos sirven de base para elegir el enfoque de solución para cada problema específico. Para el STSP, los resultados demuestran que la formulación como un problema de inserción multietapa es más eficiente que las formulaciones clásicas, al resolver 90.47% de las instancias en comparación a MTZ (76.19%) y DFJ (14.28%). Los resultados para el CSP demuestran que la formulación extendida con variables por patrones es más eficiente que la formulación estándar con desigualdades para romper simetría, cuando la función objetivo modelada corresponde a minimizar la pérdida de material que se produce al realizar el corte de los rollos.