New Neighborhoods and an Iterated Local Search Algorithm for the Generalized Traveling Salesman Problem

The generalized traveling salesman problem (GTSP) is the problem of finding a cost-minimal cycle in a clustered graph so that exactly one vertex of every cluster is contained in the cycle. 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 a simple but effective iterated local search (ILS) for the GTSP. The simplicity of the ILS consists in its straightforward random neighborhood selection within the local search and an ordinary record-to-record ILS acceptance criterion. The computational experiments on four symmetric standard GTSP libraries show that, with some small refinements, the ILS can compete with state-of-the-art algorithms, although it is simple in structure and less involved to code compared to many other metaheuristics.