A novel reduction algorithm for the generalized traveling salesman problem
Mehdi El Krari, Belaïd Ahiod, Bouazza Elbenani · Proceedings of the Genetic and Evolutionary Computation Conference Companion · 2017
The Generalized Traveling Salesman Problem (GTSP) is a Combinatorial Optimization Problem considered as a generalization of the well known Traveling Salesman Problem. The GTSP, which is an NP-Hard problem, consists of visiting only one city/node from each region/cluster from all given clusters of an instance. This paper introduces a new reduction method that removes "farthest" cities from other clusters and keeps the nearest ones. Experimental tests done on 81 instances from the TSPLIB benchmark present a reduction rate from 9 to 73%. The runtime is almost less than one second for most instances and doesn't exceed 7 for the larger ones.