A Novel Hybrid Approach for Solving the Traveling Salesman Problem: Combining Local Search Techniques for Enhanced Performance

Abstract

The Traveling Salesman Problem (TSP) is a classic combinatorial optimization problem. It involves finding the most efficient route that visits a set of cities exactly once and returns to the starting point. The development of an efficient solution to this problem is of great practical importance, particularly in the context of logistical and transportation applications. Some of the classic local search methods that have been adopted in the quest for better solutions include 2-Opt, 3-Opt, Slide, and Swap. These methods generate neighboring solutions in a systematic manner, eliminating suboptimal routes and thus improving the quality of the solutions. Among these, the 2-Opt method involves the elimination of crossed edges in the route. In contrast, the 3-Opt extends this concept to more complex changes, and while it may have the potential to generate superior solutions, it does so at a higher computational cost. The aim of this study is to provide a comprehensive investigation of the performance of the four methods: 2-Opt, 3-Opt, Slide, and Swap. Additionally, this paper proposes a hybrid method, HLSA, which incorporates all four methods in a systematic and balanced manner: 30% 2-Opt, 30% 3-Opt, 20% Slide, and 20% Swap. This approach is designed to yield more optimized results. The results demonstrate that the HLSA is significantly faster and more effective than traditional algorithms, as evidenced by rigorous experimentation and comparison. Furthermore, the solution to TSP has been shown to be both practical and efficient, making it a viable candidate for real-world implementation.

Keywords

• Traveling Salesman Problem
• local search
• Swap
• Slide
• 2-Opt
• 3-Opt

References

1. [1] M. Englert, H. Röglin, and B. Vöcking, “Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP,” Algorithmica, vol. 68, no. 1, pp. 190–264, 2014.
2. [2] A. H. Halim and Ija. Ismail, “Combinatorial optimization: comparison of heuristic algorithms in travelling salesman problem,” Archives of Computational Methods in Engineering, vol. 26, pp. 367–380, 2019.
3. [3] G. F. Hertono and B. D. Handari, “The modification of hybrid method of ant colony optimization, particle swarm optimization and 3-OPT algorithm in traveling salesman problem,” in Journal of Physics: Conference Series, IOP Publishing, 2018, p. 012032.
4. [4] X. Yang et al., “A review: machine learning for combinatorial optimization problems in energy areas,” Algorithms, vol. 15, no. 6, p. 205, 2022.
5. [5] M. Mahi, Ö. K. Baykan, and H. Kodaz, “A new hybrid method based on particle swarm optimization, ant colony optimization and 3-opt algorithms for traveling salesman problem,” Appl Soft Comput, vol. 30, pp. 484–490, 2015.
6. [6] S. Singh and E. A. Lodhi, “Study of variation in TSP using genetic algorithm and its operator comparison,” International Journal of Soft Computing and Engineering, vol. 3, no. 2, pp. 264–267, 2013.
7. [7] N. Yagmur, I. Dag, and H. Temurtas, “A new computer‐aided diagnostic method for classifying anaemia disease: Hybrid use of Tree Bagger and metaheuristics,” Expert Syst, p. e13528, 2023.
8. [8] N. Yagmur, İ. Dag, and H. Temurtas, “Classification of anemia using Harris hawks optimization method and multivariate adaptive regression spline,” Neural Comput Appl, pp. 1–20, 2024.

