Artificial rat optimization with decision-making: A bio-inspired metaheuristic algorithm for solving the traveling salesman problem




Bio-inspired; Metaheuristics; Rat Swarm Optimizer (RSO); Combinatorial optimization; TSP; Artificial intelligence (AI); Swarm intelligence (SI); Modeling systems.


In this paper, we present the Rat Swarm Optimization with Decision Making (HDRSO), a hybrid metaheuristic algorithm inspired by the hunting behavior of rats, for solving the Traveling Salesman Problem (TSP). The TSP is a well-known NP-hard combinatorial optimization problem with important applications in transportation, logistics, and manufacturing systems. To improve the search process and avoid getting stuck in local minima, we added a natural mechanism to HDRSO through the incorporation of crossover and selection operators. In addition, we applied 2-opt and 3-opt heuristics to the best solution found by HDRSO. The performance of HDRSO was evaluated on a set of symmetric instances from the TSPLIB library and the results demonstrated that HDRSO is a competitive and robust method for solving the TSP, achieving better results than the best-known solutions in some cases.


Download data is not yet available.


Abualigah, L., Elaziz, M. A., Sumari, P., Khasawneh, A. M., Alshinwan, M., Mirjalili, S., Shehab, M., Abuaddous, H. Y., & Gandomi, A. H. (2022). Black hole algorithm: A comprehensive survey. Applied Intelligence, 52(10), 11892–11915.

Anuar, S., Selamat, A., & Sallehuddin, R. (2016). A modified scout bee for artificial bee colony algorithm and its performance on optimization problems. Journal of King Saud University - Computer and Information Sciences, 28(4), 395–406.

Atashpaz-Gargari, E., & Lucas, C. (2007). Imperialist competitive algorithm: An algorithm for optimization inspired by imperialistic competition. 2007 IEEE Congress on Evolutionary Computation, 4661–4667.

Barbarosoglu, G., & Ozgur, D. (1999). A tabu search algorithm for the vehicle routing problem. Computers & Operations Research, 26(3), 255–270.

BAŞ, E., & ÜLKER, E. (2021). Dıscrete socıal spıder algorıthm for the travelıng salesman problem. Artificial Intelligence Review, 54(2), 1063–1085.

Chung, S. W., & Freund, J. B. (2022). An optimization method for chaotic turbulent flow. Journal of Computational Physics, 457, 111077.

Cinar, A. C., Korkmaz, S., & Kiran, M. S. (2020). A discrete tree-seed algorithm for solving symmetric traveling salesman problem. Engineering Science and Technology, an International Journal, 23(4), 879–890.

Cotta, C., Mathieson, L., & Moscato, P. (2018). Memetic Algorithms. In Handbook of Heuristics (pp. 607–638). Springer International Publishing.

Dorigo, M., & Gambardella, L. M. (1997). Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation, 1(1), 53–66.

Ezugwu, A. E.-S., & Adewumi, A. O. (2017). Discrete symbiotic organisms search algorithm for travelling salesman problem. Expert Systems with Applications, 87, 70–78.

Ezugwu, A. E., Shukla, A. K., Nath, R., Akinyelu, A. A., Agushaka, J. O., Chiroma, H., & Muhuri, P. K. (2021). Metaheuristics: a comprehensive overview and classification along with bibliometric analysis. Artificial Intelligence Review, 54(6), 4237–4316.

Ginidi, A., Ghoneim, S. M., Elsayed, A., El-Sehiemy, R., Shaheen, A., & El-Fergany, A. (2021). Gorilla Troops Optimizer for Electrically Based Single and Double-Diode Models of Solar Photovoltaic Systems. Sustainability, 13(16), 9459.

Gunduz, M., & Aslan, M. (2021). DJAYA: A discrete Jaya algorithm for solving traveling salesman problem. Applied Soft Computing, 105, 107275.

Kaveh, A., & Dadras, A. (2017). A novel meta-heuristic optimization algorithm: Thermal exchange optimization. Advances in Engineering Software, 110, 69–84.

Kennedy, J., & Eberhart, R. (n.d.). Particle swarm optimization. Proceedings of ICNN’95 - International Conference on Neural Networks, 1942–1948.

Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1987). Optimization by Simulated Annealing. In Readings in Computer Vision (pp. 606–615). Elsevier.

Koza, J. R., & Poli, R. (2005). Genetic Programming. In E. K. Burke & G. Kendall (Eds.), Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques (pp. 127–164). Springer US.

Kumar, A., Vohra, M., Pant, S., & Singh, S. K. (2021). Optimization techniques for petroleum engineering: A brief review. International Journal of Modelling and Simulation, 41(5), 326–334.

Kumar, J., Kumar Singh, A., Mohan, A., & Buyya, R. (2021). Metaheuristic Optimization Algorithms. In Machine Learning for Cloud Management (pp. 59–74). Chapman and Hall/CRC.

Lee, K. S., & Geem, Z. W. (2004). A new structural optimization method based on the harmony search algorithm. Computers & Structures, 82(9–10), 781–798.

Lourenço, H. R., Martin, O. C., & Stützle, T. (2010). Iterated Local Search: Framework and Applications (pp. 363–397).

