Application of the noising method to the travelling salesman problem

In this paper, we study the application of the noising method, a recent combinatorial optimization metaheuristic, to the Travelling Salesman Problem (TSP). We first detail the features of the noising method in order to adapt it to the TSP. Then we ‘experimentally’ compare it to the simulated annealing method, and we study its sensitiveness to different parameters involved in its design. Two types of TSPs have been considered: the randomly weighted TSP, for which the weights of the edges are randomly chosen, and the Euclidean TSP, for which the vertices belong to the Euclidean plane and where the weights of the edges are given by the Euclidean distances between the vertices.