Dynamic Vehicle Routing with Moving Demands - Part I: Low speed demands and high arrival rates

We introduce a dynamic vehicle routing problem in which demands arrive uniformly on a segment and via a temporal Poisson process. Upon arrival, the demands translate perpendicular to the segment in a given direction and with a fixed speed. A service vehicle, with speed greater than that of the demands, seeks to serve these translating demands. For the existence of any stabilizing policy, we determine a necessary condition on the arrival rate of the demands in terms of the problem parameters: (i) the speed ratio between the demand and service vehicle, and (ii) the length of the segment on which demands arrive. Next, we propose a novel policy for the vehicle that involves servicing the outstanding demands as per a translational minimum Hamiltonian path (TMHP) through the moving demands. We derive a sufficient condition on the arrival rate of the demands for stability of the TMHP-based policy, in terms of the problem parameters. We show that in the limiting case in which the demands move much slower than the service vehicle, the necessary and the sufficient conditions on the arrival rate are within a constant factor.