Running time analysis of ant colony optimization for shortest path problems (Q414437)

Ant colony optimization denotes a class of randomized search heuristics that are inspired by the ability of natural ants to find shortest paths. They simulate the path finding of ants algorithmically to find good solutions to different optimization problems. While finding shortest paths is the original motivation for ant colony optimization, its applications are usually in difficult optimization problems (see [\textit{M.\ Dorigo} and \textit{T. Stützle}, Ant Colony Optimization. Cambridge, MA: MIT Press (2004; Zbl 1092.90066)] for an introduction and overview). The theoretical analysis is concerned with particularly simple ant colony optimizers and simple problems. An important step was the analysis for the single source shortest paths problem [\textit{N.\ Attiratanasunthron} and \textit{J.\ Fakcharoenphol}, Inf. Process. Lett. 105, No. 3, 88--92 (2008; Zbl 1184.68659)]. The article under review continues this line of research and contains improved bounds, transfers the analysis to the all pairs shortest paths problem, and contains a comparison with evolutionary algorithms. The article is clearly structured and provides useful explanations. The proofs are complete and accessible, the example graphs used for lower bounds help to also build up a useful intuitive understanding.