Optimal Service Commitments in Traveling Salesman Problems with Stochastic Demand
Abstract
In ridepooling services, mobility providers must communicate an expected arrival time before customers decide whether to book. An ambitious commitment attracts higher demand than a conservative one, but is correspondingly harder to fulfill. Provider revenue is therefore governed by an endogenous interplay between the announced commitment and the demand it induces. We study this interplay in a traveling salesman setting in which all customers share a shuttle to a common destination, formalizing it as the Traveling Salesman Problem with Service Commitments (TSP-SC), a two-stage stochastic optimization problem. In the first stage, the provider announces an arrival commitment to all customers interested in the trip, each of whom independently accepts or rejects the offer with a probability decreasing in the committed time. In the second stage, an Orienteering Problem determines a revenue-maximizing subset of accepting customers to be served within the commitment; the remaining customers are rejected. We show that optimal commitments lie in a finite candidate set induced by the tour lengths of customer subsets, and develop two exact algorithms, a general and a faster variant for homogeneous customers, together with an Adaptive Binomial Sampling Heuristic (BSH) for larger instances. In a numerical study on instances with up to 100 customers, the heuristic deviates from the optimal expected revenue by at most 0.32~\% on average across all exactly solvable sizes. The results further reveal a striking operational regularity: as the customer base grows, the revenue-maximizing policy converges to a regime in which roughly one in three accepting customers is rejected, a rejection rate that remains stable across instance sizes.
Related
- Collaborative Attention Ant Colony Optimization for Large-Scale Traveling Salesman Problems
- Exact cost of the Euclidean Maximum Traveling Salesman Problem in one dimension
- Traveling Salesman Problem on Graphs with Proportional Independent Set
- On the Segment-Based Remove-and-Reinsert Heuristic for the Generalized Traveling Salesman Problem
- Closing All-Exp Gaps in Local Search for the Traveling Salesman Problem and Maximum Constraint Assignment
BibTeX
@misc{schmidt2026optimal,
title = {{Optimal Service Commitments in Traveling Salesman Problems with Stochastic Demand}},
author = {Lina Schmidt and Julian Golak and Arne Schulz and Malte Fliedner},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.11950},
eprint = {2609.11950},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.11950},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Optimal Service Commitments in Traveling Salesman Problems with Stochastic Demand
AU - Lina Schmidt
AU - Julian Golak
AU - Arne Schulz
AU - Malte Fliedner
PY - 2026
DA - 2026/09/01
PB - arXiv
DO - 10.48550/arxiv.2609.11950
UR - https://arxiv.org/abs/2609.11950
AB - In ridepooling services, mobility providers must communicate an expected arrival time before customers decide whether to book. An ambitious commitment attracts higher demand than a conservative one, but is correspondingly harder to fulfill. Provider revenue is therefore governed by an endogenous interplay between the announced commitment and the demand it induces. We study this interplay in a traveling salesman setting in which all customers share a shuttle to a common destination, formalizing it as the Traveling Salesman Problem with Service Commitments (TSP-SC), a two-stage stochastic optimization problem. In the first stage, the provider announces an arrival commitment to all customers interested in the trip, each of whom independently accepts or rejects the offer with a probability decreasing in the committed time. In the second stage, an Orienteering Problem determines a revenue-maximizing subset of accepting customers to be served within the commitment; the remaining customers are rejected. We show that optimal commitments lie in a finite candidate set induced by the tour lengths of customer subsets, and develop two exact algorithms, a general and a faster variant for homogeneous customers, together with an Adaptive Binomial Sampling Heuristic (BSH) for larger instances. In a numerical study on instances with up to 100 customers, the heuristic deviates from the optimal expected revenue by at most 0.32~\% on average across all exactly solvable sizes. The results further reveal a striking operational regularity: as the customer base grows, the revenue-maximizing policy converges to a regime in which roughly one in three accepting customers is rejected, a rejection rate that remains stable across instance sizes.
ER -