Dynamic Vehicle Routing in Presence of Random Recalls

Dynamic vehicle routing (DVR) problems involve a vehicle that seeks to service demands which are generated via a spatio-temporal stochastic process in a given environment. This letter introduces a DVR problem in which the vehicle needs to return to a central facility from time to time. We model the return events as a Poisson process with a known parameter. The problem parameters are the demand generation rate, the size of the environment and the recall rate. The goal is to design service policies for the vehicle in order to minimize the expected service time per demand. The contributions are as follows. We first provide a complete analysis of the regime of low demand arrival using a first-come-first-served policy. For the regime of high demand arrival, we derive a policy independent lower bound on the expected service time as a function of the problem parameters. We then adapt a well-known policy based on repeated computation of the Euclidean traveling salesperson tour through unserviced demands and provide an upper bound on the expected service time, quantifying the factor of optimality relative to the lower bound. We supplement the analysis with several insightful numerical simulations.