Ant Colony optimization technique to Solve the min-max multi depot vehicle routing problem

In this paper, we extend our work on solving minmax single depot vehicle routing, published in the proceedings of the ACC 2011, to solving min-max multi depot vehicle routing problem. The min-max multi-depot vehicle routing problem involves minimizing the maximum distance travelled by any vehicle in case of vehicles starting from multiple depots and travelling to each customer location (or city) at least once. This problem is of specific significance in case of time critical applications such as emergency response in large-scale disasters, and server-client network latency. In this paper we extend the ant colony based algorithm which was proposed earlier in our previous paper and introduce a novel way to address the min-max multi-depot vehicle routing problem. The approach uses a region partitioning method developed by Carlsson et al. to convert the multi-depot problem into multiple single-depot versions. A computer simulation model using MATLAB was developed. Also, in terms of optimality of solution and computational time, a comparison with the existing Carlsson model has been carried out.