AN EFFICIENT TRANSFORMATION OF THE GENERALIZED TRAVELING SALESMAN PROBLEM INTO THE TRAVELING SALESMAN PROBLEM ON DIGRAPHS

The generalized traveling salesman problem (GTSP) is a generalization of the traveling salesman problem (TSP), one of the outstanding intrac table combinatorial optimization problems. In the GTSP problem, we are given n cities that are grouped into mutually disjoint districts (clu sters) and nonnegative distances between the cities in different distr icts. A traveling salesman has to find the shortest tour that visits e xactly one city in each district. In this paper, we study the asymmetr ic version of this problem, and describe a transformation by which an instance of the GTSP can be transformed into an instance of the asymme tric TSP with 2n cities. This compares favorably with the transformati on proposed by Lien and Ma in [5], in which the resulting TSP has more than 3n vertices. We show that any optimal solution of the TSP instan ce corresponds to a unique optimal solution of the GTSP instance of no greater length. Thus, the described transformation enables to solve t he GTSP by applying some of the numerous TSP's heuristics or optimal a pproaches. (C) Elsevier Science Inc. 1997.