The k-Traveling Repairman Problem with Stochastic Service Request Times

The traveling repairman problem focuses on minimizing total latency, defined as the waiting time experienced by customers after submitting a service request. This problem naturally arises in settings where customer experience is a key objective, particularly in time-sensitive service operations. We address a generalized traveling repairman problem that extends the classical setting by incorporating available probabilistic information on the timing of future requests as well as a more flexible method for measuring the impact of service latency. To account for potential future requests in addition to those known at the time of route planning, we develop a priori routes combined with recourse rules for their execution, aiming to minimize the total expected disutility caused by service latency across all customers. We formulate the problem as a stochastic, path-based traveling repairman problem and solve it using a branch-and-price algorithm, where expected latency is estimated through sample-scenario planning. We then evaluate the performance of our a priori routing approach through a factorial experiment; compare it with alternative routing strategies; and apply these methods to a large-scale, real-world bike-sharing setting.

Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2023.0478.