Abstract
In this paper, the travelling salesman problem (TSP) is tackled by coronavirus herd immunity optimizer (CHIO). TSP is the problem of finding the best tour for the salesman in order to visit all cities with minimum cost. In essential, this is a scheduling optimization problem that belongs to NP-hard class in almost all of its variants. CHIO is a recent human-based optimization algorithm that imitated the herd immunity strategy as a way to treat COVID-19 pandemic. The proposed method is evaluated against TSP models of various sizes and complexity including six models (25, 50, 100, 150, 200, and 300) cities. The obtained results are compared against four other methods. They are the genetic algorithm (GA), imperial competitive algorithm (ICA), Keshtel algorithm (KA), and red deer algorithm (RDA). The results prove that the CHIO is able to achieve the best obtained results for all large-scaled problems and produced very comparative results for small TSP problems.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
R. Matai, S.P. Singh, M.L. Mittal, Traveling salesman problem: an overview of applications, formulations, and solution approaches, in Traveling Salesman Problem, Theory and Applications, vol. 1 (2010)
S. Deb, S. Fong, Z. Tian, R.K. Wong, S. Mohammed, J. Fiaidhi, Finding approximate solutions of np-hard optimization and tsp problems using elephant search algorithm. J. Supercomput. 72(10), 3960–3992 (2016)
S. Arora, Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J. ACM (JACM) 45(5), 753–782 (1998)
R.W. Dewantoro, P. Sihombing, Sutarman, The combination of ant colony optimization (ACO) and Tabu search (TS) algorithm to solve the traveling salesman problem (TSP), in 2019 3rd International Conference on Electrical, Telecommunication and Computer Engineering (ELTICOM) (2019), pp. 160–164
X. Geng, Z. Chen, W. Yang, D. Shi, K. Zhao, Solving the traveling salesman problem based on an adaptive simulated annealing algorithm with greedy search. Appl. Soft Comput. 11(4), 3680–3689 (2011)
M.-H. Chen, S.-H. Chen, P.-C. Chang, Imperial competitive algorithm with policy learning for the traveling salesman problem. Soft Comput. 21(7), 1863–1875 (2017)
M. Hajiaghaei-Keshteli, M.J.A.S.C. Aminnayeri, Solving the integrated scheduling of production and rail transportation problem by Keshtel algorithm. Appl. Soft Comput. 25, 184–203 (2014)
A.M. Fathollahi-Fard, M. Hajiaghaei-Keshteli, R. Tavakkoli-Moghaddam. Red deer algorithm (RDA): a new nature-inspired meta-heuristic. Soft Comput. 1–29 (2020)
S.E. De León-Aldaco, H. Calleja, J.A. Alquicira, Metaheuristic optimization methods applied to power converters: a review. IEEE Trans. Power Electron. 30(12), 6791–6803 (2015)
M.A. Al-Betar, A.T. Khader, I.A. Doush, Memetic techniques for examination timetabling. Ann. Oper. Res. 218(1), 23–50 (2014)
M.A. Al-Betar, Z.A.A. Alyasseri, M. Awadallah, I.A. Doush, Coronavirus herd immunity optimizer (CHIO). Neural Comput. Appl. 1–32 (2020)
H. Braun, On solving travelling salesman problems by genetic algorithms, in International Conference on Parallel Problem Solving from Nature (Springer, Berlin, 1990), pp. 129–133
E. Osaba, X.-S. Yang, J. Del Ser, Traveling salesman problem: a perspective review of recent research and new results with bio-inspired metaheuristics, in Nature-Inspired Computation and Swarm Intelligence (Elsevier, Amsterdam, 2020), pp. 135–164
J.A. Regules, J.H. Beigel, K.M. Paolino, J. Voell, A.R. Castellano, Z. Hu, P. Muñoz, J.E. Moon, R.C. Ruck, J.W. Bennett et al., A recombinant vesicular stomatitis virus Ebola vaccine. New Engl. J. Med. 376(4), 330–341 (2017)
C.-C. Lai, T.-P. Shih, W.-C. Ko, H.-J. Tang, P.-R. Hsueh, Severe acute respiratory syndrome coronavirus 2 (SARS-CoV-2) and corona virus disease-2019 (COVID-19): the epidemic and the challenges. Int. J. Antimicrob. Agents 105924 (2020)
C.M. Pease, An evolutionary epidemiological mechanism, with applications to type a influenza. Theor. Population Biolo. 31(3), 422–452 (1987)
M.A. Awadallah, A.L. Bolaji, M.A. Al-Betar, A hybrid artificial bee colony for a nurse rostering problem. Appl. Soft Comput. 35, 726–739 (2015)
M.A. Al-Betar, A.T. Khader, M. Zaman, University course timetabling using a hybrid harmony search metaheuristic algorithm. IEEE Trans. Syst. Man Cybern. Part C (Appl. Rev.) 42(5), 664–681 (2012)
M.A. Al-Betar, University course timetabling using a hybrid harmony search metaheuristic algorithm. J. Ambient Intell. Humanized Comput. https://doi.org/10.1007/s12652-020-02047-2
Acknowledgements
The first author would like toas course timetabling, examination thank the Ajman University (AU) for supporting his Master of AI study and Research Assistant (RA) position.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper
Dalbah, L.M., Al-Betar, M.A., Awadallah, M.A., Zitar, R.A. (2022). A Coronavirus Herd Immunity Optimization (CHIO) for Travelling Salesman Problem. In: Khanna, A., Gupta, D., Bhattacharyya, S., Hassanien, A.E., Anand, S., Jaiswal, A. (eds) International Conference on Innovative Computing and Communications. Advances in Intelligent Systems and Computing, vol 1394. Springer, Singapore. https://doi.org/10.1007/978-981-16-3071-2_58
Download citation
DOI: https://doi.org/10.1007/978-981-16-3071-2_58
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-16-3070-5
Online ISBN: 978-981-16-3071-2
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)