Operations Research 2025
Abstract Submission

178. The non-disjoint Clustered Traveling Salesperson Problem

Invited abstract in session TD-3: Workforce Scheduling and Routing, stream Project Management and Scheduling.

Thursday, 14:30-16:00
Room: H5

Authors (first author is the speaker)

1. Felix Weidinger
Technical University of Darmstadt
2. Kris Braekers
Research Group Logistics, Hasselt University

Abstract

The talk is introducing the non-disjoint Clustered Traveling Salesperson Problem (ndCTSP). For the classical Clustered Traveling Salesperson Problem (CTSP) all vertices of a graph are assigned exactly one cluster. All vertices of the same cluster then need to be visited in direct succession before a subsequent cluster can be entered; therefore, nodes within each cluster as well as the clusters themselves need to be sequenced (see Chisman (1975): The clustered traveling salesman problem. Computers & Operations Research, 2(2), 115-119). For the ndCTSP, however, vertices can be assigned several clusters, of which not all need to be considered, i.e., activated, in a solution. As a consequence of the many-to-many relation, not all vertices of an activated cluster have to be visited contiguously, as they can be included into the tour later or might be already part of the tour via another cluster they belong to. Hereby, however, each cluster can be activated at most once and the tour has to be enclosed in activated clusters, i.e., the active cluster can only be switched in a vertex belonging to the previously and successively activated cluster. In the talk, two versions of ndCTSP are defined and analyzed regarding their problem specifications and complexity status. Different integer programs are introduced and compared in a computational study making use of off-the-shelf solver Gurobi. Finally, relations of the ndCTSP to other planning problems are detailed, positioning the ndCTSP as a generalization of planning problems from different domains, as, for example, warehousing.

Keywords

Status: accepted

Back to the list of papers