Parallel Ant Systems for the Capacitated Vehicle Routing Problem

In this paper we first provide a thorough performance comparison of the three main Ant Colony Optimization (ACO) paradigms for the Vehicle Routing Problem (VRP), namely the Rank based Ant System, the Max-Min Ant System and the Ant Colony System. Based on the results of this comparison we then implement a parallelization strategy to increase computational efficiency and study the effects of increasing the number of processors.