Dynamic Vehicle Routing Problem with Multiple Depots
Keywords:Vehicle routing problem, multiple depots, dynamic problem, heuristic, nearest neighbor procedure, sweeping and reordering procedures, insertion procedure
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.
Authors who publish with Engineering Journal agree to transfer all copyright rights in and to the above work to the Engineering Journal (EJ)'s Editorial Board so that EJ's Editorial Board shall have the right to publish the work for nonprofit use in any media or form. In return, authors retain: (1) all proprietary rights other than copyright; (2) re-use of all or part of the above paper in their other work; (3) right to reproduce or authorize others to reproduce the above paper for authors' personal use or for company use if the source and EJ's copyright notice is indicated, and if the reproduction is not made for the purpose of sale.