Branch and Price for the Stochastic Traveling Salesman Problem with Generalized Latency

We consider an extension of the symmetric traveling salesman problem with generalized latency that explicitly models uncertainty. The stochastic traveling salesman problem with generalized latency (STSP-GL) aims to choose a subset of nodes of an undirected graph and determines a Hamiltonian tour among those nodes, minimizing an objective function that is a weighted combination of route design and passenger routing costs. These nodes are selected to ensure that a predefined percentage of uncertain passenger demand is served with a given probability. We formulate the STSP-GL as a stochastic program and propose a branch-and-price algorithm for solving its deterministic equivalent. We also develop a local search approach with which we improve the performance of the branch-and-price approach. We assess the efficiency of the proposed methods on a set of instances from the literature. We demonstrate that the proposed methods outperform a known benchmark, improving upper bounds by up to 85% and lower bounds by up to 55%. Finally, we show that solutions of the stochastic model are both more cost-effective and robust than those of the deterministic model.

History: This paper has been accepted for the Transportation Science Special Issue on TSL Conference 2023.

Funding: This work was supported by the Bundesministerium für Bildung und Forschung [Grant 03ZU1105FA].

Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2023.0417.