Multi-caste ant colony algorithm for the dynamic traveling salesperson problem



In this paper we apply a multi-caste ant colony system to the dynamic traveling salesperson problem. Each caste inside the colony contains its own set of parameters, leading to the coexistence of different exploration behaviors. Two multi-caste variants are proposed and ana- lyzed. Results obtained with different dynamic scenarios reveal that the adoption of a multi-caste architecture enhances the robustness of the al- gorithm. A detailed analysis of the outcomes suggests guidelines to select the best multi-caste variant, given the magnitude and severity of changes occurring in the dynamic environment.


ant colony optimization; dynamic traveling salesperson; multi-caste ant colony system; problem


Ant Colony Optimization


M. Tomassini et al. (Eds.): ICANNGA 2013, LNCS 7824, pp. 226--235. Springer, Heidelberg (2013), April 2013, April 2013


Cited by

Year 2019 : 1 citations

 Oliveira S., Wanner E.F., de Souza S.R., Bezerra L.C.T., Stützle T. (2019) The Hypervolume Indicator as a Performance Measure in Dynamic Optimization. In: Deb K. et al. (eds) Evolutionary Multi-Criterion Optimization. EMO 2019. Lecture Notes in Computer Science, vol 11411. Springer, Cham

Year 2018 : 3 citations

 Mavrovouniotis, Michalis; Shengxiang Yang, : Ant colony optimization for dynamic combinatorial optimization problems (Control, Robotics & Sensors, 2018), 'Swarm Intelligence - Volume 1: Principles, current algorithms and methods', Chap. 5, pp. 121-142, DOI: 10.1049/PBCE119F_ch5

 M. Mavrovouniotis, M. Van, S. Yang. Pheromone modification strategy for the dynamic travelling salesman problem with weight changes. IEEE Symposium Series on Computational Intelligence (SSCI 2017) Conference Proceedings, pp. 1-8, 2017

 Souza, Matheus. (2018) Algoritmo híbrido para o problema do caixeiro viajante dinâmico: otimização por colônia de formigas+ buscas locais. Dissertação de Mestrado do Programa de Pós-graduação em Informática, área de computação aplicada, da Universidade Federal de Santa Maria. Orientado por Felipe Martins Muller.

Year 2017 : 3 citations

 M. Mavrovouniotis, A. Ioannou, S. Yang. Pre-scheduled colony size variation in dynamic environments. Applications of Evolutionary Computation, LNCS, vol. 10200, pp. 128-139, Springer, 2017.

 M. Mavrovouniotis, F. M. Müller, S. Yang. An ant colony optimization with local search for dynamic traveling salesman problems. IEEE Transactions on Cybernetics, vol. 47, no. 7, pp. 1743-1756, 2017.

 M. Mavrovouniotis, C. Li, S. Yang. A survey of swarm intelligence for dynamic optimization: Algorithms and applications. Swarm and Evolutionary Computation, vol. 33, pp. 1-17, Elsevier. 2017.

Year 2016 : 1 citations

 M. Mavrovouniotis, S. Yang. Empirical study on the effect of population size on MAX-MIN Ant System in dynamic environments. Proceedings of the 2016 IEEE Congress on Evolutionary Computation (CEC'16), pp. 853-860, 2016.

Year 2014 : 4 citations

 M. Mavrovouniotis and S. Yang. Ant Colony Optimization with Self-Adaptive Evaporation Rate in Dynamic Environments. Proceedings of the 2014 IEEE Symposium on Computational Intelligence in Dynamic and Uncertain Environments, pp. 47-54, IEEE, 2014

 M. Mavrovouniotis, S. Yang and Xin Yao. Multi-Colony Ant Algorithms for the Dynamic Travelling Salesman Problem. Proceedings of the 2014 IEEE Symposium on Computational Intelligence in Dynamic and Uncertain Environments, pp. 9-16, IEEE, 2014

 M. Mavrovouniotis and S. Yang. Interactive and non-interactive hybrid immigrants schemes for ant algorithms in dynamic environments. Proceedings of the 2014 IEEE Congress on Evolutionary Computation (CEC'14), pp. 1542-1549, IEEE Press, 2014.

 M. Mavrovouniotis and S. Yang. Elitism-based immigrants for ant colony optimization in dynamic environments: adapting the replacement rate. Proceedings of the 2014 IEEE Congress on Evolutionary Computation (CEC'14), pp. 1752-1759, IEEE Press, 2014.