A Hybrid Method Based on Intelligent Water Drop Algorithm and Simulated Annealing for Solving Multi-depot Vehicle Routing Problem

The vehicle routing problem and its variants such as the multi-depot vehicle routing problem are well-known NP-hard combinatorial optimization problems with wide engineering and theoretical background. In this paper a new hybrid technique based on intelligent water drop algorithm and simulated annealing is proposed to solve the multi-depot vehicle routing problem. The intelligent water drop algorithm is a stochastic population based metaheuristic optimization algorithm that uses a constructive approach to find optimal solutions of a given problem. Simulated annealing is a popular local search meta-heuristic approach with the key features of being able to provide a means to escape local optima by allowing hill-climbing moves with the hope of finding a global optimum. The performance of the hybrid algorithm is evaluated on a set of 23 benchmark instances and the results obtained compared with the best known solutions. The computational results show that the proposed method can produce good solutions, indicating that it is a good alternative algorithm for solving the multi-depot vehicle routing problem.