9. [9] S. Dörterler, H. Dumlu, D. Özdemir, and H. Temurtaş, “Hybridization of Meta-heuristic Algorithms with K-Means for Clustering Analysis: Case of Medical Datasets,” Gazi Mühendislik Bilimleri Dergisi, pp. 1–23.
10. [10] S. Dörterler, H. Dumlu, D. Özdemir, and H. Temurtaş, “Hybridization of K-means and Meta-Heuristics Algorithms for Heart Disease Diagnosis,” in NEW TRENDS IN ENGINEERING AND APPLIED NATURAL SCIENCES, Duvar Publishing, 2022, p. 55.
11. [11] N. S. Gunay-Sezer, E. Cakmak, and S. Bulkan, “A hybrid metaheuristic solution method to traveling salesman problem with drone,” Systems, vol. 11, no. 5, p. 259, 2023.
12. [12] D. Zhao, W. Xiong, and Z. Shu, “Simulated annealing with a hybrid local search for solving the traveling salesman problem,” J Comput Theor Nanosci, vol. 12, no. 7, pp. 1165–1169, 2015.
13. [13] F. Aydemir and S. Arslan, “A System Design With Deep Learning and IoT to Ensure Education Continuity for Post-COVID,” IEEE Transactions on Consumer Electronics, 2023.
14. [14] F. Aydemir and S. Arslan, “Covid-19 pandemi sürecinde çocukların el yıkama alışkanlığının nesnelerin interneti tabanlı sistem ile izlenmesi,” Mühendislik Bilimleri ve Araştırmaları Dergisi, vol. 3, no. 2, pp. 161–168, 2021.
15. [15] V. Kaya, “Classification of waste materials with a smart garbage system for sustainable development: a novel model,” Front Environ Sci, vol. 11, p. 1228732, 2023.
16. [16] C. Arslan and V. Kaya, “Classification of Plant Species from Microscopic Plant Cell Images Using Machine Learning Methods,” International Research Journal of Engineering and Technology (IRJET), vol. 11, no. 05, pp. 853–861, May 2024.
17. [17] G. Arslan, F. Aydemir, and S. Arslan, “Enhanced license plate recognition using deep learning and block-based approach,” Journal of Scientific Reports-A, no. 058, pp. 57–82, 2023.
18. [18] V. Kaya, “A perspective on transfer learning in computer vision,” 1st ed., vol. 1, Platanus, 2023, ch. 17, pp. 332–359.
19. [19] N. N. Arslan, E. Şahin, and M. Akçay, “Deep learning-based isolated sign language recognition: a novel approach to tackling communication barriers for individuals with hearing impairments,” Journal of Scientific Reports-A, no. 055, pp. 50–59, 2023.
20. [20] E. Şahin, D. Özdemir, and H. Temurtaş, “Multi-objective optimization of ViT architecture for efficient brain tumor classification,” Biomed Signal Process Control, vol. 91, p. 105938, 2024.
21. [21] I. Khan and M. K. Maiti, “A swap sequence based artificial bee colony algorithm for traveling salesman problem,” Swarm Evol Comput, vol. 44, pp. 428–438, 2019.
22. [22] V. Tongur and E. Ülker, “The analysis of migrating birds optimization algorithm with neighborhood operator on traveling salesman problem,” in Intelligent and Evolutionary Systems: The 19th Asia Pacific Symposium, IES 2015, Bangkok, Thailand, November 2015, Proceedings, Springer, 2016, pp. 227–237.
23. [23] C. Voudouris and E. Tsang, “Guided local search and its application to the traveling salesman problem,” Eur J Oper Res, vol. 113, no. 2, pp. 469–499, 1999.
24. [24] L. Gouveia, A. Paias, and M. Ponte, “The travelling salesman problem with positional consistency constraints: An Application to healthcare services,” Eur J Oper Res, vol. 308, no. 3, pp. 960–989, 2023.
25. [25] M. Mosayebi, M. Sodhi, and T. A. Wettergren, “The traveling salesman problem with job-times (tspj),” Comput Oper Res, vol. 129, p. 105226, 2021.
26. [26] Y. Shi and Y. Zhang, “The neural network methods for solving Traveling Salesman Problem,” Procedia Comput Sci, vol. 199, pp. 681–686, 2022.
27. [27] J. Gu and X. Huang, “Efficient local search with search space smoothing: A case study of the traveling salesman problem (TSP),” IEEE Trans Syst Man Cybern, vol. 24, no. 5, pp. 728–735, 1994.
28. [28] K. Panwar and K. Deep, “Discrete Grey Wolf Optimizer for symmetric travelling salesman problem,” Appl Soft Comput, vol. 105, p. 107298, 2021.
29. [29] G. Lancia and M. Dalpasso, “Finding the best 3-OPT move in subcubic time,” Algorithms, vol. 13, no. 11, p. 306, 2020.
30. [30] J. Schmidt and S. Irnich, “New neighborhoods and an iterated local search algorithm for the generalized traveling salesman problem,” EURO Journal on Computational Optimization, vol. 10, p. 100029, 2022.
31. [31] S. Gao, Y. Yu, Y. Wang, J. Wang, J. Cheng, and M. Zhou, “Chaotic local search-based differential evolution algorithms for optimization,” IEEE Trans Syst Man Cybern Syst, vol. 51, no. 6, pp. 3954–3967, 2019.
32. [32] A. Aly, G. Guadagni, and J. B. Dugan, “Derivative-free optimization of neural networks using local search,” in 2019 IEEE 10th Annual Ubiquitous Computing, Electronics & Mobile Communication Conference (UEMCON), IEEE, 2019, pp. 293–299.
33. [33] Y. Dumas, J. Desrosiers, E. Gelinas, and M. M. Solomon, “An optimal algorithm for the traveling salesman problem with time windows,” Oper Res, vol. 43, no. 2, pp. 367–371, 1995.
34. [34] J. Gu and X. Huang, “Efficient local search with search space smoothing: A case study of the traveling salesman problem (TSP),” IEEE Trans Syst Man Cybern, vol. 24, no. 5, pp. 728–735, 1994.
35. [35] L. Sengupta, R. Mariescu-Istodor, and P. Fränti, “Which local search operator works best for the open-loop TSP?,” Applied Sciences, vol. 9, no. 19, p. 3985, 2019.
36. [36] P. Singamsetty, J. Thenepalle, and B. Uruturu, “Solving open travelling salesman subset-tour problem through a hybrid genetic algorithm,” Journal of Project Management, vol. 6, no. 4, pp. 209–222, 2021.
37. [37] R. Hossain, S. Magierowski, and G. G. Messier, “GPU enhanced path finding for an unmanned aerial vehicle,” in 2014 IEEE International Parallel & Distributed Processing Symposium Workshops, IEEE, 2014, pp. 1285–1293.
38. [38] Y. Harrath, A. F. Salman, A. Alqaddoumi, H. Hasan, and A. Radhi, “A novel hybrid approach for solving the multiple traveling salesmen problem,” Arab J Basic Appl Sci, vol. 26, no. 1, pp. 103–112, 2019.
39. [39] I. Mavroidis, I. Papaefstathiou, and D. Pnevmatikatos, “Hardware implementation of 2-opt local search algorithm for the traveling salesman problem,” in 18th IEEE/IFIP International Workshop on Rapid System Prototyping (RSP’07), IEEE, 2007, pp. 41–47.
40. [40] A. F. Tuani, E. Keedwell, and M. Collett, “Heterogenous adaptive ant colony optimization with 3-opt local search for the travelling salesman problem,” Appl Soft Comput, vol. 97, p. 106720, 2020.
41. [41] B. Cheng, H. Lu, Y. Huang, and K. Xu, “An improved particle swarm optimization algorithm based on Cauchy operator and 3-opt for TSP,” in 2016 17th International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT), IEEE, 2016, pp. 177–182.
42. [42] G. Reinelt, “Tsplib95,” Interdisziplinäres Zentrum für Wissenschaftliches Rechnen (IWR), Heidelberg, vol. 338, pp. 1–16, 1995.
43. [43] G. Reinelt, “TSPLIB—A traveling salesman problem library,” ORSA journal on computing, vol. 3, no. 4, pp. 376–384, 1991.
44. [44] D. Özdemir and S. Dörterler, “An adaptive search equation-based artificial bee colony algorithm fortransportation energy demand forecasting,” Turkish Journal of Electrical Engineering and Computer Sciences, vol. 30, no. 4, pp. 1251–1268, 2022.
45. [45] D. Özdemir, S. Dörterler, and D. Aydın, “A new modified artificial bee colony algorithm for energy demand forecasting problem,” Neural Comput Appl, vol. 34, no. 20, pp. 17455–17471, 2022.
46. [46] O. Çıtlak, M. Dörterler, and İ. Dogru, “A hybrid spam detection framework for social networks,” Politeknik Dergisi, vol. 26, no. 2, pp. 823–837, 2022.
47. [47] N. M. Razali and J. Geraghty, “Genetic algorithm performance with different selection strategies in solving TSP,” in Proceedings of the world congress on engineering, International Association of Engineers Hong Kong, China, 2011, pp. 1–6.
48. [48] J. Yang, X. Shi, M. Marchese, and Y. Liang, “An ant colony optimization method for generalized TSP problem,” Progress in natural science, vol. 18, no. 11, pp. 1417–1422, 2008.
49. [49] L. Li, Y. Cheng, L. Tan, and B. Niu, “A discrete artificial bee colony algorithm for TSP problem,” in Bio-Inspired Computing and Applications: 7th International Conference on Intelligent Computing, ICIC 2011, Zhengzhou, China, August 11-14. 2011, Revised Selected Papers 7, Springer, 2012, pp. 566–573.
50. [50] S. P. Tiwari, S. Kumar, and K. K. Bansal, “A survey of metaheuristic algorithms for travelling salesman problem,” International Journal Of Engineering Research & Management Technology, vol. 1, no. 5, 2014.
51. [51] I. Kaabachi, D. Jriji, and S. Krichen, “A DSS based on hybrid ant colony optimization algorithm for the TSP,” in Artificial Intelligence and Soft Computing: 16th International Conference, ICAISC 2017, Zakopane, Poland, June 11-15, 2017, Proceedings, Part II 16, Springer, 2017, pp. 645–654.
52. [52] V. Kelner, F. Capitanescu, O. Léonard, and L. Wehenkel, “A hybrid optimization technique coupling an evolutionary and a local search algorithm,” J Comput Appl Math, vol. 215, no. 2, pp. 448–456, 2008.
53. [53] A. Sharifi, J. K. Kordestani, M. Mahdaviani, and M. R. Meybodi, “A novel hybrid adaptive collaborative approach based on particle swarm optimization and local search for dynamic optimization problems,” Appl Soft Comput, vol. 32, pp. 432–448, 2015.
54. [54] G. D’Angelo and F. Palmieri, “GGA: A modified genetic algorithm with gradient-based local search for solving constrained optimization problems,” Inf Sci (N Y), vol. 547, pp. 136–162, 2021.
55. [55] M. G. C. Resende and C. C. Ribeiro, “Greedy randomized adaptive search procedures: Advances, hybridizations, and applications,” Handbook of metaheuristics, pp. 283–319, 2010.