-

 

 

 




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

Citation:

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

 

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