GLNS: an effective large neighborhood search heuristic for the generalized traveling salesman problem

DOI10.1016/j.cor.2017.05.010zbMath1391.90535OpenAlexW2614564353MaRDI QIDQ1652391

Stephen L. Smith, Frank Imeson

Publication date: 11 July 2018

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cor.2017.05.010

zbMATH Keywords

traveling salesman problemadaptive large neighborhood searchgeneralized traveling salesman problemclustered traveling salesman

Mathematics Subject Classification ID

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

Related Items (18)

Evolutionary algorithm and multifactorial evolutionary algorithm on clustered shortest-path tree problem ⋮ Optimal routing in problemsof sequential traversal of megapolises in the presence of constraints ⋮ Selective generalized travelling salesman problem ⋮ Recent advances in selection hyper-heuristics ⋮ A transformation technique for the clustered generalized traveling salesman problem with applications to logistics ⋮ A survey of adaptive large neighborhood search algorithms and applications ⋮ Local branching relaxation heuristics for integer linear programs ⋮ Multi-armed bandit-based hyper-heuristics for combinatorial optimization problems ⋮ Heuristic approaches for the family traveling salesman problem ⋮ 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 ⋮ An adaptive memory matheuristic for the set orienteering problem ⋮ New neighborhoods and an iterated local search algorithm for the generalized traveling salesman problem ⋮ A novel algorithm for construction of the shortest path between a finite set of nonintersecting contours on the plane ⋮ The resource constrained clustered shortest path tree problem: Mathematical formulation and Branch&Price solution algorithm ⋮ Constant-factor approximation algorithms for a series of combinatorial routing problems based on the reduction to the asymmetric traveling salesman problem ⋮ GTSP-LIB ⋮ Solving the traveling delivery person problem with limited computational time

Uses Software

• Hyperheuristics
• SATLIB
• LKH
• GTSP Instances Library

Cites Work

• Unnamed Item
• Unnamed Item
• GRASP with path relinking for the symmetric Euclidean clustered traveling salesman problem
• An adaptive large neighborhood search heuristic for two-echelon vehicle routing problems arising in city logistics
• Solving the equality generalized traveling salesman problem using the Lin-Kernighan-Helsgaun algorithm
• Lin-Kernighan heuristic adaptations for the generalized traveling salesman problem
• A random-key genetic algorithm for the generalized traveling salesman problem
• A general heuristic for vehicle routing problems
• A memetic algorithm for the generalized traveling salesman problem
• A memetic algorithm with a large neighborhood crossover operator for the generalized traveling salesman problem
• 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
• An adaptive large neighborhood search for the discrete and continuous berth allocation problem
• An adaptive large neighborhood search heuristic for the cumulative capacitated vehicle routing problem
• The Generalized Traveling Salesman Problem: A New Genetic Algorithm Approach
• A Lagrangian Based Approach for the Asymmetric Generalized Traveling Salesman Problem
• An Analysis of Several Heuristics for the Traveling Salesman Problem
• 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
• Hyper-Heuristics: An Emerging Direction in Modern Search Technology
• A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem
• The symmetric generalized traveling salesman polytope
• On the Dubins Traveling Salesman Problem
• An Effective Heuristic Algorithm for the Traveling-Salesman Problem

This page was built for publication: GLNS: an effective large neighborhood search heuristic for the generalized traveling salesman problem