Further Extension of TSP Assign Neighborhood

Gregory Gutin (guincs.rhul.ac.uk)
Fred Glover (Fred.Glovercolorado.edu)

Abstract: 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.

Keywords: traveling salesman problem; local search; exponential neighborhood; assign neighborhood

Category 1: Combinatorial Optimization

Category 2: Integer Programming

Category 3: Network Optimization

Citation:

Download: [PDF]

Entry Submitted: 01/04/2005
Entry Accepted: 01/04/2005
Entry Last Modified: 01/04/2005

Modify/Update this entry