A hybrid genetic algorithm for the Generalized Traveling Salesman Problem
Daniel De Ladurantaye · 2001
The Generalized Traveling Salesman Problem consists of determining a shortest tour on a graph passing through each of several clusters of vertices. A hybrid genetic algorithm (GA) is developed to solve a variant of this problem where exactly one vertex must be visited in each cluster. In this algorithm, the GA searches for a good selection of vertices, while classical operations research techniques are used to produce a tour with the selected vertices. Numerical results are reported on a standard set of benchmark problems and a comparison is provided with the two best heuristics reported in the literature.