A neighbourhood N(T) of a tour T (in the travelling salesman problem (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 T1 and T5, there exist tours T2, T3 and T4 such that T1 is in the neighbourhood of Ti – 1 for all i = 2, 3, 4, 5. In contrast, for pyramidal neighbourhoods considered by Carlier and Villon, one needs up to Θ(log n) intermediate tours to ‘move’ from a tour to another one.
