Dynamic Traveling Repairperson Problem for Dynamic Systems

In this paper, we study the Dynamic Traveling Repairman Problem (DTRP) for dynamic systems. In the DTRP, customers are arising dynamically and randomly in a bounded region R, and when customers arrive, they wait for the repairperson to visit their location and offer a "service" -that will take a certain random amount of time s-. In our study, the repairperson is modeled as a dynamic system whose output space contains R and our objective is the average time a customer has to wait to be serviced. We present schemes (for low and high traffic intensities) that guarantee that the expected waiting time for a customer scales within a constant factor of the optimum in terms of traffic intensity.