Metraipolis › archive › dc_d37d5800cb93
Optimal Service Commitments in Traveling Salesman Problems with Stochastic Demand — arXiv:2609.11950
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.11950
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T03:44:21.985Z
- SHA-256 of the archived text
edb7dd5d279a6d1ffd0572dec4b1a646ebd2bba443011137aafea5af44cfcd2c- Stable URL of this page
https://metraipolis.com/documento/dc_d37d5800cb93
How to cite
Optimal Service Commitments in Traveling Salesman Problems with Stochastic Demand — arXiv:2609.11950 — arXiv (en), https://arxiv.org/abs/2609.11950 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_d37d5800cb93 (Metraipolis archive dc_d37d5800cb93, sha256 edb7dd5d279a6d1ffd0572dec4b1a646ebd2bba443011137aafea5af44cfcd2c)
BibTeX
@misc{dcd37d5800cb93,
title = {Optimal Service Commitments in Traveling Salesman Problems with Stochastic Demand — arXiv:2609.11950},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.11950},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_d37d5800cb93; sha256 edb7dd5d279a6d1ffd0572dec4b1a646ebd2bba443011137aafea5af44cfcd2c},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.11950. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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. Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-14 in math.OC). Categorie arXiv: Optimization and Control (math.OC). Pagina del lavoro: https://arxiv.org/abs/2609.11950 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-16T03:15:38.802Z dalla pagina https://arxiv.org/catchup/math.OC/2026-09-14?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).