An Efficient Transformation Of The Generalized Traveling Salesman Problem

Abstract

The Generalized Traveling Salesman Problem (GTSP) is a useful model for problems involving decisions of selection and sequence. The problem is defined on a directed graph in which the nodes have been pregrouped into m mutually exclusive and exhaustive nodesets. Arcs are defined only between nodes belonging to different nodesets with each arc having an associated cost. The GTSP is the problem of finding a minimum cost m-arc directed cycle which includes exactly one node from each nodeset. In this paper, we show how to efficiently transform a GTSP into a standard asymmetric Traveling Salesman Problem (TSP) over the same number of nodes. The transformation allows certain routing problems which involve discrete alternatives to be modeled using the TSP framework. One such problem is the heterogenous Multiple Traveling Salesman Problem (MTSP) for which we provide a GTSP formulation.