A Multistart Heuristic for the Equality Generalized Traveling Salesman Problem

We study the Generalized Traveling Salesman Problem (GTSP), which is a variant of the well-known Traveling Salesman Problem. We are given an undirected graph G=(V,E), with set of nodes V and set of edges E, each with an associated cost. The set of nodes is partitioned into clusters. We focus on the so-called E-GTSP, where "E" stands for "Equality". E-GTSP is to find an elementary cycle visiting exactly one node for each cluster, and minimizing the sum of the costs of the traveled edges. We propose a multi-start heuristic algorithm, which iteratively starts with a randomly chosen set of nodes and applies a decomposition approach combined with improvement procedures. The decomposition approach considers a first phase to determine the visiting order of the clusters and a second phase to find the corresponding minimum cost cycle. We show the effectiveness of the proposed approach on benchmark instances from the literature.