The dynamic traveling salesman problem (DTSP) falls under the category of combinatorial dynamic optimization problems. The DTSP is composed of a primary TSP sub-problem and a series of TSP iterations; each iteration is created by changing the previous iteration. In this article, a novel hybrid metaheuristic algorithm is proposed for the DTSP. This algorithm combines two metaheuristic principles, specifically ant colony optimization (ACO) and simulated annealing (SA). Moreover, the algorithm exploits knowledge about the dynamic changes by transferring the information gathered in previous iterations in the form of a pheromone matrix. The significance of the hybridization, as well as the use of knowledge about the dynamic environment, is examined and validated on benchmark instances including small, medium, and large DTSP problems. The results are compared to the four other state-of-the-art metaheuristic approaches with the conclusion that they are significantly outperformed by the proposed algorithm. Furthermore, the behavior of the algorithm is analyzed from various points of view (including, for example, convergence speed to local optimum, progress of population diversity during optimization, and time dependence and computational complexity).

Department of Intelligence Support University of Defence Kounicova 65 662 10 Brno Czech Republic

Department of Military Geography and Meteorology University of Defence Kounicova 65 662 10 Brno Czech Republic

Zobrazit více v PubMed

Li W. A Parallel Multi-Start Search Algorithm for Dynamic Traveling Salesman Problem; Proceedings of the International Symposium on Experimental Algorithms; Crete, Greece. 5–7 May 2011; pp. 65–75.

Stodola P., Mazal J. Tactical Decision Support System to Aid Commanders in their Decision-Making; Proceedings of the Modelling and Simulation for Autonomous Systems; Rome, Italy. 15–16 June 2016; pp. 396–406.

Stodola P., Mazal J. Model of Optimal Cooperative Reconnaissance and its Solution using Metaheuristic Methods. Def. Sci. J. 2017;67:529–535. doi: 10.14429/dsj.67.10530. DOI

Drozd J., Neubauer J. Use of an aerial reconnaissance model during the movement of oversized loads. J. Déf. Model. Simul. Appl. Methodol. Technol. 2019 doi: 10.1177/1548512919866928. DOI

Drozd J. Experiment of the Tactical Decision Support System within Company Defensive Operation; Proceedings of the Modelling and Simulation for Autonomous Systems; Prague, Czech Republic. 17–19 October 2018; pp. 544–552.

Rolenec O., Silinger K., Palasiewicz T., Zizka P. Supporting the decision-making process in the planning and controlling of engineer task teams to support mobility in a combat operation. Int. J. Educ. Inf. Technol. 2019;13:33–40.

Hodicky J., Prochazka D., Prochazka J. Training with and of Autonomous System—Modelling and Simulation Approach; Proceedings of the Modelling and Simulation for Autonomous Systems; Rome, Italy. 24–26 October 2017; pp. 383–391.

Bruzzone A.G., Massei M., Di Matteo R., Kutej L. Introducing Intelligence and Autonomy into Industrial Robots to Address Operations into Dangerous Area; Proceedings of the Modelling and Simulation for Autonomous Systems; Prague, Czech Republic. 17–19 October 2018; pp. 433–444.

Otrisal P., Obsel V., Buk J., Švorc L. Preparation of Filtration Sorptive Materials from Nanofibers, Bicofibers, and Textile Adsorbents without Binders Employment. Nanomaterials. 2018;8:564. doi: 10.3390/nano8080564. PubMed DOI PMC

Blaha M., Silinger K. Application support for topographical-geodetic issues for tactical and technical control of artillery fire. Int. J. Circuits Syst. Signal Process. 2018;12:48–57.

Flood M.M. The Traveling-Salesman Problem. Oper. Res. 1956;4:61–75. doi: 10.1287/opre.4.1.61. DOI

Dantzig G., Fulkerson R., Johnson S. Solution of a Large-Scale Traveling-Salesman Problem. J. Oper. Res. Soc. Am. 1954;2:393–410. doi: 10.1287/opre.2.4.393. DOI

Applegate D.L., Bixby R.E., Chvátal V., Cook W.J. The Travelling Salesman Problem: A Computational Study. Princeton University Press; Princeton, NJ, USA: 2006.

Reinelt G. TSPLIB—A Traveling Salesman Problem Library. ORSA J. Comput. 1991;3:376–384. doi: 10.1287/ijoc.3.4.376. DOI

