A hybrid genetic–GRASP algorithm using Langrangean relaxation for the traveling salesman problem

A hybrid genetic–GRASP algorithm using Langrangean relaxation for the traveling salesman problem

0.00 Avg rating0 Votes
Article ID: iaor20061429
Country: Netherlands
Volume: 10
Issue: 4
Start Page Number: 311
End Page Number: 320
Publication Date: Dec 2005
Journal: Journal of Combinatorial Optimization
Authors: , ,
Keywords: heuristics
Abstract:

Hybridization techniques are very effective for the solution of combinatorial optimization problems. This paper presents a genetic algorithm based on Expanding Neighborhood Search technique for the solution of the traveling salesman problem: The initial population of the algorithm is created not entirely at random but rather using a modified version of the Greedy Randomized Adaptive Search Procedure. Furthermore, a stopping criterion based on Lagrangean Relaxation is proposed. The combination of these difference techniques produces high quality solutions. The proposed algorithm was tested on numerous benchmark problems from TSPLIB with very satisfactory results. Comparisons with the algorithms of the DIMACS Implementation Challenge are also presented.

Reviews

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