Multiple phase neighborhood search---GRASP based on Lagrangean relaxation, random backtracking Lin-Kernighan and path relinking for the TSP

DOI10.1007/s10878-007-9104-2zbMath1180.90274OpenAlexW2080831875MaRDI QIDQ841596

Athanasios Migdalas, Panos M. Pardalos, Yannis Marinakis

Publication date: 18 September 2009

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-007-9104-2

zbMATH Keywords

TSPmetaheuristicsGRASPENSLagrangean relaxation and subgradient optimization

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items

A new bilevel formulation for the vehicle routing problem and a solution method using a genetic algorithm, A particle swarm optimization algorithm with path relinking for the location routing problem, Honey bees mating optimization algorithm for large scale vehicle routing problems, Bilayer local search enhanced particle swarm optimization for the capacitated vehicle routing problem

Uses Software

• TSPLIB
• LKH
• Scatter Search

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The traveling salesman problem: An overview of exact and approximate algorithms
• An effective implementation of the Lin-Kernighan traveling salesman heuristic
• The traveling salesman problem and its variations
• Greedy randomized adaptive search procedures
• A new bilevel formulation for the vehicle routing problem and a solution method using a genetic algorithm
• A particle swarm optimization algorithm with path relinking for the location routing problem
• Expanding neighborhood GRASP for the traveling salesman problem
• A hybrid genetic-GRASP algorithm using Lagrangean relaxation for the traveling salesman problem
• Chained Lin-Kernighan for Large Traveling Salesman Problems
• Fast Algorithms for Geometric Traveling Salesman Problems
• Scatter Search and Path Relinking: Advances and Applications
• Computer Solutions of the Traveling Salesman Problem
• An Effective Heuristic Algorithm for the Traveling-Salesman Problem
• Variable neighborhood search: Principles and applications