Multi-depot multi-trip heterogeneous vehicle routing problem with time windows and release dates

Abstract

Currently, the requirements and buying behaviors of customers in last mile delivery and distribution continuous change. Especially, the requirement about service time is more serious and their time window interval is different and not similar. Consequently, the changes motivated us to investigate a multi-depot multi-trip heterogeneous vehicle routing problem with time windows and release dates. In the scope of the study, we identity to design a set of trips for vehicles which is concerns about different capacity in many depots with the aims of minimizing the total travelling time of vehicles. Besides, in this study we also consider time windows interval of each customer and time release dates of goods required by customers to ensure that the model we investigate is relatively useful to address some current context of problem in reality. Hence, with the assumptions and real constraints, we solve a MIP model by IBM ILOG CPLEX for small-scale instances of the problem. After that, two heuristics algorithms which are potential to solve small-scale instances of the problem, named Randomly clustering - 2- opt Algorithm and Hybrid Nearest Selection Algorithm, are developed. Moreover, the numerical experiments are conducted to evaluate the effectiveness of the applied methods and identify that which method should be utilized in specific cases. In addition, sensitivity analysis is proceeded to analyze how the root parameters impacts on our model in this problem and search for the causes of that impact, which is useful for model improvements.