Transformations of generalized asymmetric traveling salesman problems into simple asymmetric traveling salesman problems

Transformations of generalized asymmetric traveling salesman problems into simple asymmetric traveling salesman problems

0.00 Avg rating0 Votes
Article ID: iaor20041248
Country: Netherlands
Volume: 31
Issue: 5
Start Page Number: 357
End Page Number: 365
Publication Date: Sep 2003
Journal: Operations Research Letters
Authors: , , , ,
Keywords: combinatorial analysis
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.

Reviews

Required fields are marked *. Your email address will not be published.