Models and algorithms for the Time Window Assignment Traveling Salesperson Problem with stochastic travel times

We study the Time Window Assignment Traveling Salesperson Problem with Stochastic Travel Times, a two-stage stochastic problem where the first-stage decisions involve the routing aspects and the customer time window definition. Second-stage decisions follow, which integrate travel time uncertainties into the optimization process. The objective is to minimize the combined routing and time window cost, including penalties for earliness and lateness, marking a shift from a cost-focused routing strategy to a more balanced approach that considers both cost and service quality aspects in delivery operations. We introduce a novel formulation inspired by a 3-index formulation for the Time-Dependent Traveling Salesperson Problem, and we report an extensive computational comparison of alternative models and solution methods from the literature. Additionally, we provide a set of benchmark instances characterized by two opposite scenario types, intended to facilitate future research. Our results show that the (by far) most effective solution method is an ad-hoc Benders Decomposition algorithm that leverages our new model, demonstrating substantial improvements over prior state-of-the-art exact solution methods. • We investigate the Time Window Assignment Traveling Salesperson Problem with Stochastic Travel Times. • We propose a specialized Benders algorithm based on a new mixed-integer linear model. • We generate and make publicly available a new set of benchmark instances. • We demonstrate that the proposed method substantially outperforms the state-of-the-art methods.