A stochastic and dynamic routing policy using branching processes with state dependent immigration

A stochastic and dynamic vehicle routing problem called the Dynamic Traveling Repairman Problem was introduced by Bertsimas and van Ryzin. Several routing policies were analyzed in light traffic and in heavy traffic conditions. But, the good light traffic policies become very quickly unstable with increasing traffic intensity, and the good heavy traffic policies are inefficient in light traffic conditions. In this paper, a new routing policy is defined and analyzed, using results from branching processes with state dependent immigration. This policy not only performs optimally in light traffic, but also performs very well in heavy traffic. This is important to the designer of a service system because the traffic conditions may be variable and/or be unpredictable, and having to switch routing policies could prove to be costly and difficult to implement.