An APPLICATION of A MODIFIED CAMEL TRAVELING BEHAVIOR ALGORITHM for TRAVELING SALESMAN PROBLEM

Year 2021, Issue: 047, 88 - 98, 31.12.2021

Mehmet Fatih Demiral

Abstract

Camel Traveling Behavior Algorithm (CA) is a fairly new algorithm developed in 2016 by Mohammed Khalid Ibrahim and Ramzy Salim Ali. Scientists have put forward a few publications on CA. CA was applied to continuous optimization problems and engineering problems in the literature. It has been shown that CA has comparable performance with Particle Swarm Optimization (PSO) and Genetic Algorithm (GA). Besides, a modified camel algorithm (MCA) has been implemented in the field of engineering and was showed that it has competitive performance with Cuckoo Search (CS), PSO, and CA. In this work, an application of MCA has been done in the traveling salesman problem. A set of classical datasets which have cities scale ranged from 51 to 150 was used in the application. The results show that the MCA is superior to Simulated Annealing (SA), Tabu Search (TS), GA, and CA for 60% of all datasets. Also, it was given that a detailed analysis presents the number of best, worst, average solutions, standard deviation, and the average CPU time concerning meta-heuristics. The metrics stress that MCA demonstrates a performance rate over 50% in finding optimal solutions. Finally, MCA solves the discrete problem in reasonable times in comparison to other algorithms for all datasets.

Keywords

Modified Camel Algorithm, Meta-heuristic Algorithms, Traveling Salesman Problem

References

