Gutin, Gregory, Ben-Arieh, D., Penn, M., Yeo, Anders and Zverovitch, A. (2003) Transformations of generalized ATSP into ATSP. Operations Research Letters, 31 (5).
Full text access: Open
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.
This is a Submitted version This version's date is: 2003 This item is not peer reviewed
https://repository.royalholloway.ac.uk/items/bb7a2b02-c663-feaf-7552-1e548db29327/5/
Deposited by Research Information System (atira) on 03-Jul-2014 in Royal Holloway Research Online.Last modified on 03-Jul-2014