Solving a Multi-Depot Routing Problem with Time Windows and Heterogeneous Vehicles by Multi-objective Differential Evolution Algorithm: A Case Study

A Multi-depot Heterogeneous Vehicle Routing Problem with Time Windows (MDHVRPTW) is a variant of the Vehicle Routing Problem (VRP)، in which the vehicles do not necessarily have the same capacity and they belong to different depots. Therefore، the MDHVRPTW involves designing a set of vehicle routes، each starting and ending at the depot، for a heterogeneous fleet of vehicles which services a set of customers with known demands. Most problems presented in this field are single-objective problems with the aim of minimizing the cost; however، the complexity of real problems usually doubts the use of single-objective problems. This paper considers not only the minimum travel cost، but also the distance travelled by the used vehicles and their loads. Since this problem is NP-hardness، the use of a meta-heuristic algorithm is obligatory. Therefore a meta-heuristic algorithm based on Multi-Objective Differential Evolution (MODE) is proposed. In addition، to show the efficiency of the proposed MODE، a number of test problems in small and large sizes are considered and then solved. The associated results are evaluated with the results obtained by the ε-constraint method and results showed that the gained function gap was less than 3. 5% in all the solved problems. Furthermore، to run the proposed MODE، a real-case study in an oil distribution company is carried out. Finally، the obtained results are reported and discussed.