• [1] Parejo, J.A., Ruiz-Cortés, A., Lozano, S., and Fernandez, P., (2012). Metaheuristic optimization frameworks: a survey and benchmarking. Soft Computing, 16, 527–561. https://doi.org/10.1007/s00500-011-0754-8.
• [2] Cárdenas-Montes, M., (2018). Creating hard-to-solve instances of travelling salesman problem. Applied Soft Computing, 71, 268-276. https://doi.org/10.1016/j.asoc.2018.07.010.
• [3] Yang, XS., (2010). Nature-inspired metaheuristic algorithms. United Kingdom (Bristol): Luniver Press.
• [4] Gogna, A. and Tayal, A., (2013). Metaheuristics: review and application. Journal of Experimental & Theoretical Artificial Intelligence, 25(4), 503–526. http://doi.org/10.1080/0952813X.2013.782347
• [5] Rajpurohit, J., Sharma, T.K., Abraham, A., and Vaishali, (2017). Glossary of metaheuristic algorithms. International Journal of Computer Information Systems and Industrial Management Applications, 9, 181-205.
• [6] Karaboga, D. and Basturk, B., (2007). A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm. Journal of Global Optimization, 39(3), 459– 471.
• [7] Hatamlou, A., (2018). Solving travelling salesman problem using black hole algorithm. Soft Computing, 22(24), 8167-8175. https://doi.org/10.1007/s00500-017-2760-y.
• [8] Mirjalili, S., (2016). A sine cosine algorithm for solving optimization problems. Knowledge- Based Systems, 96, 120-133.
• [9] Yazdani, M. and Jolai, F., (2016). Lion optimization algorithm (LOA): A nature-inspired metaheuristic algorithm. Journal of Computational Design and Engineering, 3(1), 24-36.
• [10] Zheng, Y.J., (2015). Water wave optimization: a new nature-inspired metaheuristic. Computers & Operations Research, 55:1–11.
• [11] Yildirim, A.E. and Karci A., (2018). Applications of artificial atom algorithm to small-scale traveling salesman problems. Soft Computing, 22(22), 7619-7631. https://doi.org/10.1007/s00500-017-2735-z.
• [12] Feng, X., Liu, Y., Yu, H., and Luo, F. (2019). Physarum-energy optimization algorithm. Soft Computing, 23, 871–888. https://doi.org/10.1007/s00500-017-2796-z.
• [13] Dorigo, M., Birattari, M., and Stutzle, T., (2006, Nov). Ant colony optimization. IEEE Computational Intelligence Magazine, 1(4), 28-39.
• [14] Akça, M.R. (2011). Yapay arı kolonisi algoritması kullanılarak gezgin satıcı probleminin Türkiye’deki il ve ilçe merkezlerine uygulanması, Selçuk Üniversitesi Fen Bilimleri Enstitüsü, Konya.
• [15] Bektas, T., (2006). The multiple traveling salesman problem: an overview of formulations and solution procedures. Omega, 34(3), 209-219.
• [16] Ibrahim, M.K. and Ali, R.S., (2016). Novel optimization algorithm inspired by camel traveling behavior. Iraqi Journal for Electrical and Electronic Engineering, 12(2), 167-177.
• [17] Ali, R.S., Alnahwi, F.M., and Abdullah, A.S., (2019). A modified camel travelling behavior algorithm for engineering applications. Australian Journal of Electrical and Electronics Engineering, 16(3), 176-186. https://doi.org/10.1080/1448837X.2019.1640010.
• [18] Hassan, K.H, Abdulmuttalib, T.R., and Jasim, B.H., (2021, Feb). Parameters estimation of solar photovoltaic module using camel behavior search algorithm. International Journal of Electrical and Computer Engineering (IJECE), 11(1), 788-793.
• [19] Burkard, R.E., Deineko, V.G., van Dal, R., van, J.A.A., Veen, der, and Woeginger, G.J., (1998). Well-solvable special cases of the traveling salesman problem: a survey. Society for Industrial and Applied Mathematics, 40(3), 496-546. https://doi.org/10.1137/S0036144596297514.
• [20] Sahana, S.K., (2019). Hybrid optimizer for the travelling salesman problem. Evolutionary Intelligence, 12, 179–188. https://doi.org/10.1007/s12065-019-00208-7.
• [21] Nagata, Y. and Soler, D., (2012). A new genetic algorithm for the asymmetric traveling salesman problem. Expert Systems with Applications, 39(10), 8947-8953. https://doi.org/10.1016/j.eswa.2012.02.029.
• [22] Osaba, E., Yang, XS., Diaz, F., Lopez-Garcia, P., and Carballedo, R., (2016). An improveddiscrete bat algorithm for symmetric and asymmetric traveling salesman problems. Engineering Applications of Artificial Intelligence, 48, 59-71. https://doi.org/10.1016/j.engappai.2015.10.006
• [23] Öncan, T., Altınel, İ.K., and Laporte, G., (2009). A comparative analysis of several asymmetric traveling salesman problem formulations. Computers & Operations Research, 36(9), 637- 654.https://doi.org/10.1016/j.cor.2007.11.008.
• [24] Malik, W., Rathinam, S., and Darbha, S., (2007). An approximation algorithm for a symmetric generalized multiple depot, multiple travelling salesman problem. Operations Research Letters, 35(6), 747-753. https://doi.org/10.1016/j.orl.2007.02.001.
• [25] Asih, A.M.S., Sopha, B.M., and Kriptaniadewa, G., (2017). Comparison study of metaheuristics: empirical application of delivery problems. International Journal of Engineering Business Management, 9, 1-12. https://doi.org/10.1177/1847979017743603.
• [26] Khanra, A., Maiti, M.K., and Maiti, M., (2015). Profit maximization of tsp through a hybrid algorithm. Computers & Industrial Engineering, 88, 229-236. https://doi.org/10.1016/j.cie.2015.06.018.
• [27] Halim, A.H. and Ismail, I., (2019). Combinatorial optimization: comparison of heuristic algorithms in travelling salesman problem. Archives of Computational Methods in Engineering, 26, 367–380. https://doi.org/10.1007/s11831-017-9247-y.
• [28] Szeto, W.Y., Yongzhong, W. and Ho, S.C., (2011). An artificial bee colony algorithm for the capacitated vehicle routing problem. European Journal of Operational Research, 215(1), 126- 135. https://doi.org/10.1016/j.ejor.2011.06.006.
• [29] Demiral, M.F. and Işik, A.H., (2020). Simulated annealing algorithm for a medium-sized tsp data. In: D. J. Hemanth and U. Kose (Eds), Artificial Intelligence and Applied Mathematics in Engineering Problems. ICAIAME 2019. Lecture Notes on Data Engineering and Communications Technologies, 43. Springer, Cham, pp. 457-465. https://doi.org/10.1007/978-3- 030-36178-5_35.