GTSP-LIB swMATH ID: 25565 Software Authors: Smith, Stephen L.; Imeson, Frank Description: GLNS: an effective large neighborhood search heuristic for the generalized traveling salesman problem. This paper presents a new solver for the exactly one-in-a-set generalized traveling salesman problem (GTSP). In the GTSP, a complete directed graph with edge weights is given as input along with a partition of the vertices into disjoint sets. The objective is to find a cycle (or tour) in the graph that visits each set exactly once and has minimum length. In this paper, we present an effective algorithm for the GTSP based on an adaptive large neighborhood search. The algorithm operates by repeatedly removing from, and inserting vertices in the tour. We propose a general insertion mechanism that contains, as special cases, the well-known nearest, farthest and random insertion mechanisms. We provide extensive benchmarking results for our solver in comparison to the state-of-the-art on a wide range of existing and new problem libraries. We show that on the GTSP-LIB library, the proposed algorithm is competitive with the best known algorithms. On several other libraries. We show that given the same amount of time, the proposed solver finds higher quality solutions than existing approaches, particularly on harder instances that are non-metric and/or whose sets are not clustered. Homepage: https://www.sciencedirect.com/science/article/pii/S0305054817301223 Keywords: generalized traveling salesman problem; traveling salesman problem; adaptive large neighborhood search; clustered traveling salesman Related Software: GTSP Instances Library; LKH; Hyperheuristics; TSPLIB; GOAL; Hyperion; jMetal; irace; HyFlex; Knapsack; PISA; SATLIB Cited in: 6 Publications Standard Articles 1 Publication describing the Software, including 1 Publication in zbMATH Year GLNS: an effective large neighborhood search heuristic for the generalized traveling salesman problem. Zbl 1391.90535Smith, Stephen L.; Imeson, Frank 2017 all top 5 Cited by 20 Authors 1 Baniasadi, Pouya 1 Binh, Huynh Thi Thanh 1 Burke, Edmund Kieran 1 Cattaruzza, Diego 1 Derya, Tusan 1 Dinler, Esra 1 Drake, John H. 1 Ezhov, Vladimir Vladimirovich 1 Foumani, Mehdi 1 Hanh, Phan Thi Hong 1 Imeson, Frank 1 Keçeci, Bariş 1 Kheiri, Ahmed 1 Ogier, Maxime 1 Ozcan, Ender 1 Semet, Frédéric 1 Smith-Miles, Kate A. 1 Smith, Stephen L. 1 Thanh, Pham Dinh 1 Yuan, Yuan Cited in 4 Serials 3 European Journal of Operational Research 1 Information Sciences 1 Computers & Operations Research 1 Mathematical and Computer Modelling of Dynamical Systems Cited in 2 Fields 6 Operations research, mathematical programming (90-XX) 2 Computer science (68-XX) Citations by Year