Dynamic Vehicle Routing Problem (DVRP)
The Vehicle Routing Problem (VRP) consists in designing the optimal set of routes for fleet of vehicles in order to serve a given set of customers.
For detailed information about VRP, we encourage you to visit NEO's thematic site dedicated to VRP (link).
Dynamic VRP assumes some kind of changes can affect the problem while the algorithm is trying to solve it. These changes may involve incidences like a car breakdown and traffic jams, as well as new order placements, unexpected withdrawal of orders, etc.
One of the most studied versions of VRP is Capacitated VRP (CVRP), where all vehicles have the same capacity. The fitness of a solution is defined as the sum of the costs of all its routes:
where each vehicle cannot exceed a certain maximum load L, and the distance covered by each route cannot exceed a certain distance limit D:
The Dynamic CVRP is often defined by changes in the former restrictions, so that the maximum vehicle's load and route's distance vary over time: