An effective genetic algorithm for the multi-depot vehicle routing problem [PDF]
B. Ombuki and F. Hanshar, October 2004.
Efficient routing and scheduling of vehicles has significant economic implications for both the public and private sectors. This paper considers the multi-depot vehicle routing problem (MDVRP) which is an important extension of the vehicle routing problem. We find it is surprising to identify only one effective genetic algorithm (GA) that can compete with the powerful tabu search methods designed for the MDVRP. We present a simple but efficient GA that employs an indirect encoding and an adaptive inter-depot exchange strategy for the MDVRP with capacity and route-length restrictions. The algorithm is tested on a set of 23 classic MDVRP benchmark problems with 50 to 360 customers. The GA's ability to find good solutions demonstrates that the solution for the MDVRP problem does not strongly depend on the clustering algorithm used to initially assign customers to depots. The GA finds 17 out of 23 new GA solutions compared to the current best-known GA for the problem. Overall, the GA is equally good compared to other existing non-GA based meta-heuristics, obtaining better or competitive results.