Solving the equality generalized traveling salesman problem using the Lin-Kernighan-Helsgaun algorithm

DOI10.1007/s12532-015-0080-8zbMath1327.90259OpenAlexW2163557644MaRDI QIDQ499157

Keld Helsgaun

Publication date: 30 September 2015

Published in: Mathematical Programming Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s12532-015-0080-8

zbMATH Keywords

heuristicstraveling salesman problemarc routing problemse-gtspequality generalized traveling salesman problemlin-kernighantsp

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (15)

Optimal routing in problemsof sequential traversal of megapolises in the presence of constraints ⋮ GLNS: an effective large neighborhood search heuristic for the generalized traveling salesman problem ⋮ Gotta (efficiently) catch them all: Pokémon GO meets orienteering problems ⋮ A transformation technique for the clustered generalized traveling salesman problem with applications to logistics ⋮ 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 ⋮ Temperature field optimization for laser powder bed fusion as a traveling salesperson problem with history ⋮ The single robot line coverage problem: Theory, algorithms, and experiments ⋮ A Heuristic Approach for Cluster TSP ⋮ Continuous relaxations for the traveling salesman problem ⋮ Improving dynamic programming for travelling salesman with precedence constraints: parallel Morin–Marsten bounding ⋮ Memetic algorithm-based path generation for multiple Dubins vehicles performing remote tasks

Uses Software

• TSPLIB
• LKH
• DIMACS
• GTSP Instances Library

Cites Work

• Efficient local search algorithms for known and new neighborhoods for the generalized traveling salesman problem
• Lin-Kernighan heuristic adaptations for the generalized traveling salesman problem
• A memetic algorithm for the generalized traveling salesman problem
• General \(k\)-opt submoves for the Lin-Kernighan TSP heuristic
• Transformations of generalized ATSP into ATSP.
• New results on the windy postman problem
• Zigzag inequalities: a new class of facet-inducing inequalities for arc routing problems
• 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
• Exact solution of the generalized routing problem through graph transformations
• Numerical Solution of the Navier-Stokes Equations
• The Traveling-Salesman Problem and Minimum Spanning Trees
• An Effective Heuristic Algorithm for the Traveling-Salesman Problem
• Computational Evaluation Of A Transformation Procedure For The Symmetric Generalized Traveling Salesman Problem
• Unnamed Item

This page was built for publication: Solving the equality generalized traveling salesman problem using the Lin-Kernighan-Helsgaun algorithm