A progressive hedging method for the multi-path travelling salesman problem with stochastic travel times

In this paper, we consider a recently introduced problem specifically designed for Smart Cities and City Logistics applications: the multi-path travelling salesman problem with stochastic travel costs (mpTSPs)(mpTSPs). The mpTSPsmpTSPs is a variant of the TSP problem where a set of paths exists between any two nodes and each path is characterized by a random travel time. We propose a two-stage stochastic programming formulation where tour design makes up the first stage, while recourse decisions related to the choice of the path to follow are made in the second stage. To solve this formulation, we propose a heuristic method inspired by the Progressive Hedging (PH) algorithm of Rockafellar & Wets (1991, Scenarios and policy aggregation in optimization under uncertainty. Math. Oper. Res., 16, 119–147.) We then benchmark the solution method by solving model instances derived from the traffic speed sensor network of the city of Turin. Furthermore, the impact of the stochastic travel time costs on the problem solution is examined, showing the benefits of the proposed methodology in both solution quality and computational effort when compared to solving the deterministic equivalent formulation using a commercial solver.