IEEE Computational Intelligence Magazine - February 2020 - 63

drawn. First, the effect on the performance of the decision rule used to construct solutions strongly depends on the
pheromone update policy of the ACO
framework. Second, the dynamic strategies further enhance the adaptation
capabilities of the two ACO frameworks,
but their effect on the performance
strongly depends on the dynamic settings
of the problem. And third, the utilization
of change-related information is always
effective for both ACO frameworks.
Finally, the source code of the
dynamic benchmark framework together with the performance measures and
the ACO algorithms used in this case
study is available at https://github.com/
Mavrovouniotis/ACODTSP. The source
code can be useful to researchers who
are interested in generating the same or
different dynamic test cases to compare
their own algorithms (not necessarily
ACO) in dynamic environments.
Acknowledgments

This work was supported in part by the
European Union's Horizon 2020 research
and innovation program under grant
agreement No. 739551 (KIOS CoE)
and from the Gover nment of the
Republic of Cyprus through the Directorate General for European Programs,
Coordination and Development, and in
part by the National Natural Science
Foundation of China under Grants
61673331 and 61673355.
References

[1] M. Dorigo and L. M. Gambardella, "Ant colony system: A cooperative learning approach to the traveling
salesman problem," IEEE Trans. Evol. Comput., vol. 1, no.
1, pp. 53-66, Apr. 1997.
[2] M. Dorigo, V. Maniezzo, and A. Colorni, "Ant system: Optimization by a colony of cooperating agents,"
IEEE Trans. Syst., Man, Cybern., B, vol. 26, no. 1, pp.
29-41, Feb. 1996.
[3] S. Goss, S. Aron, J. L. Deneubourg, and J. M. Pasteels,
"Self-organized shortcuts in the Argentine ant," Naturwissenschaften, vol. 76, no. 12, pp. 579-581, Dec. 1989.
[4] M. Dorigo, M. Birattari, and T. Stützle, "Ant colony
optimization," IEEE Comput. Intell. Mag., vol. 1, no. 4,
pp. 28-39, Nov. 2006.
[5] Y. Jin and J. Branke, "Evolutionary optimization in
uncertain environments-A survey," IEEE Trans. Evol.
Comput., vol. 9, no. 3, pp. 303-317, June 2005.
[6] G. Leguizamón and E. Alba, "Ant colony based algorithms for dynamic optimization problems," in Metaheuristics for Dynamic Optimization, E. Alba, A. Nakib, and
P. Siarry, Eds. Berlin, Germany: Springer-Verlag, 2013,
pp. 189-210.
[7] M. Mavrovouniotis, C. Li, and S. Yang, "A survey
of swarm intelligence for dynamic optimization: Algorithms and applications," Swarm Evol. Comput., vol. 33,
pp. 1-17, Apr. 2017.

