In the online traveling repairman problem OLTRP requests for visits to cities arrive online while the repairman is traveling. We analyze the performance of algorithms for the online problem using competitive analysis, where the cost of an online algorithm is compared to that of an optimal offline algorithm.

Feuerstein and Stougie [8] present a 9-competitive algorithm for the OLTRP on the real line. In this paper we show how to use techniques from online-scheduling to obtain a 6-competitive deterministic algorithm for the OLTRP on any metric space. We also present a randomized algorithm with competitive ratio of 3/ln 2 < 4.3281 against an oblivious adversary. Our results extend to the “dial-a-ride” generalization L-OLDARP of the OLTRP, where objects have to be picked up and delivered by a server. We supplement the deterministic lower bounds presented in [8] with lower bounds on the competitive ratio of any randomized algorithm against an oblivious adversary. Our lower bounds are ln 16+1/ln 16-1 > 2.1282 for the L-OLDARP on the line, 4e-5/2e-3 > 2.41041 for the L-OlDarp on general metric spaces, 2 for the OLTRP on the line, and 7/3 for the OLTRP on general metric spaces.