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

ResumenEn 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.

The aim of this article is to perform a computational study to analyze the impact of formulations, and the solution strategy on the algorithmic performance of two classical optimization problems: the traveling salesman problem and the cutting stock problem. In order to assess the algorithmic performance on both problems three dependent variables were used: solution quality, computing time and number of iterations. The results are useful for choosing the solution approach to each specific problem. In the STSP, the results demonstrate that the multistage decision formulation is better than the conventional formulations, by solving 90.47% of the instances compared with MTZ (76.19%) and DFJ (14.28%). The results of the CSP demonstrate that the cutting patterns formulation is better than the standard formulation with symmetry breaking inequalities, when the objective function is to minimize the loss of trim when cutting the rolls.