Ant Colony Optimisation (ACO) is an effective population-based meta-heuristic
for the solution of a wide variety of problems. As a population-based
algorithm, its computation is intrinsically massively parallel, and it is
there- fore theoretically well-suited for implementation on Graphics Processing
Units (GPUs). The ACO algorithm comprises two main stages: Tour construction
and Pheromone update. The former has been previously implemented on the GPU,
using a task-based parallelism approach. However, up until now, the latter has
always been implemented on the CPU.