Resumen

The Shortest Path Tour Problem with Time Windows (SPTPTW) seeks the minimum-cost path between two nodes in a directed graph while visiting exactly one node from each ordered subset and respecting service times and time windows. The problem is NP-hard and existing exact methods, mainly labeling algorithms, often suffer from high memory usage and exponential growth of partial paths. This work introduces new backward temporal bounds that compute latest feasible arrival and reachability times to prune infeasible partial solutions early. In addition, a pulse-based exact algorithm is proposed that explores paths through depth-first search with dominance and bounding rules, requiring substantially less memory than labeling approaches. Computational experiments on multiple instance types show that the proposed bounds significantly reduce the search space and improve runtime, with pulse variants achieving competitive performance and lower memory consumption.