Small Diameter Neighbourhood Graphs for the Traveling Salesman Problem: At Most Four Moves From Tour to Tour

A neighbourhood N (T ) of a tour T (in the TSP with n cities) is polynomially searchable if the best among tours in N (T ) can be found in time polynomial in n. Using Punnen's neighbourhoods introduced in 1996, we construct polynomially searchable neighbourhoods of exponential size satisfying the following property: for any pair of tours T 1 and T 5 , there exist tours T 2 ; T 3 and T 4 such that T i is in the neighbourhood of T i\Gamma1 for all i = 2; 3; 4; 5: In contrast, for pyramidal neighbourhoods considered by J. Carlier and P. Villon (1990), one needs up to \Theta(log n) intermediate tours to 'move' from a tour to another one. 1 Introduction Let DK n be a weighted complete directed graph on n vertices (the weights are assigned to the edges). In the asymmetric traveling salesman problem (TSP) one seeks for a hamiltonian directed cycle (called a tour) of DK n of minimum total weight. Local search based heuristics and metaheuristics have been the most effective and efficient tool ..