[8] G. Di Caro and M. Dorigo, "AntNet: Distributed
stigmergetic control for communications networks," J.
Artif. Intell. Res., vol. 9, pp. 317-365, Dec. 1998.
[9] R. Montemanni, L. M. Gambardella, A. E. Rizzoli,
and A. V. Donati, "Ant colony system for a dynamic vehicle routing problem," J. Comb. Optim., vol. 10, no. 4,
pp. 327-343, Dec. 2005.
[10] J. Eaton, S. Yang, and M. Mavrovouniotis, "Ant
colony optimization with immigrants schemes for the
dynamic railway junction rescheduling problem with
multiple delays," Soft Comput., vol. 20, no. 8, pp. 2951-
2966, Aug. 2016.
[11] C. Eyckelhof and M. Snoek, "Ant systems for a dynamic TSP," in Ant Algorithms, LNCS, vol. 2463, M.
Dorigo, G. Di Caro, and M. Sampels, Eds. Berlin, Germany: Springer-Verlag, 2002, pp. 88-99.
[12] M. Guntsch and M. Middendorf, "Applying population based ACO to dynamic optimization problems," in
Ant Algorithms, LNCS, vol. 2463, M. Dorigo, G. Di Caro,
and M. Sampels, Eds. Berlin, Germany: Springer-Verlag,
2002, pp. 111-122.
[13] M. Guntsch, M. Middendorf, and H. Schmeck, "An
ant colony optimization approach to dynamic TSP," in
Proc. 3rd Annu. Conf. Genetic and Evolutionary Computation, GECCO'01, San Francisco: Morgan Kaufmann,
2001, pp. 860-867.
[14] M. Mavrovouniotis and S. Yang, "Ant colony optimization with immigrants schemes for the dynamic
travelling salesman problem with traffic factors," Appl.
Soft Comput., vol. 13, no. 10, pp. 4023-4037, Oct. 2013.
[15] J. Liu, "Rank-based ant colony optimization applied
to dynamic traveling salesman problems," Eng. Optim.,
vol. 37, no. 8, pp. 831-847, 2005.
[16] M. Guntsch and M. Middendorf, "Pheromone modification strategies for ant algorithms applied to dynamic
TSP," in Applications of Evolutionary Computation, LNCS,
vol. 2037, E. J. W. Boers, Ed. Berlin, Germany: SpringerVerlag, 2001, pp. 213-222.
[17] C. Silva and T. Runkler, "Ant colony optimization
for dynamic traveling salesman problems," in Proc. ARCS
Workshop, 2004, pp. 259-266.
[18] L. Kang, A. Zhou, B. McKay, Y. Li, and Z. Kang,
"Benchmarking algorithms for dynamic travelling salesman problems," in Proc. 2004 IEEE Congr. Evolutionary
Computation, Portland, OR, pp. 1286-1292.
[19] A. Siemin´ski, "Using ACS for dynamic traveling salesman problem," in New Research in Multimedia and Internet
Systems, vol. 314, A. Zgrzywa, K. Choros´, and A. Siemin´ski,
Eds. Cham: Springer-Verlag, 2015, pp. 145-155.
[20] R. Tinós, D. Whitley, and A. Howe, "Use of explicit
memory in the dynamic traveling salesman problem," in
Proc. 2014 Annu. Conf. Genetic and Evolutionary Computation, GECCO'14, New York: ACM, pp. 999-1006.
[21] M. Mavrovouniotis, S. Yang, and X. Yao, "A benchmark generator for dynamic permutation-encoded problems," in Parallel Problem Solving from Nature, PPSN XII,
LNCS, vol. 7492, C. Coello, V. Cutello, K. Deb, S. Forrest, G. Nicosia, and M. Pavone, Eds. Berlin, Germany:
Springer-Verlag, 2012, pp. 508-517.
[22] T. Weise et al., "Benchmarking optimization algorithms: An open source framework for the traveling salesman problem," IEEE Comput. Intell. Mag., vol. 9, no. 3,
pp. 40-52, Aug. 2014.
[23] H. Handa, L. Chapman, and X. Yao, "Robust route
optimization for gritting/salting trucks: A CERCIA experience," IEEE Comput. Intell. Mag., vol. 1, no. 1, pp.
6-9, Feb. 2006.
[24] A. E. Rizzoli, R. Montemanni, E. Lucibello, and
L. M. Gambardella, "Ant colony optimization for realworld vehicle routing problems," Swarm Intell., vol. 1, no.
2, pp. 135-151, Dec. 2007.
[25] A. Siemin´ski, "Using hyper populated ant colonies
for solving the TSP," Vietnam J. Comput. Sci., vol. 3, no.
2, pp. 103-117, May 2016.
[26] A. Prakasam and N. Savarimuthu, "Novel local
restart strategies with hyper-populated ant colonies for
dynamic optimization problems," Neural Comput. Appl.,
vol. 31, no. 1, pp. 63-76, Jan. 2019.
[27] M. Mavrovouniotis, F. M. Müller, and S. Yang, "Ant
colony optimization with local search for dynamic travelling salesman problems," IEEE Trans. Cybern., vol. 47, no.
7, pp. 1743-1756, July 2017.

