The paper verifies the usefulness of a parallel and adaptive Ant Colony Communities (ACC) for solving the dynamic Travelling Salesman Problem (DTSP). ACC consists of a set of client colonies with a server to coordinate their work. Each one of the client colonies implements a standard ACO algorithm. The paper contains a detailed analysis of the operation of ACO for static TSP in order to identify its most dominant parameters. Graph Generator is used to modify the distances in TSP. In order to catch up with the constant changes the ACC should work in parallel and to adopt to the current distances. This is accomplished by modifying the number of iterations and changing the size of its internal prospective solutions buffer. Two implementations of ACC are presented: an asynchronous that works on computers connected through a LAN and a synchronous that uses a Hadoop environment. Numerous experiments clearly indicate, that the adaptive, parallel ACC outperforms both standard version of ACO as well as its versions adopted for DTSP. This is especially true for highly dynamic Graph Generators.
AbdelkafiO., LepagnotJ., IdoumgharL.Multilevel parallelization for hybrid aco, In International Conference on Swarm Intelligence Based Optimization, 2014, pp. 60–67. Springer.
2.
AntosiewiczM., KolochG., KamińskiB.Choice of best possible metaheuristic algorithm for the travelling salesman problem with limited computational time: Quality, uncertainty and speed, Journal of Theoretical and Applied Computer Science7(1) (2013)46–55.
3.
BoryczkaU. and StrąkŁ.Heterogeneous dpso algorithm for dtsp, In Computational Collective Intelligence, Springer, 2015, pp. 119–128.
4.
BullnheimerB., KotsisG. and StraußC.Parallelization strategies for the ant system, In High Performance Algorithms and Software in Nonlinear Optimization, Springer, 1998, pp. 87–100.
5.
CastilloO., NeyoyH., SoriaJ., MelinP., ValdezF.A new approach for dynamic fuzzy logic parameter tuning in ant colony optimization and its application in fuzzy control of a mobile robot, Applied Soft Computing28 (2015)150159.
6.
CeciliaJ.M., GarcíAJ.M., NisbetA., AmosM., UjaldónM.Enhancing data parallelism for ant colony optimization on gpus, Journal of Parallel and Distributed Computing73(1) (2013)42–51.
7.
ChiricoU. A java framework for ant colony systems, In Ants2004: Forth International Workshop on Ant Colony Optimization and Swarm Intelligence, Brussels, 2004.
8.
DongG., LiW., ShenJ., WangY., FuX., GuoW.Solving traveling salesman problems with ant colony optimization algorithms in sequential and parallel computing environments: A normalized comparison, International Journal of Machine Learning and Computing8(2) (2018).
9.
DorigoM.Optimization, learning and natural algorithms, Politecnico di Milano, PhD Thesis, 1992.
10.
DorigoM., StützleT.Ant colony optimization: Overview and recent advances, In Handbook of Metaheuristics, Springer, 2019, pp. 311–351.
11.
KopelM.Ant colony optimization in hadoop ecosystem, In Multimedia and Network Information Systems, Springer, 2017, pp. 193–201.
12.
MavrovouniotisM., EllinasG., PolycarpouM. Ant colony optimization for the electric vehicle routing problem, In 2018 IEEE Symposium Series on Computational Intelligence (SSCI), IEEE, 2018, pp. 1234–1241.
13.
MavrovouniotisM., YangS.Ant colony optimization with immigrants schemes for the dynamic traveling salesman problem with traffic factors, Applied Soft Computing13(10) (2013)4023–4037.
14.
MohanA., RemyaG.A parallel implementation of ant colony optimization for tsp based on mapreduce framework, International Journal of Computer Applications88(8) (2014).
15.
PedemonteM., NesmachnowS., CancelaH.A survey on parallel ant colony optimization, Applied Soft Computing11(8) (2011)5181–5197.
16.
PsaraftisH.N.Dynamic vehicle routing: Status and prospects, Annals of Operations Research61(1) (1995)143–164.
17.
PsaraftisH.N., WenM., KontovasC.A.Dynamic vehicle routing problems: Three decades and counting, Networks67(1) (2016)3–31.
18.
SiemińskiA.Ant colony optimization parameter evaluation, In Multimedia and Internet Systems: Theory and Practice, Springer, 2013, pp. 143–153.
19.
SiemińskiA.Potentials of hyper populated ant colonies. In Asian Conference on Intelligent Information and Database Systems, Springer, 2015a, pp. 408–417.
20.
SiemińskiA.Using acs for dynamic traveling salesman problem. In New Research in Multimedia and Internet Systems, Springer, 2015b, pp. 145–155.
21.
SiemińskiA.Parallel implementations of the ant colony optimization metaheuristic, In Asian Conference on Intelligent Information and Database Systems, Springer, 2016, pp. 626–635.
22.
SiemińskiA.Measuring efficiency of ant colony communities, In Multimedia and Network Information Systems, Springer, 2017, pp. 203–213.
23.
SiemińskiA.Verifying usefulness of ant colony community for solving dynamic tsp, In Asian Conference on Intelligent Information and Database Systems, Springer, 2019, pp. 224–235.
24.
SiemińskiA., KopelM.Comparing efficiency of aco parallel implementations, Journal of Intelligent & Fuzzy Systems32(2) (2017)1377–1388.
25.
SkinderowiczR.Implementing population-based aco, In International Conference on Computational Collective Intelligence, Springer, 2014, pp. 603–612.
26.
StützleT.Parallelization strategies for ant colony optimization, In International Conference on Parallel Problem Solving from Nature, Springer, 1998, pp. 722–731.
27.
TanQ., HeQ., ShiZ.Parallel max-min ant system using mapreduce, In International Conference in Swarm Intelligence, Springer, 2012, pp. 182–189.
28.
WangL., WangY., XieY.Implementation of a parallel algorithm based on a spark cloud computing platform, Algorithms8(3) (2015)407–414.
