Dynamic Vehicle Routing Problem with Time Windows (DVRPTW)

The Dynamic Vehicle Routing Problem with Time Windows (DVRPTW) is an extension of the well-known Vehicle Routing Problem (VRP), which takes into account the dynamic nature of the problem, when the inputs are revealed or updated continuously. This aspect requires the vehicle routes to be updated in an ongoing manner as new customer requests arrive in the system and must be incorporated into an evolving schedule during the working day. Besides the vehicle capacity constraint involved in the classical VRP, DVRPTW considers in addition time windows, which are able to better capture real-world situations.

In Dynamic Vehicle Routing Problems (DVRPs), also referred to as online or real-time VRP, part or all the information defining the problem is revealed during the execution of the routes. Unlike the static version of VRP, in the dynamic case some information which defines the problem instance may be revealed dynamically during the working day, such that not all the input is known beforehand, and the algorithm must adapt and incorporate these changes. Common examples include the appearance of new customers or uncertain traveling times. In case of customers, new orders arrive while the working day plan is in progress, and 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-world applications (repair services, courier mail services, dial-a-ride services, etc.). In DVRP, not all information about the problem is known at the beginning of the planning horizon, and, in most cases the information can change after the solution process begins. These two characteristics make the DVRP harder than static VRP. Thus, not all information relevant to the planning of the routes is known by the algorithm when the routing process begins

Possible sources of dynamism in DVRP include: customers requests, travel time and demands, which can be dynamically revealed for a set of known customers. The most common source of dynamism is given by the customers requests, in which customers requests are serviced in a real-time manner, while the drivers have already started their routes, visiting in their way other customers. In DVRP, some of the orders are known in advance before the start of the working day, but as the day progresses, new orders arrive and the system has to incorporate them into an evolving schedule. This aspect increases the complexity of decisions and introduces new challenges while finding the optimal route plan. Thus, the algorithm needs to adjust the ongoing vehicle routes, such as to take into account these dynamic customer requests, while maintaining the feasibility of solution.

The vehicle routing problem with time windows (VRPTW) is a well known combinatorial problem that consists of designating the best set of routes to service a number of costumers. In order to service these costumers, a fleet of vehicles depart from a central depot, where they have to return at the end of their route. Each vehicle within the fleet has a maximum capacity that must not be exceeded. Costumers have a time window in which they may be serviced. Also, they have associated a service time (the unloading time at each destination), which is the actual time that the delivery takes once the vehicle arrives at a customer location. The requirement in VRPTW is to find a set of routes for each vehicle, such that each customer is visited exactly once, while minimizing the overall routing cost. The primary objective is to minimize the number of tours (vehicles), whilst a second objective is to minimize the total traveled distance needed to supply all customers in their required hours, meaning that the number of tours minimization takes precedence over total distance minimization. In case of solutions with the same number of vehicles, those solutions are preferred that are of lower distance.

The DVRPTW instances used in this study [1] can be found here.

The Java source code of the DVRPTW-ACS algorithm proposed in this study [1] can be found here.

Each of the below tables reflects the results obtained with the method described in this study [1]

The VRPTW problem instances from the Solomon's benchmark define a time window for each node, including the depot, namely [e₀, l₀], which denotes the scheduling horizon. At the same time, the specifications of the DVRPTW problem involve a certain length of the working day, which establishes when the algorithm will stop from its execution. To comply with these two requirements, we scaled in our algorithm all time related values. More precisely, for each customer request from a particular DVRPTW instance, the values for time windows, service time, available time and distance between two customers, are multiplied with the s_v factor, computed as: s_v = t_wd/(l₀-e₀). The results reported in the above tables for the total traveled distance (TD) are obtained as: TD = TD/s_v.

[1] Necula, R., Breaban, M., Raschip, M.: Tackling Dynamic Vehicle Routing Problem with Time Windows by means of Ant Colony System, 2017 IEEE Congress on Evolutionary Computation (CEC), 5-8 June, Donostia - San Sebastián, Spain, pp. 2480-2487, 2017 [link]