A Computational Analysis of the Traveling Salesman and Cutting Stock Problems

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