Savings Based Ants for Large-scale Vehicle Routing Problems

In this paper we present a modified version of our Savings based Ant System for large-scale instances of the Vehicle Routing Problem (VRP). The main idea is to speed up the search by letting the ants solve only sub-problems rather than the whole problem. This is particularly necessary, when one has to solve large real world instances, for which the computation times of classic meta-heuristics are prohibitive. Our model is also inspired by Taillard ’s work on th e VRP ([1]), where the Tabu Search procedure employed solves only some sub-problems.