Graphical Traveling Salesman Problem With Release Dates in Path-like Graphs: Algorithms and Complexity

Abstract

In this dissertation, we investigates the Graphical Traveling Salesman Problem with Release Dates (GTSP-rd), a generalization of the classical NP-hard TSP in which each vertex has an associated release date, the earliest time a vertex becomes available to be served. Unlike the traditional approach of transforming the input into a complete graph, the GTSP-rd is solved directly on the original graph, preserving structural properties that may admit more efficient algorithms for special cases. Motivated by real-world applications such as logistics in grid-based warehouses, rural road networks, and sameday express deliveries in general, this work aims to determine for which graph classes the GTSP-rd can be solved in polynomial time. Based on previous polynomial-time results for path graphs and a few other structures, this research focuses on Path-like graphs, including paths, cycles, stars, caterpillars, lobsters, and subdivided stars. Thus, this work provides: (i) a precise and explicit formulation of the GTSP-rd, filling gaps in the existing literature; (ii) improved linear and near-linear algorithms for paths with the depot at an extremity; (iii) new polynomial-time dynamic programming algorithms for general paths, stars, and cycles; and (iv) structural insights and partial results for caterpillar, lobster and subdivided stars. Overall, this work advances the understanding of how graph structure influences the computational complexity of the GTSP-rd, expands the set of graph classes known to admit polynomial-time solutions, and establishes new theoretical insights that may support further progress toward a broader characterization of other tractable cases.