Generalized Traveling Salesman Problem


The symmetric Generalized Travelling Salesman Problem (GTSP) is a variant of the classical symmetric Travelling Salesman Problem, in which the nodes are partitioned into clusters and the salesman has to visit at least one node for each cluster. A different version of the problem, called E-GTSP, arises when exactly one node for each cluster has to be visited. Both GTSP and E-GTSP are NP-hard problems, and find practical applications in routing and scheduling. In a paper we model GTSP and E-GTSP as integer linear programs, and study the facial structure of the corresponding polytopes. In another paper the previous results have been used to design a branch-and-cut algorithm for the exact solution of instances up to 442 nodes.

My contributions with P. Toth and M. Fischetti are:


  • The Symmetric Generalized Traveling Salesman Polytope, Networks 26 (1995) 113-123.

  • A Branch-and-Cut Algorithm for the Symmetric Generalized Traveling Salesman Polytope, Operations Research 45/3 (1997) 378-394.