Lin-Kernighan heuristic adaptations for the generalized traveling salesman problem

DOI10.1016/j.ejor.2010.08.011zbMath1208.90148OpenAlexW2065862878MaRDI QIDQ621685

Gregory Gutin, Daniel Karapetyan

Publication date: 28 January 2011

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

Full work available at URL: https://doi.org/10.1016/j.ejor.2010.08.011

zbMATH Keywords

heuristicscombinatorial optimizationgeneralized traveling salesman problemLin-Kernighan

Mathematics Subject Classification ID

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

Related Items

Integer programming models and branch-and-cut approaches to generalized \(\{0,1,2\}\)-survivable network design problems, Selective generalized travelling salesman problem, A meta-heuristic based goal-selection strategy for mobile robot search in an unknown environment, GLNS: an effective large neighborhood search heuristic for the generalized traveling salesman problem, Layered graph models and exact algorithms for the generalized hop-constrained minimum spanning tree problem, Reducing the size of combinatorial optimization problems using the operator vaccine by fuzzy selector with adaptive heuristics, A Discrete State Transition Algorithm for Generalized Traveling Salesman Problem, A transformation technique for the clustered generalized traveling salesman problem with applications to logistics, New neighborhoods and an iterated local search algorithm for the generalized traveling salesman problem, Efficient local search algorithms for known and new neighborhoods for the generalized traveling salesman problem, Solving the equality generalized traveling salesman problem using the Lin-Kernighan-Helsgaun algorithm, A construction for directed in-out subgraphs of optimal size, A polynomial matrix processing heuristic algorithm for finding high quality feasible solutions for the TSP

Uses Software

• TSPLIB
• GTSP Instances Library

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• A new relaxation method for the generalized minimum spanning tree problem
• The Generalized Traveling Salesman Problem: A New Genetic Algorithm Approach
• Local Search Heuristics for the Multidimensional Assignment Problem
• A Lagrangian Based Approach for the Asymmetric Generalized Traveling Salesman Problem
• An Algorithm for the Three-Index Assignment 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
• An Effective Heuristic Algorithm for the Traveling-Salesman Problem
• Computational Evaluation Of A Transformation Procedure For The Symmetric Generalized Traveling Salesman Problem