ANT COLONY OPTIMIZATION FOR SOLVING TSP WITH SUB-ROUTE ELIMINATION CONSTRAINTS ON TÜRKIYE MAP

Year 2025, Volume: 15 Issue: 12, 2750 - 2759, 06.12.2025

Fidan Nuriyeva Veysel Erdemci

Abstract

The Traveling Salesman Problem is the famous optimization problem in the NP-hard class. Many problems with applications in computer science and engineering can be modeled using the Traveling Salesman Problem. In this study, one of the artificial intelligence techniques, ant colony method, is used to solve the traveling salesman problem. In the study applied on the map of Türkiye, it is aimed to plan the best route.

Keywords

Symmetric Traveling Salesman Problem , Artificial Intelligence , Ant Colony Algorithm , Metaheuristics , Sub-Route Elimination Constraint

References

• Appligate, D. L., Bixby, R. E., Chavatal, V., Cook, W. J., (2006), The Traveling Salesman Problem, A Computational Study, Princeton University Press.
• Bonabeau, E., Dorigo, M., Theraulaz, G., (1999), Swarm Intelligence: From Natural to Artificial Systems, Oxford University Press.
• Bullnheimer, B., Hartl, R. F., Strauss, C., (1999), A new rank-based version of the ant system - computational study, Central European Journal of Operations Research, 7(1), pp. 25-38.
• Davendra, D., (2010), Travelling Salesman Problem, Theory and Applications, IntechOpen.
• Dikmen, H., Dikmen, H., Elbir, A., Ekşi, Z., Çelik, F., (2014), Gezgin satıcı probleminin karınca kolonisi ve genetik algoritmalarla eniyilemesi ve karşılaştırılması, (Optimization and comparison of Travelling Salesman Problem using ant colony and genetic algorithms), Suleyman Demirel University Journal of Natural and Applied Science, 18(1), pp. 8-13.
• Dorigo, M., Maniezzo, V., Colorni, A., (1991), Ant System: An Autocatalytic Optimizing Process, Technical Report 91-016.
• 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), pp. 53-66.
• Dorigo, M., Maniezzo, V., Colorni, A., (1996), The ant system: Optimization by a colony of cooperating agents, IEEE Transactions on Systems, Man, and Cybernetics, Part B, 26(1), pp. 1-13.
• Garey, M. R., Johnson, D. S., (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Company.
• Gutin, G., Punnen, A., (2002), The Traveling Salesman Problem and Its Variations, Kluwer Academic Publishers.
• Johnson, D., Papadimitriou, C., (1985a), Computational Complexity, In Lawler et al., Chapter 3, pp. 37-86.
• Johnson, D., Papadimitriou, C., (1985b), Performance Guarantees for Heuristics, In Lawler et al., Chapter 5, pp. 145-180.
• Johnson, D. S., McGeoch, L. A., (1995), The Traveling Salesman Problem: A Case Study in Local Search in Combinatorial Optimization, pp. 215-310, John Wiley \& Sons.
• Kızılateş, G., Nuriyeva, F., (2013), On the nearest neighbor algorithms for the traveling salesman problem, Advances in Computational Science, Engineering and Information Technology, Advances in Intelligent Systems and Computing, 225, Springer, Heidelberg.
• Lawler, E. L., Lenstra, J. K., Rinnoy Kan, A. H. G., Shmoys, D. B., (1991), The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, Wiley Series in Discrete Mathematics \& Optimization.
• Manfrin, M., Birattari, M., Stützle, T., Dorigo, M., (2006), Parallel Ant Colony Optimization for the Traveling Salesman Problem, In: Dorigo, M., Gambardella, L.M., Birattari, M., Martinoli, A., Poli, R., Stützle, T. (eds) Ant Colony Optimization and Swarm Intelligence. ANTS 2006. Lecture Notes in Computer Science, 4150, Springer, Berlin, Heidelberg.
• Miller, C. E., Tucker, A. W., Zemlin, R. A., (1960), Integer programming formulations and Traveling Salesman Problems, Journal of the ACM, 7(4), pp. 326–329.
• Mohsen, A. M., (2016), Annealing ant colony optimization with mutation operator for solving TSP, Computational Intelligence and Neuroscience, 2016, pp. 1-13.
• Nuriyev, U., Nuriyeva, F., (2018), Practical aspects of solving combinatorial optimization problems, Advanced Mathematical Models and Applications, 3(3), pp. 179--191.
• Rosenkrantz, D. J., Stearns, R. E., Lewis, P. M., (1977), An analysis of several heuristics for the Travelling Salesman Problem, SIAM Journal of Computing, 6, pp. 563-581.
• Shang, Y., Gong, H., Zeng, Q., (2007), Enhancing ant colony optimization algorithm for solving large traveling salesman problem, Applied Mathematics and Computation, 184(2), pp. 422-431.
• Siemiński, A., (2016), Using hyper populated ant colonies for solving the TSP, Vietnam J Comput Sci, 3, pp. 103–117.
• Söyler, H., Keskintürk, T., (2007), Karınca kolonisi algoritması ile Gezen Satıcı Probleminin çözümü, (Solution of the Traveling Salesman Problem with ant colony algorithm), 8th Turkish Conference on Econometrics and Statistics, Malatya, Turkey, pp. 1-11.
• Skinderowicz, R., (2022), Improving ant colony optimization efficiency for solving large TSP instances, Applied Soft Computing, 120, pp. 108653.
• Stützle, T., Hoos, H. H., (2000), MAX–MIN ant system, Future Generation Computer Systems, 16(8), pp. 889-914.
• Şenaras, E. A., İnanç, Ş., (2017), GSP çözümü için karınca kolonisi optimizasyonu, (Ant colony optimization for solving Vehicle Routing Problems), Papers on Social Science, 2017(2), pp. 58-67.
• Zarei, H., YousefiKhoshbakht, M., Khorram, E., (2016), A hybrid modified meta-heuristic algorithm for solving the traveling salesman problem, Journal of Industrial and Systems Engineering, 9(3), pp. 57-69.
• Zhang, X., Bai, Q., Yun, X., (2011), A new hybrid artificial bee colony algorithm for the traveling salesman problem, 2011 IEEE 3rd International Conference on Communication Software and Networks, Xi'an, China, pp. 155-159, doi: 10.1109/ICCSN.2011.6014240.
• Zheng, Z., Liu, S., Zhou, X., (2023), Optimization of Logistics Distribution Route Based on Ant Colony Algorithm – Taking Nantian Logistics as an Example, In: Hu, Z., Zhang, Q., He, M. (eds) Advances in Artificial Systems for Logistics Engineering III. ICAILE 2023. Lecture Notes on Data Engineering and Communications Technologies, vol 180, Springer, Cham.