Applegate D., Bixby R.E., Chvátal V., Cook W., Espinoza D.G., Goycoolea M., Helsgaun K. Certification of an optimal TSP tour through 85,900 cities. Oper. Res. Lett. 2009;37:11–15. doi: 10.1016/j.orl.2008.09.006. DOI

Lin S., Kernighan B.W. An Effective Heuristic Algorithm for the Traveling-Salesman Problem. Oper. Res. 1973;21:498–516. doi: 10.1287/opre.21.2.498. DOI

Applegate D., Cook W., Rohe A. Chained Lin-Kernighan for Large Traveling Salesman Problems. INFORMS J. Comput. 2003;15:82–92. doi: 10.1287/ijoc.15.1.82.15157. DOI

Helsgaun K. An effective implementation of the Lin–Kernighan traveling salesman heuristic. Eur. J. Oper. Res. 2000;126:106–130. doi: 10.1016/S0377-2217(99)00284-2. DOI

Solving TSPs: World TSP. [(accessed on 30 June 2020)]; Available online: http://www.math.uwaterloo.ca/tsp/world/index.html.

Dahan F., El Hindi K., Mathkour H., Alsalman H., Hindi E. Dynamic Flying Ant Colony Optimization (DFACO) for Solving the Traveling Salesman Problem. Sensors. 2019;19:1837. doi: 10.3390/s19081837. PubMed DOI PMC

Ahmed A.K.M.F., Sun J.U. An Improved Particle Swarm Optimization Algorithm for the Travelling Salesman Problem. Adv. Sci. Lett. 2016;22:3318–3322. doi: 10.1166/asl.2016.7864. DOI

Shirdel G.H., Abdolhosseinzadeh M. A simulated annealing heuristic for the online symmetric traveling salesman problem. J. Inf. Optim. Sci. 2018;39:1–14. doi: 10.1080/02522667.2017.1367494. DOI

Jafarzadeh H., Moradinasab N., Elyasi M. An Enhanced Genetic Algorithm for the Generalized Traveling Salesman Problem. Eng. Technol. Appl. Sci. Res. 2017;7:2260–2265.

Akhand M.A.H., Ayon S.I., Shahriyar S., Siddique N., Adeli H. Discrete Spider Monkey Optimization for Travelling Salesman Problem. Appl. Soft Comput. 2020;86:105887. doi: 10.1016/j.asoc.2019.105887. DOI

Khan I., Pal S., Maiti M.K. A Hybrid PSO-GA Algorithm for Traveling Salesman Problems in Different Environments. Int. J. Uncertain. Fuzziness Knowl. Based Syst. 2019;27:693–717. doi: 10.1142/S0218488519500314. DOI

Yu M. A solution of TSP based on the ant colony algorithm improved by particle swarm optimization. Discret. Contin. Dyn. Syst. S. 2019;12:979–987. doi: 10.3934/dcdss.2019066. DOI

Hertono G.F., Handari B.D. The Modification of Hybrid Method of Ant Colony Optimization, Particle Swarm Optimization and 3-OPT Algorithm in Traveling Salesman Problem; Proceedings of the International Conference on Mathematics: Pure, Applied and Computation; Surabaya, Indonesia. 1 November 2017.

Mavrovouniotis M., Yang S. Ant colony optimization with immigrants schemes for the dynamic travelling salesman problem with traffic factors. Appl. Soft Comput. 2013;13:4023–4037. doi: 10.1016/j.asoc.2013.05.022. DOI

Ma A.X., Zhang X.H., Zhang C.S., Zhang B., Gao Y. An Adaptive Ant Colony Algorithm for Dynamic Traveling Salesman Problem. J. Inf. Sci. Eng. 2019;35:1263–1277.

Chowdhury S., Marufuzzaman M., Tunc H., Bian L., Bullington W. A modified Ant Colony Optimization algorithm to solve a dynamic traveling salesman problem: A case study with drones for wildlife surveillance. J. Comput. Des. Eng. 2018;6:368–386. doi: 10.1016/j.jcde.2018.10.004. DOI

Mavrovouniotis M., Van M., Yang S.X. Pheromone Modification Strategy for the Dynamic Travelling Salesman Problem with Weight Changes; Proceedings of the IEEE Symposium Series on Computational Intelligence; Honolulu, HI, USA. 27 November–1 December 2017.

Sieminski A. Solving Dynamic Traveling Salesman Problem with Ant Colony Communities; Proceedings of the International Conference on Computational Collective Intelligence; Nicosia, Cyprus. 27–29 September 2017.

