A Review of Dynamic Vehicle Routing Problems

The Vehicle Routing Problem (VRP) formulation was first introduced in 1959 as a generalization of the Traveling Salesman Problem (TSP). In contrast to the classical definition of the vehicle routing problem, real-world applications often include two important dimensions: evolution and quality of information. Evolution of information relates to the fact that in some problems the information available to the planner may change during the execution of the routes. Quality of information reflects possible uncertainty on the available data. In addition, depending on the problem and the available technology, vehicle routes can either be designed statically or dynamically.

Static and stochastic problems are characterized by input partially known as random variables, which realizations are only revealed during the execution of the routes. In dynamic and deterministic problems, part or all of the input is unknown and revealed dynamically during the design or execution of the routes. Similarly, dynamic and stochastic problems have part or all of their input unknown and revealed dynamically during the execution of the routes.

In contrast to their static counterparts, dynamic routing problems involve new elements that increase the complexity of their decisions (more degrees of freedom) and introduce new challenges while judging the merit of a given route plan. In dynamic routing, the ability to redirect a moving vehicle to a new request nearby allows for additional savings.

Different problems (or instances of a same problem) can have different levels of dynamism, which

can be characterized according to two dimensions, the frequency of changes and the urgency of requests. Thus, three metrics have been proposed to measure the dynamism of a problem. The degree of dynamism is defined as the ratio between the number of dynamic requests and the total number of requests. The effective degree of dynamism can be interpreted as the normalized average of the disclosure times. The reaction time is defined as the difference between the disclosure time and the end of the corresponding time window li, highlighting that longer reaction times mean more flexibility to insert the request into the current routes.

In a category of applications, a service request is defined by a customer location and a possible time window; while vehicle routes just fulfill service requests without considering side constraints such as capacity. Approaches for dynamic and deterministic vehicle routing problems can be divided into two categories: those based on periodic reoptimization, and those based on continuous reoptimization.  Periodic reoptimization approaches start at the beginning of the day with a first optimization that produces an initial set of routes. Then, an optimization procedure periodically solves a static problem corresponding to the current state. Continuous reoptimization approaches perform the optimization throughout the day and maintain information on good solutions in an adaptive memory. Whenever the available data changes, a decision procedure aggregates the information from the memory to update the current routing.

Researchers have mainly focused on the routing aspect of the dynamic fleet management. However, in some applications there is more that can be done to improve performance and service level. So a system in which aside from giving a yes/no answer to a customer request, suggests convenient times for the company would be highly desirable in such contexts.