Siegfried Benkner1, Karl F. Doerner2, Richard F. Hartl2,
Guenter Kiechle2, Maria Lucka1
1 Institute for Software Science, University of Vienna,
Liechtensteinstrasse 22, A-1090 Vienna, Austria
2 Institute for Management Science, University of Vienna
Bruenner Strasse 72, A-1210 Vienna, Austria
In this paper we study the efficiency and efficacy of information exchange of several ant colonies for the Vehicle Routing Problem (VRP) on different parallel hardware architectures. The VRP involves the construction of a set of vehicle tours starting and ending at a single depot and satisfying the demands of a set of customers, where each customer is served by exactly one vehicle and neither vehicle capacities nor maximum tour lengths are violated. Therefore no efficient exact solution methods are available, and the existing solution approaches are of heuristic nature.
We focus on solving the VRP with Ant Colony Optimization (ACO). Based on the observation of real ants' foraging behavior ACO was developed as a graph-based, iterative, constructive metaheuristic by Dorigo et al. The main idea of ACO is that a population of computational ants repeatedly builds and improves solutions to a given instance of a combinatorial optimization problem. From one generation to the next a joint memory is updated that guides the work of the successive populations. The memory update is based on the solutions found by the ants and more or less biased by their associated quality.
The method, being a population based approach, seems to lend itself to parallelization on different levels. In fact recently some possible parallelization strategies for ACO have been proposed. In fine-grained parallelization strategies very few artificial ants are assigned to each processor and therefore frequent information exchange between the small sub-populations of ants (i.e. an information exchange between the processors) takes place. Coarse grained parallelization schemes run several subcolonies in parallel. The information exchange among these subcolonies is done at certain intervals or numbers of iterations. The important questions in implementing different subpopulations are when, which and how information should be exchanged among the subcolonies. We realized both fine grained as well as coarse grained implementations. We analyze the effectiveness of different parallel variants of our algorithm on clusters and Grids. Moreover, we describe the realization of a Grid service for coarse grained parallel Ant Colony Optimization using Web Services technologies and Globus/OGSA.