Metaheuristics for Dynamic Vehicle Routing

Combinatorial optimization problems are usually modeled in a static fashion. In this kind of problems, all data are known in advance, i.e. before the optimization process has started. However, in practice, many problems are dynamic, and change while the optimization is in progress. For example, in the Dynamic Vehicle Routing Problem (DVRP), which is one of the most challenging combinatorial optimization tasks, the aim consists in designing the optimal set of routes for a fleet of vehicles in order to serve a given set of customers. However, new customer orders arrive while the working day plan is in progress. In this case, routes must be reconfigured dynamically while executing the current simulation. The DVRP is an extension of the conventional routing problem, its main interest being the connection to many real-word applications (repair services, courier mail services, dial-a-ride services, etc.). In this chapter, the DVRP is examined, and a survey on solving methods such as population-based metaheuristics and trajectory-based metaheuristics is exposed. Dynamic performances measures of different metaheuristics are assessed using dedicated indicators for the dynamic environment.