Branch and Price for the Stochastic Traveling Salesman Problem with Generalized Latency
研究了带广义延迟的对称旅行商问题的随机扩展，提出分支定价算法和局部搜索方法，在文献实例上比已知基准改进上界最多85%、下界最多55%，并证明随机模型比确定性模型更经济且鲁棒。
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 .