Pseudo-pyramidal Tours and Efficient Solvability of the Euclidean Generalized Traveling Salesman Problem in Grid Clusters

摘要

Generalized Traveling Salesman Problem (GTSP) is a well-known combinatorial optimization problem having numerous applications in operations research. For a given edge-weighted graph and a partition of its nodeset onto k (disjoint) clusters it is required to find a minimum cost cyclic tour visiting all the clusters once. The problem is strongly NP-hard even in the Euclidean plane provided the number of clusters is a part of the instance. Recently we proposed efficient optimal algorithms for GTSP based on quasi- and pseudo-pyramidal tours. As a consequence, we proved polynomial time solvability of the Euclidean GTSP in Grid Clusters defined by a grid of height at most 2. In this short paper, we show how to extend this result to the case defined by grids of an arbitrary fixed height.