Further Extension of the TSP Assign Neighborhood

We introduce a new extension of Punnen's exponential neighborhood for the traveling salesman problem (TSP). In contrast to an interesting generalization of Punnen's neighborhood by De Franceschi, Fischetti, and Toth (2005), our neighborhood is searchable in polynomial time, a feature that invites exploitation by heuristic and metaheuristic procedures for the TSP and related problems, including those of De Franceschi, Fischetti, and Toth (2005) for the vehicle routing problem. Research of GG was partially supported by Leverhulme Trust and by the IST Programme of the European Community, under the PASCAL Network of Excellence, IST-2002–506778.