Vehicle routing algorithms to intercept escaping targets
Pushkarini Agharkar, Francesco Bullo · 2014
We study a dynamic vehicle routing problem for moving targets. Our setup is as follows: (i) targets appear uniformly distributed on a unit disk via a temporal Poisson process and move radially outward with a constant speed v, (ii) a single vehicle with speed greater than that of the targets aims to intercepts them before they escape the disk. With the goal of maximizing the fraction of captured targets in the steady state, we propose three policies: Capturable Nearest Neighbor (CNN), Sector Wise (SW) and Stay Near Boundary (SNB) policy. We derive lower bounds on the fraction of targets captured by the CNN, SW and SNB policies. The CNN policy is shown to be optimal for arrival rate λ below a critical value. For arrival rates above another critical value, the fraction of targets captured by the SW policy is more than that of the CNN policy. Finally, the SNB policy is within a constant factor of optimal in the limiting regime of ν → 0+and λ → +∞. We present numerical simulations to illustrate our results.