Ant algorithms with immigrants schemes for the dynamic vehicle routing problem

Abstract

Many real-world optimization problems are subject to dynamic environments that require an optimization algorithm to track the optimum during changes. Ant colony optimization (ACO) algorithms have proved to be powerful methods to address combinatorial dynamic optimization problems (DOPs), once they are enhanced properly. The integration of ACO algorithms with immigrants schemes showed promising performance on different DOPs. The principle of immigrants schemes is to introduce new solutions (called immigrants) and replace a small portion in the current population. In this paper, immigrants schemes are specifically designed for the dynamic vehicle routing problem (DVRP). Three immigrants schemes are investigated: random, elitism- and memory-based. Their difference relies on the way immigrants are generated, e.g., in random immigrants they are generated randomly whereas in elitism- and memory-based the best solution from previous environments is retrieved as the base to generate immigrants. Random immigrants aim to maintain the population diversity in order to avoid premature convergence. Elitism- and memory-based immigrants aim to maintain the population diversity and transfer knowledge from previous environments, simultaneously, to enhance the adaptation capabilities. The experiments are based on a series of systematically constructed DVRP test cases, generated from a general dynamic benchmark generator, to compare and benchmark the proposed ACO algorithms integrated with immigrants schemes with other peer ACO algorithms. Sensitivity analysis regarding some key parameters of the proposed algorithms is also carried out. The experimental results show that the performance of ACO algorithms depends on the properties of DVRPs and that immigrants schemes improve the performance of ACO in tackling DVRPs.