TSSIA: Türkiye'deki Gezgin Satıcı Problemi için Yeni Bir Tabu Arama Segment İyileştirme Algoritması

Abstract

Gezgin satıcı probleminde, bir satıcının bir şehirden başlayarak her şehirden sadece bir kez geçilmesi ve aynı şehre geri dönmesi amaçlanır. Fakat, bu problem, toplamda en kısa rotanın bulunmasıyla çözülür. Şehir sayısı fazla olduğunda çözülmesi çok zor ve zaman alan problemlerdendir. Bu yüzden, genelde meta sezgisel metotlarla çözülmeye çalışılır. Bu çalışmada, Türkiye’nin şehirlerinin mesafeleri kullanılarak Karınca Kolonisi, Yapay Arı Kolonisi ve Tabu Arama algoritmaları ile gezgin satıcı problemi çözülmeye çalışılmıştır. Her metot için en kısa rotalar bulunmuş ve bu metotlar karşılaştırılmıştır. Bu çalışma sonucunda en başarılı metot Tabu Arama algoritması olduğu görülmüştür. Bunula birlikte, Tabu Arama algoritmasına segment iyileştirme eklenmesi suretiyle bilinen en iyi rota tespit edilmiştir. Türkiye şehirleriyle oluşturulan gezgin satıcı probleminin şimdiye kadarki en iyi rotası 9966 km iken bu çalışmada önerilen Tabu Arama Segment İyileştirme algoritmasıyla 60 km azaltılarak 9906 km ye kadar düşürülmüştür.

Keywords

• Gezgin Satıcı Problemi
• Tabu Arama Algoritması
• Karınca Kolonisi Algoritması
• Yapay Arı Kolonisi Algoritması
• Türkiye şehirleri

TSSIA: A Novel Tabu Search Segment Improvement Algorithm for the Traveling Salesman Problem in Türkiye

Abstract

In the traveling salesman problem, the aim is for a salesperson to start from one province, pass through each province only once, and come back to the same province. However, this problem can be reached by discovering the shortest possible route in total. When the number of provinces is large, it is a very difficult and time-consuming problem to solve. Therefore, it is generally attempted to be solved with metaheuristic methods. In this work, the traveling salesman problem was attempted to be solved using the distances between the provinces of Türkiye with Ant Colony, Artificial Bee Colony, and Tabu Search algorithms. The shortest routes were found for each method, and these methods have been compared with each other. As a result, it was seen that the most successful method was the Tabu Search algorithm. In addition, the best-known route has been determined by adding segment improvement to the Tabu Search algorithm. While the best-known route for the Traveling Salesman Problem involving Turkish cities was previously 9,966 km, it has been reduced to 9,906 km using the Tabu Search Segment Improvement algorithm proposed in this study, achieving a reduction of 60 km.

Keywords

• Traveling Salesman Problem
• Tabu Search Algorithm
• Ant Colony Algorithm
• Artificial Bee Colony Algorithm
• Turkish provinces

References

