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

Loading...
Thumbnail Image

Co-advisor(s)

Committee members

Moura, Edleno Silva de Moura
Delle-Done, Diego
Ravelo, Santiago Valdés

Journal Title

Journal ISSN

Volume Title

Publisher

Universidade Federal do Amazonas

Access rights

DOI

Resumo (Portuguese)

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.

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.

Description

Controlled term

Sustainable Development Goals (SDG)

Citation

ANDRADE, Thailsson Clementino de. Graphical Traveling Salesman Problem With Release Dates in Path-like Graphs: Algorithms and Complexity. 2026. 74 f. Dissertação (Mestrado em Informática) - Universidade Federal do Amazonas, Manaus (AM), 2026.

Endorsement

Review

Supplemented By

Referenced By

Creative Commons license

Except where otherwise noted, this item's license is described as Acesso Aberto