In this section the dynamic vehicle routing problem (DVRP) will be ver-bally defined and a simple example of a DVRP scenario will be presented.
Psaraftis [36] uses the following classification of the static routing problem;
“if the output of a certain formulation is a set of preplanned routes that are not re-optimized and are computed from inputs that do not evolve in real-time”. While he refers to a problem as dynamic if“the output is not a set of routes, but rather a policy that prescribes how the routes should evolve as a function of those inputs that evolve in real-time”.
In the above definition by Psaraftis the temporal dimension plays a vital role for the categorizing of a vehicle routing problem. As will be demon-strated throughout this thesis the time of when relevant information is made known to the planner distinguishes a dynamic from a static vehicle routing problem.
In definition 1.1 we verbally define what we mean when we talk about a static vehicle routing problem.
Definition 1.1 The Static Vehicle Routing Problem.
1. All information relevant to the planning of the routes is as-sumed to be known by the planner before the routing process begins.
2. Information relevant to the routing does not change after the routes have been constructed.
1.3. THE DYNAMIC VEHICLE ROUTING PROBLEM 5 The information which is assumed to be relevant, includes all attributes of the customers such as the geographical location of the customers, the on-site service time and the demand of each customer. Furthermore, system information as for example the travel times of the vehicle between the customers must be known by the planner.
The dynamic counterpart of the static vehicle routing problem as defined in definition 1.1 could then be formulated as:
Definition 1.2 The Dynamic Vehicle Routing Problem.
1. Not all information relevant to the planning of the routes is known by the planner when the routing process begins.
2. Information can change after the initial routes have been constructed.
Obviously, the DVRP is a richer problem compared to the conventional static VRP. If the problem class of VRP is denotedP(VRP) and the prob-lem class of DVRP is denotedP(DVRP), thenP(VRP)⊂ P(DVRP).
The dynamic vehicle routing problem calls for online algorithms that work in real-time since the immediate requests should be served, if possible.
As conventional static vehicle routing problems areN P −hard, it is not always possible to find optimal solutions to problems of realistic sizes in a reasonable amount of computation time. This implies that the dynamic vehicle routing problem also belongs to the class ofN P −hardproblems, since a static VRP should be solved each time a new immediate request is received.
Psaraftis [35] refers to the solutionxtof the current problemptas atentative solution. The tentative solution corresponds to the current set of inputs and only those. If no new requests for service are received during the execution of this solution, the tentative route is said to be optimal.
In Figure 1.1 a simple example of a dynamic vehicle routing situation is shown. In the example, two un-capacitated vehicles must service both advance and immediate request customers without time windows. The advance request customers are represented by black nodes, while those
that are immediate requests are depicted by white nodes. The solid lines represent the two routes the dispatcher has planned prior to the vehicles leaving the depot. The two thick arcs indicate the vehicle positions at the time the dynamic requests are received. Ideally, the new customers should be inserted into the already planned routes without the order of the non-visited customers being changed and with minimal delay. This is the case depicted on the right hand side route. However, in practice, the insertion of new customers will usually be a much more complicated task and will imply a re-planning of the non-visited part of the route system. This is illustrated by the left hand side route where servicing the new customer creates a large detour.
New route segment Advance request customer (static)
Immediate request customer (dynamic)
Current position of vehicle Planned route
Figure 1.1: A dynamic vehicle routing scenario with 8 advance and 2 im-mediate request customers.
Generally, the more restricted and complex the routing problem is, the more complicated the insertion of new dynamic customers will be. For instance, the insertion of new customers in a time window constrained routing problem will usually be much more difficult than in a non-time constrained problem. Note that in an online routing system customers may even be denied service, if it is not possible to find a feasible spot to insert them. Often this policy of rejecting customers includes an offer to serve the customers the following day of operation. However, in some systems - as for instance the pick-up of long-distance courier mail - the service provider
1.3. THE DYNAMIC VEHICLE ROUTING PROBLEM 7 (distributor) will have to forward the customer to a competitor when they are not able to serve them.
When investigating dynamic vehicle routing systems, randomly generated data rather than real-life data are often used. There are two main reasons for this. Firstly, the use of randomly generated data often enables more in-depth analyses, since the datasets can be constructed in such a way that other issues could be addressed. Secondly, the vast majority of real-life dynamic vehicle routing problems do not at the present capture all data needed for in-depth analyses of the specific routing problem. The geographical locations of all vehicles each time new immediate requests are received are one of the most commonly missing data items in the study of real-life problems.
If one chooses to use randomly generated data, several highly relevant issues need to be addressed. Below we briefly discuss three of these issues bearing in mind that several other issues must be considered.
First, the method used for generating the arrival times of the immediate request customers must be considered. This is an important issue, since system designers use such information to develop solution methods. Tra-ditionally, a Poisson process is assumed for this purpose. The arrival rate parameter, generally denotedλ, then describes the “congestion” of the sys-tem. To emulate scenarios in more complex systems, the arrival process could be a mix of several different stochastic processes.
Another important modeling issue is the distributions that characterize the demand of the customers and the on-site service times at the customer locations. Uniform and Gaussian distributions as well as constant values have been employed. The latter is convenient, but also unrealistic in most cases. As an example, one could think of the pick-up of long-distance courier mail. In this context, the on-site service time at each customer will often vary greatly depending on a wide range of factors, as for instance the parking facilities, the physical layout of the buildings to be served and the efficiency of the pick-up itself (does the courier have to wait or is the customer set to hand over the mail?).
The last aspect to be mentioned in this introductory stage is the system reaction time. This is defined as the elapsed time between the receipt of the request and the end of the time window defining the latest feasible time for service to begin. The reaction time of each customer could be seen as a measure for the urgency in serving this customer. The overall reaction
time of a system is strongly related to the level of dynamism present in the system. Generally, the more dynamic a system is, the more difficult or costly it is to generate a fast reaction. Therefore, the dynamic make-up of a system plays a major role in choosing appropriate models and algorithms to support decisions in different scenarios.