A hybrid genetic : GRASP algorithm using lagrangean relaxation for the traveling salesman problem

Hybridization techniques are very effective for the solution of combinatorial optimization problems. This paper presents a genetic algorithm based on Expanding Neighborhood Search technique (Marinakis, Migdalas, and Pardalos, Computational Optimization and Applications, 2004) for the solution of the...

Full description

Saved in:
Bibliographic Details
Published in:Journal of combinatorial optimization 2005-12, Vol.10 (4), p.311-326
Main Authors: MARINAKIS, Yannis, MIGDALAS, Athanasios, PARDALOS, Panos M
Format: Article
Language:English
Subjects:
Applied sciences
Exact sciences and technology
Flows in networks. Combinatorial problems
Industrial Logistics
Industriell logistik
Operational research and scientific management
Operational research. Management science
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Hybridization techniques are very effective for the solution of combinatorial optimization problems. This paper presents a genetic algorithm based on Expanding Neighborhood Search technique (Marinakis, Migdalas, and Pardalos, Computational Optimization and Applications, 2004) 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. Farther more a stopping criterion based on Lagrangean Relaxation is proposed. The combination of these different 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
ISSN:1382-6905
1573-2886
1573-2886
DOI:10.1007/s10878-005-4921-7