New neighborhoods and an iterated local search algorithm for the generalized traveling salesman problem

For a given graph with a vertex set that is partitioned into clusters, the generalized traveling salesman problem (GTSP) is the problem of finding a cost-minimal cycle that contains exactly one vertex of every cluster. We introduce three new GTSP neighborhoods that allow the simultaneous permutation of the sequence of the clusters and the selection of vertices from each cluster. The three neighborhoods and some known neighborhoods from the literature are combined into an effective iterated local search (ILS) for the GTSP. The ILS performs a straightforward random neighborhood selection within the local search and applies an ordinary record-to-record ILS acceptance criterion. The computational experiments on four symmetric standard GTSP libraries show that, with some purposeful refinements, the ILS can compete with state-of-the-art GTSP algorithms. (c) 2022 The Author(s). Published by Elsevier Ltd on behalf of Association of European Operational Research Societies (EURO). This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/).

Automated summary

The generalized traveling salesman problem (GTSP) aims to find a minimum-cost cycle in a given graph that contains exactly one vertex from each cluster. This study introduces three new GTSP neighborhoods that allow for simultaneous permutation of cluster sequence and vertex selection. These neighborhoods, along with existing ones from literature, are combined to form an effective iterated local search (ILS) algorithm for GTSP. Computational experiments on standard GTSP libraries demonstrate that the ILS algorithm, with some refinements, can compete with state-of-the-art GTSP algorithms.