Ant colony optimization algorithms with immigrants schemes for the dynamic travelling salesman problem

Abstract

Ant colony optimization (ACO) algorithms have proved to be powerful methods to address dynamic optimization problems (DOPs). However, once the population converges to a solution and a dynamic change occurs, it is difficult for the population to adapt to the new environment since high levels of pheromone will be generated to a single trail and force the ants to follow it even after a dynamic change. A good solution is to maintain the diversity via transferring knowledge from previous environments to the pheromone trails using immigrants. In this chapter, we investigate ACO algorithms with different immigrants schemes for two types of dynamic travelling salesman problems (DTSPs) with traffic factor, i.e., under random and cyclic dynamic changes. The experimental results based on different DTSP test cases show that the investigated algorithms outperform other peer ACO algorithms and that different immigrants schemes are beneficial on different environmental cases. © 2013 Springer-Verlag Berlin Heidelberg.