A dynamic programming methodology in very large scale neighborhood search applied to the traveling salesman problem

A dynamic programming methodology in very large scale neighborhood search applied to the traveling salesman problem

0.00 Avg rating0 Votes
Article ID: iaor2007463
Country: Netherlands
Volume: 3
Issue: 1
Start Page Number: 78
End Page Number: 85
Publication Date: Mar 2006
Journal: Discrete Optimization
Authors: ,
Keywords: programming: dynamic, heuristics
Abstract:

We consider the standard dynamic program to solve the TSP. We then obtain exponentially large neighborhoods by selecting a polynomially bounded number of states, and restricting the dynamic program to those states only. We show how the Balas and Simonetti neighborhood and the insertion dynasearch neighborhood can be viewed in this manner. We also show that one of the dynasearch neighborhoods can be derived directly from the 2-exchange neighborhood using this approach.

Reviews

Required fields are marked *. Your email address will not be published.