Dynamic vehicle routing with random requests: A literature review

Stimulated by the growing demand for logistics services and the advances in information technologies, research interest in the dynamic vehicle routing problem with random requests (DVRPRR) increased over recent decades. The DVRPRR differs from classical vehicle routing in that the customer requests are not fully known in advance but arrive dynamically during the execution of planned routes. Various approaches were developed to deal with this dynamism and the potential stochasticity. This paper provides a comprehensive and in-depth review of the existing DVRPRR literature. We propose a novel taxonomy that identifies four DVRPRR variants with different request types and planning horizons. We also analyze the research on each variant from the perspectives of problem settings, decision strategies, solution approaches, etc. Finally, we summarize the state of the art of the DVRPRR and suggest promising directions for future research.