Transformations of generalized ATSP into ATSP

Abstract

The generalized traveling salesman problem (GTSP) is stated as follows. Given a weighted complete digraph Kn* and a partition V1,…,Vk of its vertices, find a minimum weight cycle containing exactly one vertex from each set Vi, i=1,…,k. We study transformations from GTSP to TSP. The ‘exact’ Noon–Bean transformation is investigated in computational experiments. We study the ‘non-exact’ Fischetti–Salazar–Toth (FST) transformation and its two modifications in computational experiments and theoretically using domination analysis. One of our conclusions is that one of the modifications of the FST transformation is better than the original FST transformation in the worst case in terms of domination analysis.