Dynamic Vehicle Routing Problem with Multiple Depots

Abstract

Vehicle Routing Problems (VRPs) have been extensively studied and applied in many fields. Variants of VRPs have been proposed and appeared in researches for many decades. Dynamic Vehicle Routing Problem with Multiple Depots (D-MDVRP) extends the variation of VRPs to dynamism of customers by knowing the information of customers (both locations and due dates) at diverse times. An application of this problem can be found in food delivery services which have many service stores. The customer delivery orders are fulfilled by the scattered service stores where can be analogous to depots in D-MDVRP. In this example the information of all customer orders are not known at the same time depending on arrivals of customers. Thus the objective of this operation is to determine vehicle routing from service stores as well as dispatching time. This paper aims to develop the heuristic for D-MDVRP. The proposed heuristic comprises of two phases: route construction and vehicle dispatch. Routes are constructed by applying Nearest Neighbor Procedure (NNP) to cluster customers and select the proper depot, Sweeping and Reordering Procedures (SRP) to generate initial feasible routes, and Insertion Procedure (IP) to improve routing. Then the determination of dispatch is followed in the next phase. In order to deal with the dynamism, the dispatch time of each vehicle is determined by maximizing the waiting time to provide the opportunity to add more arriving customers in the future. An iterative process between two phases is adopted when a new customer enters the problem, and the vehicles are dispatched when the time becomes critical. From the computational study, the heuristic performs well on small size test problems in a shorter CPU time compared to the optimal solutions from CPLEX, and provides an overall average 8.36% Gap. For large size test problems, the heuristic is compared with static problems, and provides an overall average 3.48% Gap.