Guided local search and its application to the traveling salesman problem

Guided local search and its application to the traveling salesman problem

0.00 Avg rating0 Votes
Article ID: iaor20001854
Country: Netherlands
Volume: 113
Issue: 2
Start Page Number: 469
End Page Number: 499
Publication Date: Mar 1999
Journal: European Journal of Operational Research
Authors: ,
Keywords: heuristics
Abstract:

The Traveling Salesman Problem (TSP) is one of the most famous problems in combinatorial optimization. In this paper, we are going to examine how the techniques of Guided Local Search (GLS) and Fast Local Search (FLS) can be applied to the problem. GLS sits on top of local search heuristics and has as a main aim to guide these procedures in exploring efficiently and effectively the vast search spaces of combinatorial optimization problems. GLS can be combined with the neighborhood reduction scheme of FLS which significantly speeds up the operations of the algorithm. The combination of GLS and FLS with TSP local search heuristics of different efficiency and effectiveness is studied in an effort to determine the dependence of GLS on the underlying local search heuristic used. Comparisons are made with some of the best TSP heuristic algorithms and general optimization techniques which demonstrate the advantages of GLS over alternative heuristic approaches suggested for the problem.

Reviews

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