Efficient local search algorithms for known and new neighborhoods for the generalized traveling salesman problem

DOI10.1016/j.ejor.2012.01.011zbMath1244.90196OpenAlexW1985225156MaRDI QIDQ439653

Daniel Karapetyan, Gregory Gutin

Publication date: 16 August 2012

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: http://repository.essex.ac.uk/22071/1/1005.5525v4.pdf

zbMATH Keywords

heuristicscombinatorial optimizationlocal searchneighborhoodgeneralized traveling salesman problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (9)

Lower bounding procedure for the asymmetric quadratic traveling salesman problem ⋮ Selective generalized travelling salesman problem ⋮ The bi-objective insular traveling salesman problem with maritime and ground transportation costs ⋮ A double-loop hybrid algorithm for the traveling salesman problem with arbitrary neighbourhoods ⋮ A transformation technique for the clustered generalized traveling salesman problem with applications to logistics ⋮ A branch-and-cut algorithm for the generalized traveling salesman problem with time windows ⋮ Precedence constrained generalized traveling salesman problem: polyhedral study, formulations, and branch-and-cut algorithm ⋮ New neighborhoods and an iterated local search algorithm for the generalized traveling salesman problem ⋮ Solving the equality generalized traveling salesman problem using the Lin-Kernighan-Helsgaun algorithm

Uses Software

• TSPLIB
• LKH
• GTSP Instances Library

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Local search heuristics for the multidimensional assignment problem
• Lin-Kernighan heuristic adaptations for the generalized traveling salesman problem
• An ensemble of discrete differential evolution algorithms for solving the generalized traveling salesman problem
• A random-key genetic algorithm for the generalized traveling salesman problem
• A memetic algorithm for the generalized traveling salesman problem
• A memetic algorithm with a large neighborhood crossover operator for the generalized traveling salesman problem
• General \(k\)-opt submoves for the Lin-Kernighan TSP heuristic
• An efficient composite heuristic for the symmetric generalized traveling salesman problem
• Transformations of generalized ATSP into ATSP.
• An effective implementation of the Lin-Kernighan traveling salesman heuristic
• The traveling salesman problem and its variations
• The Generalized Traveling Salesman Problem: A New Genetic Algorithm Approach
• A Lagrangian Based Approach for the Asymmetric Generalized Traveling Salesman Problem
• TSPLIB—A Traveling Salesman Problem Library
• An Efficient Transformation Of The Generalized Traveling Salesman Problem
• Some Applications of the Generalized Travelling Salesman Problem
• A Branch-and-Cut Algorithm for the Symmetric Generalized Traveling Salesman Problem
• The symmetric generalized traveling salesman polytope
• Computer Solutions of the Traveling Salesman Problem
• Computational Evaluation Of A Transformation Procedure For The Symmetric Generalized Traveling Salesman Problem

This page was built for publication: Efficient local search algorithms for known and new neighborhoods for the generalized traveling salesman problem