Dynamic vehicle routing with heterogeneous demands

In this paper we study a variation of the Dynamic Traveling Repairperson Problem (DTRP) in which there are two classes of demands; high priority, and low priority. In the problem, demands arrive in the environment randomly over time and assume a random location and on-site service requirement. A service vehicle must travel to each demand location and provide the required on-site service. The quality of service provided to each class of demands is measured by the expected delay between a demand¿s arrival and its service completion. The goal is to design policies for the service vehicle which minimize a convex combination of the delays for each class. We provide a lower bound on the achievable delay for this problem, and propose a policy which performs within a known constant factor of the optimal in heavy load (i.e., when the fraction of time the service vehicle spends performing on-site service approaches one). The problem studied in this paper is analogous to the multi-class queuing problem in classical queuing theory.