ARES Lab @ MIT

S. Smith, M. Pavone, F. Bullo, and E. Frazzoli

 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's 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 delay 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.