DVRP

DVRP stands for Dynamic Vehicle Routing Problem, a dynamic extension of the classic Vehicle Routing Problem. In DVRP, a fleet of vehicles with finite capacity serves a set of customer requests that arrive over time. Each request typically involves moving a passenger or item from an origin to a destination, potentially within given time windows or service constraints. The planning objective is to operate feasible routes while adapting to new information as it becomes available, often through reoptimization or rolling-horizon planning.

The problem is characterized by uncertainty and temporality. Travel times may vary, requests arrive stochastically, and the system must decide, in real time, how to insert and reorganize routes without violating capacity or timing constraints. Solutions aim to minimize metrics such as total travel distance or time, customer waiting and delay, or a combination of cost components. DVRP can be static-primed but remains dynamic in operation, requiring frequent re-evaluation of routes.

Variants of DVRP include time-window DVRP, where service must occur within specified intervals, and multi-depot or heterogeneous fleet versions. In some literature, DVRP is used to describe dynamic versions of the dial-a-ride problem (DARP), though many authors distinguish between novel dynamic VRP formulations and DARP variants. The dynamic dial-a-ride literature is sometimes framed within the same DVRP umbrella, depending on the emphasis on passenger pick-up and drop-off timing.

Common solution approaches combine exact methods for small problems with heuristics and metaheuristics for larger instances. Techniques include insertion heuristics, rolling-horizon reoptimization, tabu search, simulated annealing, genetic algorithms, and matheuristics, often supplemented by simulation-based evaluation or reinforcement learning for policy approximation. DVRP has applications in on-demand transportation, courier and last-mile delivery, ride-sharing, and emergency response planning.