The Generalized Traveling Salesman Problem.
Charles E. Noon · Deep Blue (University of Michigan) · 1988
The Traveling Salesman Problem (TSP) seeks a minimum cost tour over the nodes of a directed graph. Applications of the TSP include sequencing tasks and movement in the areas of distribution, warehousing and scheduling. We study a generalization of this problem known as the Generalized Traveling Salesman Problem (GTSP). The canonical form of the GTSP is defined on a directed graph in which the nodes are grouped into predefined, mutually exclusive and exhaustive sets with the arcset containing no intraset arcs. The problem is to find a minimum cost tour over the sets of nodes which passes though each set exactly once. Our research aims to describe its modeling applications and present both optimal and heuristic solution approaches. In order to exp and the modeling applications of the GTSP, we define a general form of the problem. In the general form, we relax the condition of mutual exclusivity on the node sets and allow for some sets to be passed through more than once. The form also allows intraset arcs. We show that any problem in the general form can be efficiently transformed to a problem in the canonical form. The general form can describe a wide range of applications. We present a two-phase approach for determining an optimal solution to a problem in the canonical form. In the first phase, we compute lower and upper bounds on the total cost of an optimal solution. The bounds are obtained by solving assignment or TSP relaxations whose size depends only on the number of node sets. These bounds are used to identify and remove arcs and nodes which are guaranteed not to be in an optimal solution. This serves to remove a large number of arcs and nodes from further consideration, thus drastically reducing problem size. The second phase uses an efficient branch- and -bound procedure to exploit the multiple choice structure among the node sets of the canonical form. The procedure branches on the nodes of a problem, rather than arcs, and thus remains a manageable size. We present computational results for the two-phase optimal approach tested on a series of r and omly generated problems. The results show success on a wide range of problems with up to 300 nodes configured as 50 node sets with 6 nodes per set. The final phase of our research concerns the development and testing of six heuristic methods for solving the GTSP. The methods are tested on the same problems used in testing the optimal approach. The computational results show several of the methods to be robust in their ability to produce good solutions with less computation than is required for the optimal approach.