1. [1] Goyal, S. 2010. A survey on travelling salesman problem. 43rd Midwest Instruction and Computing Symposium, Eau Claire, Wisconsin, USA, 16-17.
2. [2] Aşlıyan, R. 2022. Traveling Salesman Problem Solution with Ant Colony Optimization and Simulated Annealing: A Case Study for Turkish Provinces, 2nd International Symposium of Scientific Research and Innovative Studies (ISSRIS’22), 2-5 March, 1-10, 583-592.
3. [3] Matai, R., Singh, S., Mittal, M.L. 2010. Traveling Salesman Problem: an Overview of Applications, Formulations and Solution Approaches. Editor: Davendra D. Traveling salesman problem, theory and applications, Landon, United Kingdom, InTech, 1-24.
4. [4] Aşlıyan, R. 2021. Comparison of Traveling Salesman Problem with Metaheuristic Algorithms for Turkish Provinces. International Congress on Scientific Advances (ICONSAD'21), 22-25 December, Türkiye, 660-668.
5. [5] Dikmen, H., Dikmen, H., Elbir, A., Ekşi, Z. 2014. Gezgin Satıcı Probleminin Karınca Kolonisi ve Genetik Algoritmalarla Eniyilemesi ve Karşılaştırılması. Süleyman Demirel Üniversitesi Fen Bilimleri Enstitüsü Dergisi, 18(1), 8-13.
6. [6] Glover, F., Laguna, M. 1997. Tabu Search. Kluwer Academic Publishers.
7. [7] Gendreau, M., Potvin, J. Y. (Eds.). 2010. Handbook of Metaheuristics. Second edition. Springer.
8. [8] Dantzig, G. B., Fulkerson, D. R., Johnson, S. M. 1954. Solution of a large-scale traveling-salesman problem. Operations Research, 2(4), 393-410.

9. [9] Miller, C. E., Tucker, A. W., Zemlin, R. A. 1960. Integer Programming Formulation of Traveling Salesman Problems. Journal of the ACM, 7(4), 326-329.
10. [10] Lawler, E. L., Lenstra, J. K., Rinnooy Kan, A. H. G., Shmoys, D. B. (Eds.) 1985. The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. John Wiley & Sons.
11. [11] Padberg, M., Sung, T. Y. 1991. An analytical comparison of different formulations of the traveling salesman problem. Mathematical Programming, 52(1-3), 315-357.
12. [12] Köse, O., Erdoğmuş, P. 2019. K-Gezgin Satıcı Probleminin Emperyalist Rekabetçi Algoritması ile Kümeleme Tabanlı Optimizasyonu. Bartın Üniversitesi Mühendislik ve Teknoloji Bilimleri Dergisi, 7(1), 1-13.
13. [13] Şenaras, E. A., İnanç, Ş. 2017. GSP Çözümü için Karınca Kolonisi Optimizasyonu. Sosyal Bilimler Metinleri, 58-67.
14. [14] Ertuğrul, İ., Özçil, A. 2016. Siyasi parti mitinglerinin gezgin satıcı problemi yaklaşımı ile analizi. Siyaset, Ekonomi ve Yönetim Araştırmaları Dergisi, 4(4), 223-238.
15. [15] Hasan, D. O., Aladdin, A. M. 2025. Real-World Applications of Metaheuristic Algorithms: A Comprehensive Review of the State-of-the-Art. Diyala Journal of Engineering Sciences, 1-27.
16. [16] Almufti, S. M. 2025. Metaheuristics Algorithms: Overview, Applications, and Modifications.
17. [17] Rashid, N. S., Zebari, I. M. I. 2025. A comprehensive review of metaheuristic algorithms for combinatorial optimization problems. International Journal of Scientific World, 11(1), 83-92.
18. [18] Pop, P. C., Cosma, O., Sabo, C., Pop Sitar, C. 2024. A comprehensive survey on the generalized traveling salesman problem. European Journal of Operational Research, 314(3), 819-835.
19. [19] Soni, V., Sharma, A., Singh, V. 2021. A Critical Review on Nature Inspired Optimization Algorithms. 1099(1), 012055.
20. [20] Liu, Y., Chen, X., Dib, O. 2023. Application of Metaheuristic Algorithms and Their Combinations to Travelling Salesman Problem. Springer International Publishing, 3-18.
21. [21] Jiang, C., Wan, Z., Peng, Z. 2020. A new efficient hybrid algorithm for large scale multiple traveling salesman problems. Expert Systems with Applications, 139, 112867.
22. [22] Yahia, W. B., Al-Neama, M. W., Arif, G. E. 2020. A hybrid optimization algorithm of ant colony search and neighbour-joining method to solve the travelling salesman problem. Advanced Mathematical Models & Applications, 5(1).
23. [23] Qamar, M. S., Tu, S., Ali, F., Armghan, A., Munir, M. F., Alenezi, F., Alnaim, N. 2021. Improvement of traveling salesman problem solution using hybrid algorithm based on best-worst ant system and particle swarm optimization. Applied Sciences, 11(11), 4780.
24. [24] Kanna, S. R., Sivakumar, K., Lingaraj, N. 2021. Development of deer hunting linked earthworm optimization algorithm for solving large scale traveling salesman problem. Knowledge-Based Systems, 227, 107199.
25. [25] Sarucan, A., Berkaya, M. F. 2024. Combining 3‐Opt and Improved Discrete Cuckoo Search Algorithm for the Traveling Salesman Problem. Discrete Dynamics in Nature and Society, 2024(1).
26. [26] Bai, Z., Snášel, V., Vo, B., Kong, L., Wang, X. 2024. A Hybrid Algorithm ACS-GA for Solving the Traveling Salesman Problem. Springer Science+Business Media, 71-82.
27. [27] Yang, L., Wang, X., He, Z., Wang, S. Lin, J. 2024. Review of Traveling Salesman Problem Solution Methods. Communications in computer and information science, 3-16.
28. [28] Murali Krishna, M., Panda, N., Majhi, S. K. 2021. Solving traveling salesman problem using hybridization of rider optimization and spotted hyena optimization algorithm. Expert Systems With Applications, 183, 115353.
29. [29] Thongpiem, J., Punkong, N., Ratanavilisagul C., Kosolsombat, S. 2024. Hybrid Genetic Algorithm and Ant Colony Algorithm for Solving Travelling Salesman Problem. IEEE 9th International Conference on Computational Intelligence and Applications (ICCIA), Haikou, China, 2024, 69-73.
30. [30] Kothari, A., Nikhil, V. R. N. S., Rohit, N., Sahay, A. 2024. Harnessing Meta-Heuristic Algorithms to Optimize Travelling Salesman Problem. 15th International Conference on Computing Communication and Networking Technologies (ICCCNT), Kamand, India, 1-9.
31. [31] Abid, M., El Kafhali, S., Amzil, A., Hanini, M. 2023. An Efficient Meta-Heuristic Methods for Travelling Salesman Problem. In: Hassanien, A.E., et al. The 3rd International Conference on Artificial Intelligence and Computer Vision (AICV2023), Lecture Notes on Data Engineering and Communications Technologies, Springer, vol. 164.
32. [32] Glover, F. 1986. Future Paths for Integer Programming and Links to Artificial Intelligence. Computers & Operations Research, 13(5), 533-549.
33. [33] Glover, F. 1989. Tabu Search-Part I. ORSA Journal on Computing, 1(3), 190-206.
34. [34] Glover, F. 1990. Tabu Search-Part II. ORSA Journal on Computing, 2(1), 4-32.
35. [35] Malek, M., Guruswamy, M., Pandya, M., Owens, H. 1989. Serial and parallel simulated annealing and tabu search algorithms for the traveling salesman problem. Annals of Operations Research, 21(1), 59-84.
36. [36] Wu, Y., Zhou, X. 2008. Meliorative Tabu Search Algorithm for TSP Problem. Journal of Computer Engineering and Applications, 44(1), 57-59.
37. [37] Gendreau, M., Laporte, G., Semet, F. 1998. A tabu search heuristic for the undirected selective travelling salesman problem. European Journal of Operational Research, 106(2-3), 539-545.
38. [38] 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.
39. [39] Dorigo, M., Maniezzo, V., Colorni, A. 1996. Ant System: Optimization by a colony of cooperating agents. IEEE Trans Syst, Man Cybernet Part B, 26(1), 29-41.
40. [40] Dorigo, M., Stützle, T. 2004. Ant Colony optimization. Cambridge, MA, MIT Press, 305s.
41. [41] 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.
42. [42] Shang, G. 2005. The chaotic ant colony algorithm to solve TSP problem. Journal of Systems Engineering-theory & Practice, 9,100.
43. [43] Akça, M. R. 2011. Yapay arı koloni algoritması kullanılarak gezgin satıcı probleminin Türkiye’deki il ve ilçe merkezlerine uygulanması. Master thesis, Institute of Natural and Applied Science, Konya, Turkey.
44. [44] Karaboğa, D. 2005. An idea based on honey bee swarm for numerical optimization. Technical Report TR06, Erciyes University, Engineering Faculty, Computer Engineering Department.
45. [45] Karaboğa D., Baştürk, B. 2007. A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm. J. Global. Optim, 39, 459-471.
46. [46] Karaboğa, D., Baştürk Akay, B., Öztürk, C. 2007. Artificial Bee Colony (ABC) Optimization Algorithm for Training Feed-Forward Neural Networks. In: LNCS: Modeling Decisions for Artificial Intelligence, Springer-Verlag, Berlin Heidelberg 4617/2007, 318-319.
47. [47] Kalınlı, A., Karaboğa, N., Karaboğa D. 2001. A Modified Touring Ant Colony Optimization Algorithm for Contounous Functions. 16th International Symposium on Computer and Informatıon Science (ISCIS XVI), Işık University, Antalya, 437-44.
48. [48] Türkiye Karayolları Genel Müdürlüğü. https://www.kgm.gov.tr/Sayfalar/KGM/SiteTr/Root/Uzakliklar.aspx (Erişim Tarihi: 20.06.2025).
49. [49] Cografya Harita. http://cografyaharita.com. (Acces Date: 17.06.2025).