Some exchange operators and a relaxation method for the Travelling Salesman Problem

The paper gives a new approach to find acceptable low-cost minima for the Travelling Salesman Problem, in a metric space. It introduces a new relaxation method, and above all the paper uses topological criteria to define the exchange operators. This approach leads to a new algorithm better than Lin-Kerninghan algorithm. For a 532 cities path, the average accuracy is 1% and the best result is the true optimum. Running times grow empirically as O(N¹’.⁵).