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

Benedikt Lienkamp (), Mike Hewitt () and Maximilian Schiffer ()
Additional contact information
Benedikt Lienkamp: School of Management, Technical University of Munich, 80333 Munich, Germany
Mike Hewitt: Quinlan School of Business, Loyola University, Chicago, Illinois 60611
Maximilian Schiffer: School of Management, Technical University of Munich, 80333 Munich, Germany; and Munich Data Science Institute, Technical University of Munich, 80333 Munich, Germany

Transportation Science, 2025, vol. 59, issue 2, 229-249

Abstract: 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.

Keywords: semiflexible transit; branch and price; traveling salesperson problem; latency; stochastic programming (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2023.0417 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:59:y:2025:i:2:p:229-249

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().