Medjahed, S. A., Ait Saadi, T., Benyettou, A., & Ouali, M. (2016). Gray Wolf Optimizer for hyperspectral band selection. Applied Soft Computing, 40, 178–186.

Mirjalili, S., Gandomi, A. H., Mirjalili, S. Z., Saremi, S., Faris, H., & Mirjalili, S. M. (2017). Salp Swarm Algorithm: A bio-inspired optimizer for engineering design problems. Advances in Engineering Software, 114, 163–191.

Mirjalili, S. Z., Mirjalili, S., Saremi, S., Faris, H., & Aljarah, I. (2018). Grasshopper optimization algorithm for multi-objective optimization problems. Applied Intelligence, 48(4), 805–820.

Mladenović, N., & Hansen, P. (1997). Variable neighborhood search. Computers & Operations Research, 24(11), 1097–1100.

Mzili, T., Riffi, M. E., Mzili, I., & Dhiman, G. (2022). A novel discrete Rat swarm optimization (DRSO) algorithm for solving the traveling salesman problem. Decision Making: Applications in Management and Engineering, 5(2), 287–299.

Opara, K. R., & Arabas, J. (2019). Differential Evolution: A survey of theoretical analyses. Swarm and Evolutionary Computation, 44, 546–558.

Osaba, E., Yang, X.-S., & Del Ser, J. (2020). Traveling salesman problem: a perspective review of recent research and new results with bio-inspired metaheuristics. In Nature-Inspired Computation and Swarm Intelligence (pp. 135–164). Elsevier.

Pereira, J. L. J., Francisco, M. B., Diniz, C. A., Antônio Oliver, G., Cunha, S. S., & Gomes, G. F. (2021). Lichtenberg algorithm: A novel hybrid physics-based meta-heuristic for global optimization. Expert Systems with Applications, 170, 114522.

Peres, F., & Castelli, M. (2021). Combinatorial Optimization Problems and Metaheuristics: Review, Challenges, Design, and Development. Applied Sciences, 11(14), 6449.

Prajapati, V. K., Jain, M., & Chouhan, L. (2020). Tabu Search Algorithm (TSA): A Comprehensive Survey. 2020 3rd International Conference on Emerging Technologies in Computer Engineering: Machine Learning and Internet of Things (ICETCE), 1–8.

Rahman, Md. A., & Parvez, H. (2021). Repetitive Nearest Neighbor Based Simulated Annealing Search Optimization Algorithm for Traveling Salesman Problem. OALib, 08(06), 1–17.

Rashedi, E., Nezamabadi-pour, H., & Saryazdi, S. (2009). GSA: A Gravitational Search Algorithm. Information Sciences, 179(13), 2232–2248.

Rawat, S. S., Pant, S., Kumar, A., Ram, M., Sharma, H. K., & Kumar, A. (2022). A State-of-the-Art Survey on Analytical Hierarchy Process Applications in Sustainable Development. International Journal of Mathematical, Engineering and Management Sciences, 7(6), 883–917.

Saji, Y., & Riffi, M. E. (2016). A novel discrete bat algorithm for solving the travelling salesman problem. Neural Computing and Applications, 27(7), 1853–1866.

Simon, D. (2008). Biogeography-Based Optimization. IEEE Transactions on Evolutionary Computation, 12(6), 702–713.

Slowik, A., & Kwasnicka, H. (2020). Evolutionary algorithms and their applications to engineering problems. Neural Computing and Applications, 32(16), 12363–12379.

Sun, L. (2015). Genetic Algorithm for TSP Problem.

Tanaev, V. S., Gordon, V. S., & Shafransky, Y. M. (1994). NP-Hard Problems. In Scheduling Theory. Single-Stage Systems (pp. 253–311). Springer Netherlands.

Uniyal, N., Pant, S., Kumar, A., & Pant, P. (2022). Nature-inspired metaheuristic algorithms for optimization. In Meta-heuristic Optimization Techniques (pp. 1–10). De Gruyter.

Wu, C., Fu, X., Pei, J., & Dong, Z. (2021). A Novel Sparrow Search Algorithm for the Traveling Salesman Problem. IEEE Access, 9, 153456–153471.

Xu, G.-H., Zhang, T.-W., & Lai, Q. (2022). A new firefly algorithm with mean condition partial attraction. Applied Intelligence, 52(4), 4418–4431.

Yang, X.-S. (2009a). Firefly Algorithms for Multimodal Optimization (pp. 169–178).

Yang, X.-S. (2009b). Firefly Algorithms for Multimodal Optimization (pp. 169–178).

Yang, X.-S. (2010). A New Metaheuristic Bat-Inspired Algorithm (pp. 65–74).

Yang, X.-S., & Deb, S. (2009). Cuckoo Search via Lévy flights. 2009 World Congress on Nature & Biologically Inspired Computing (NaBIC), 210–214.

Zhong, X. (2021). On the approximation ratio of the 3-Opt algorithm for the (1,2)-TSP. Operations Research Letters, 49(4), 515–521.



How to Cite

Mzili, T., Mzili, I. ., & Riffi , M. E. . (2023). Artificial rat optimization with decision-making: A bio-inspired metaheuristic algorithm for solving the traveling salesman problem. Decision Making: Applications in Management and Engineering, 6(2), 150–176.