Schmitt J.P., Baldo F., Parpinelli R.S. A MAX-MIN Ant System with Short-term Memory Applied to the Dynamic and Asymmetric Traveling Salesman Problem; Proceedings of the Brazilian Conference on Intelligent Systems; Sao Paulo, Brazil. 22–25 October 2018.

Strąk Ł., Skinderowicz R., Boryczka U., Nowakowski A. A Self-Adaptive Discrete PSO Algorithm with Heterogeneous Parameter Values for Dynamic TSP. Entropy. 2019;21:738. doi: 10.3390/e21080738. PubMed DOI PMC

Strąk Ł., Skinderowicz R., Boryczka U. Adjustability of a discrete particle swarm optimization for the dynamic TSP. Soft Comput. 2017;22:7633–7648. doi: 10.1007/s00500-017-2738-9. DOI

Simoes A., Costa E. Extended Virtual Loser Genetic Algorithm for the Dynamic Traveling Salesman Problem; Proceedings of the Genetic and Evolutionary Computation Conference; Amsterdam, The Netherlands. 6–10 July 2013.

Groba C., Sartal A., Vázquez X.H. Solving the dynamic traveling salesman problem using a genetic algorithm with trajectory prediction: An application to fish aggregating devices. Comput. Oper. Res. 2015;56:22–32. doi: 10.1016/j.cor.2014.10.012. DOI

Boryczka U., Strak L. A Hybrid Discrete Particle Swarm Optimization with Pheromone for Dynamic Traveling Salesman Problem; Proceedings of the International Conference on Computational Collective Intelligence; Ho Chi Minh City, Vietnam. 28–30 November 2012.

Mavrovouniotis M., Muller F.M., Yang S. Ant Colony Optimization With Local Search for Dynamic Traveling Salesman Problems. IEEE Trans. Cybern. 2017;47:1743–1756. doi: 10.1109/TCYB.2016.2556742. PubMed DOI

Saian R., Ku-Mahamud K.R. Hybrid Ant Colony Optimization and Simulated Annealing for Rule Induction; Proceedings of the European Symposium on Computer Modeling and Simulation; Madrid, Spain. 16–18 November 2011.

Saian R. Ph.D. Thesis. Universiti Utara Malaysia; Changlun, Malaysia: 2013. A Hybrid of Ant Colony Optimization Algorithm and Simulated Annealing for Classification Rules.

Hoseini P., Shayesteh M.G. Hybrid Ant Colony Optimization, Genetic Algorithm, and Simulated Annealing for image contrast enhancement; Proceedings of the IEEE Congress on Evolutionary Computation; Barcelona, Spain. 18–23 July 2010.

Hoseini P., Shayesteh M.G. Efficient contrast enhancement of images using hybrid ant colony optimisation, genetic algorithm, and simulated annealing. Digit. Signal Process. 2013;23:879–893. doi: 10.1016/j.dsp.2012.12.011. DOI

Liu B., Meng P. Simulated annealing-based ant colony algorithm for traveling salesman problems. J. Huazhong Univ. Sci. Technol. 2009;37:26–30.

Mohsen A.M. Annealing Ant Colony Optimization with Mutation Operator for Solving TSP. Comput. Intell. Neurosci. 2016;2016:1–13. doi: 10.1155/2016/8932896. PubMed DOI PMC

Mazal J., Stodola P. Applying the ant colony optimisation algorithm to the capacitated multi-depot vehicle routing problem. Int. J. Bio-Inspired Comput. 2016;8:228. doi: 10.1504/IJBIC.2016.10000256. DOI

Discrete and Combinatorial Optimization. [(accessed on 30 June 2020)]; Available online: http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp/

Wang Y., Gao S., Todo Y. Swarm Intelligence—Volume 1: Principles, Current Algorithms and Methods. The Institution of Engineering and Technology; London, UK: 2018. Ant colony systems for optimization problems in dynamic environments.

Skinderowicz R. Implementing Population-Based ACO; Proceedings of the International Conference on Computational Collective Intelligence; Seoul, Korea. 23–26 September 2014; pp. 603–612.

Ma Z.B., Liu L.T., Sukhatme G.S. An Adaptive k-opt Method for Solving Traveling Salesman Problem; Proceedings of the IEEE Conference on Decision and Control; Las Vegas, NV, USA. 12–14 December 2016.

Bentley J.J. Fast Algorithms for Geometric Traveling Salesman Problems. INFORMS J. Comput. 1992;4:387–411. doi: 10.1287/ijoc.4.4.387. DOI

Artificial Intelligence and Computational Methods in the Modeling of Complex Systems