[28] T. Stützle and H. Hoos, "MAX-MIN ant system and
local search for the traveling salesman problem," in Proc.
1997 IEEE Int. Conf. Evolutionary Computation, Indianapolis, IN, pp. 309-314.
[29] T. Stützle and H. H. Hoos, "MAX-MIN ant system,"
Future Gener. Comput. Syst., vol. 16, no. 8, pp. 889-914,
June 2000.
[30] D. Angus and T. Hendtlass, "Ant colony optimisation
applied to a dynamically changing problem," in Developments in Applied Artificial Intelligence, LNCS, vol. 2358, T.
Hendtlass and M. Ali, Eds. Berlin, Germany: SpringerVerlag, 2002, pp. 618-627.
[31] L. Melo, F. Pereira, and E. Costa, "Multi-caste ant
colony algorithm for the dynamic traveling salesperson
problem," in Adaptive and Natural Computing Algorithms,
LNCS, vol. 7824, M. Tomassini, A. Antonioni, F. Daolio,
and P. Buesser, Eds. Berlin, Germany: Springer-Verlag,
2013, pp. 179-188.
[32] M. Mavrovouniotis and S. Yang, "A memetic ant
colony optimization algorithm for the dynamic travelling salesman problem," Soft Comput., vol. 15, no. 7, pp.
1405-1425, July 2011.
[33] M. Mavrovouniotis and S. Yang, "Adapting the pheromone evaporation rate in dynamic routing problems," in
Applications of Evolutionary Computation, LNCS, vol. 7835,
A. Esparcia-Alcázar, Ed. Berlin, Germany: Springer-Verlag, 2013, pp. 606-615.
[34] M. Mavrovouniotis and S. Yang, "Ant colony optimization with self-adaptive evaporation rate in dynamic
environments," in Proc. 2014 IEEE Symp. Computational
Intelligence Dynamic and Uncertain Environments, Orlando,
FL, pp. 47-54.
[35] M. Mavrovouniotis and S. Yang, "Multi-colony ant
algorithms for the dynamic travelling salesman problem,"
in Proc. 2014 IEEE Symp. Computational Intelligence Dynamic and Uncertain Environments, Orlando, FL, pp. 9-16.
[36] M. Mavrovouniotis and S. Yang, "Ant colony optimization with immigrants schemes for dynamic environments," in Parallel Problem Solving from Nature, PPSN XI,
LNCS, vol. 6239, R. Schaefer, C. Cotta, J. Kołodziej,
and G. Rudolph, Eds. Berlin, Germany: Springer-Verlag,
2010, pp. 371-380.
[37] M. Mavrovouniotis and S. Yang, "Memory-based
immigrants for ant colony optimization in changing environments," in Applications of Evolutionary Computation,
LNCS, vol. 6624, C. Di Chio et al., Eds. Berlin, Germany: Springer-Verlag, 2011, pp. 324-333.
[38] M. Mavrovouniotis and S. Yang, "An immigrants
scheme based on environmental information for ant colony
optimization for the dynamic travelling salesman problem,"
in Artificial Evolution, LNCS, vol. 7401, J.-K. Hao, P. Legrand,
P. Collet, N. Monmarché, E. Lutton, and M. Schoenauer,
Eds. Berlin, Germany: Springer-Verlag, 2012, pp. 1-12.
[39] M. Mavrovouniotis and S. Yang, "Interactive and noninteractive hybrid immigrants schemes for ant algorithms
in dynamic environments," in Proc. 2014 IEEE Congr.
Evolutionary Computation, Beijing, China, pp. 1542-1549.
[40] G. Reinelt, "TSPLIB-A traveling salesman problem
library," ORSA J. Comput., vol. 3, no. 4, pp. 376-384,
Nov. 1991.
[41] K. Trojanowski and Z. Michalewicz, "Searching for
optima in non-stationary environments," in Proc. 1999
IEEE Congr. Evolutionary Computation, Washington, D.C.,
pp. 1843-1850.
[42] Y. Jin, K. Tang, X. Yu, B. Sendhoff, and X. Yao,
"A framework for finding robust optimal solutions over
time," Memetic Comput., vol. 5, no. 1, pp. 3-18, Mar. 2013.
[43] L. M. Gambardella and M. Dorigo, "Ant-Q: A
reinforcement learning approach to the traveling salesman problem," in Proc. 12th Int. Conf. Machine Learning,
A. Prieditis and S. Russell, Eds. San Francisco: Morgan
Kaufmann, 1995, pp. 252-260.
[44] D. Whitley, D. Hains, and A. Howe, "Tunneling
between optima: Partition crossover for the traveling
salesman problem," in Proc. 11th Annu. Conf. Genetic and
Evolutionary Computation, GECCO'09, New York: ACM,
2009, pp. 915-922.
[45] S. Yang, "Genetic algorithms with memory- and
elitism-based immigrants in dynamic environments,"
Evol. Comput., vol. 16, no. 3, pp. 385-416, 2008.

FEBRUARY 2020 | IEEE COMPUTATIONAL INTELLIGENCE MAGAZINE

63
https://github.com/Mavrovouniotis/ACODTSP https://github.com/Mavrovouniotis/ACODTSP
IEEE Computational Intelligence Magazine - February 2020

Table of Contents for the Digital Edition of IEEE Computational Intelligence Magazine - February 2020
