Optimization Online


Further Extension of TSP Assign Neighborhood

Gregory Gutin (guin***at***cs.rhul.ac.uk)
Fred Glover (Fred.Glover***at***colorado.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


Download: [PDF]

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

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society