The non-disjoint Clustered Traveling Salesperson Problem
提出非不相交聚类旅行商问题，每个顶点至少属于一个聚类，寻找最短路径，每个聚类最多进入一次，仅当顶点属于同一聚类时才连续访问。
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.