A Lagrangian Based Approach for the Asymmetric Generalized Traveling Salesman Problem

Abstract

This paper presents an optimal approach for the asymmetric Generalized Traveling Salesman Problem (GTSP). The GTSP is defined on a directed graph in which the nodes are grouped into m predefined, mutually exclusive and exhaustive sets with the arc set containing no intraset arcs. The problem is to find a minimum cost m-arc directed cycle which includes exactly one node from each set. Our approach employs a Lagrangian relaxation to compute a lower bound on the total cost of an optimal solution. The lower bound and a heuristically determined upper bound are used to identify and remove arcs and nodes which are guaranteed not to be in an optimal solution. Finally, we use an efficient branch-and-bound procedure which exploits the multiple choice structure of the node sets. We present computational results for the optimal approach tested on a series of randomly generated problems. The results show success on a range of problems with up to 104 nodes.