The non-disjoint Clustered Traveling Salesperson Problem

Abstract

The traveling salesperson problem (TSP) has a long tradition in Operations Research and, thereby, is still relevant as the core and therefore important subproblem of decision problems in today's research. However, the TSP in its general form often lacks specific characteristics of the higher-level planning problems. For that reason, many extensions of the TSP have been developed over recent decades, allowing to consider additional constraints. The paper introduces the non-disjoint Clustered Traveling Salesperson Problem (ndCTSP), for which vertices are a member of at least one cluster. Having multiple non-disjoint clusters, a shortest tour is searched for, which enters each cluster at most once and only visits vertices in direct succession if they belong to the same (entered) cluster. Two variants of the problem are introduced, the unlimited and the limited version, for which the number of entered clusters is either unrestricted or bounded by a problem parameter, respectively. Theoretical insights, three different (mixed) integer linear programming formulations, and complexity results are provided. Further, the broad applicability and relevance of the novel problem are indicated by demonstrating how it generalizes three exemplarily selected planning problems from different domains. Computational tests on the solution performance of the proposed modeling approaches are provided for randomized instances to provide an unbiased evaluation. Finally, a first benchmark on structured instances of one of the generalized problems showcases that solving the ndCTSP outperforms specialized mixed integer models described in literature.