Dynamic Vehicle Routing Problem with Multiple Depots

Authors

  • Kwankaew Meesuptaweekoon Chulalongkorn University
  • Paveena Chaovalitwongse Chulalongkorn University

DOI:

https://doi.org/10.4186/ej.2014.18.4.135

Keywords:

Vehicle routing problem, multiple depots, dynamic problem, heuristic, nearest neighbor procedure, sweeping and reordering procedures, insertion procedure

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.

Downloads

Download data is not yet available.

Author Biographies

Kwankaew Meesuptaweekoon

Department of Industrial Engineering, Faculty of Engineering, Chulalongkorn University, Bangkok 10330, Thailand

Paveena Chaovalitwongse

Department of Industrial Engineering, Faculty of Engineering, Chulalongkorn University, Bangkok 10330, Thailand

Published

Vol 18 No 4, Oct 16, 2014

How to Cite

[1]
K. Meesuptaweekoon and P. Chaovalitwongse, “Dynamic Vehicle Routing Problem with Multiple Depots”, Eng. J., vol. 18, no. 4, pp. 135-149, Oct. 2014.