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.