New Formulations for the Generalized Traveling Salesman Problem

摘要

The Generalized Traveling Salesman Problem (GTSP) is an extension of the well known Traveling Salesman Problem (TSP). The GTSP is defined on a graph in which the nodes (customers or vertices) are grouped into a given number of clusters (node sets). Solution procedures for the GTSP are generally focused on transforming the problem to the TSP and applying the exact or heuristic solution methods developed for the TSP. There exist a few integer programming formulations for the GTSP some of which are exponential size with respect to number of the nodes. In this paper, we propose two new formulations for the GTSP with polynomial size with respect to number of the nodes. For preliminary computational analysis, GTSP instances from TSPLIB are solved by proposed formulations and also by the previously existing formulations in the literature. Performances of the formulations in terms of linear programming relaxations and CPU times are analyzed. We observe that, performances of the proposed formulations are better than the existing formulations in terms of these two evaluation criteria.