Article Dynamic Vehicle Routing Problem with Multiple Depots

Abstract. The Vehicle Routing Problems (VRPs) has been extensively studied and applied in many fields. Variations of VRPs have been proposed and appeared in research 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 a group of scattered service stores which 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 a heuristic approach for D-MDVRP. The proposed heuristic method comprises of two phases: route construction and vehicle dispatch. Routes are constructed by applying the Nearest Neighbor Procedure (NNP) to cluster customers and select a 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. A