D-ants: Savings based ants divide and conquer the vehicle routing problem

This paper presents an algorithm that builds on the Savings based Ant System presented in [Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2002), Morgan Kaufmann, San Francisco, 2002] and enhances its performance in terms of computational effort. This is achieved by decomposing the problem and solving only the much smaller subproblems resulting from the decomposition. The computational study and statistical analysis conducted both on standard benchmark problem instances as well as on new large scale Vehicle Routing Problem instances will show that the approach does not only improve the efficiency, but also improves the effectiveness of the algorithm leading to a fast and powerful problem solving tool for real world sized Vehicle Routing Problems.