Small diameter neighbourhood graphs for the traveling salesman problem: atmost 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 polyn omially searchable neighbourhoods of exponential size satisfying the follow ing 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 Ti-1 for all i = 2, 3, 4, 5. In contrast, for pyramidal neighbourhoods considered by Carlier and Vil lon (1990, RAIRO 24, 245-253), one needs up to Theta(log n) intermediate te ars to 'move' from a tour to another one. (C) 1999 Elsevier Science Ltd. Al l rights reserved.