Statistical Analysis of Some Traveling Salesman Algorithms

摘要

This paper reports the results of a statistical analysis of the performance of three branch and bound algorithms for the general (asymmetric) traveling salesman problem on randomly generated test problems with up to 325 cities. Three types of functions, polynomial, superpolynomial (long-exponential) and exponential, were fitted to the performance data of each of the algorithms by least squares techniques. The three functions describe almost equally well the behavior of the algorithms in the range of problem sizes examined.