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

The article focuses on the stochastic traveling salesman problem with generalized latency (STSP-GL), which extends the classical traveling salesman problem by explicitly incorporating uncertainty in passenger demand for demand-adaptive transit systems (DAS). The STSP-GL aims to select a subset of transit stops and determine a Hamiltonian tour that minimizes a weighted sum of route design and passenger routing costs while ensuring that a specified percentage of uncertain passenger demand is served with a given probability. The authors formulate the STSP-GL as a chance-constrained stochastic program, develop its deterministic equivalent, and propose solution methods including a branch-and-price (B&P) algorithm, a local search heuristic, and a hybrid approach combining both. Computational experiments on instances from the TSPGL_LIB data set demonstrate that the B&P and hybrid methods outperform a mixed-integer programming benchmark by significantly improving upper and lower bounds, especially on larger instances, and that stochastic solutions provide more robust and cost-effective routes than deterministic ones. The study also finds that the service level (market share served) has a greater impact on design costs than the frequency of meeting that service level, suggesting that DAS operators should prioritize service level targets in tactical planning under demand uncertainty.