A Hybrid Algorithm for Multi-depot Vehicle Routing Problem

Vehicle routing problem (VRP) is an important combinatorial optimization problem. The problem is easy to describe but difficult to achieve an optimal solution owing to the high computational complexity. It is an NP-hard problem. Multi-depot vehicle routing problem is one of the extensions of VRP, which is assumed that a logistics company has more than one depot. To solve the problem, a hybrid algorithm which embedded Metropolis acceptance rule of simulated annealing in genetic algorithm is developed. In the hybrid algorithm, genetic algorithm (GA) combines global search and local search to search for the optimal results and simulated annealing (SA) uses certain probability to avoid being trapped in a local optimum. The computational study showed that the proposed algorithm is a feasible and effective approach for multi-depot vehicle routing problem.