Benchmarking Ant Colony Optimization and Simulated Annealing on Nigerian Travelling Salesman Problem Instances

The Travelling Salesman Problem (TSP) is a canonical combinatorial optimisation problem central to transportation planning, logistics, and regional network design. This study compares two widely used metaheuristics, Ant Colony Optimisation (ACO) and Simulated Annealing (SA), on a geographically grounded TSP instance built from road-network distances among the 23 Local Government Area (LGA) headquarters of Rivers State, Nigeria. A verified 23 × 23 Haversine distance matrix, derived from GPS-referenced coordinates, formed the dataset. Both algorithms were coded in Python and executed under identical conditions across 30 independent trials, with performance assessed on solution quality, computational efficiency, convergence, stability, and robustness. ACO produced shorter optimal routes (best distance: 1,247.3 km vs 1,316.8 km for SA) with lower variance (SD = 31.7 vs 52.3 km), while SA ran considerably faster (4.2 s vs 18.4 s). A paired-samples t-test confirmed that ACO's quality advantage is statistically significant and large in magnitude (t = −13.63, df = 29, p < 0.0001, d = 2.49). The findings provide empirically grounded guidance for metaheuristic selection in regional transportation optimisation within developing-economy contexts.

Travelling Salesman Problem; Ant Colony Optimisation; Simulated Annealing; metaheuristics

1. K., Menger, “ Das botenproblem. Ergebnisse eines Mathematischen Kolloquiums”, 2, 11–12, 1932. [Google Scholar] [Crossref]

2. M. R.,Garey, & D. S., Johnson (1979). Computers and intractability: A guide to the theory of NP-completeness. W. H. Freeman. [Google Scholar] [Crossref]

3. G., Gutin & A. P., Punnen (2002). The Traveling Salesman Problem and Its Variations, Springer. Combinatorial Optimization, 12, 84-85. [Google Scholar] [Crossref]

4. D. L., Applegate, R. E. ,Bixby, V., Chvátal, & W. J.,Cook (2006). The travelling salesman problem: A computational study. Princeton University Press. [Google Scholar] [Crossref]

5. P., Toth, & D.,Vigo(Eds.). (2014). Vehicle routing: Problems, methods, and applications (2nd ed.). SIAM. [Google Scholar] [Crossref]

6. S., Lin & B. W., Kernighan (1973). An effective heuristic algorithm for the travelling-salesman problem. Operations Research, 21(2), 498–516. DOI: 10.1287/opre.21.2.498. [Google Scholar] [Crossref]

7. K., Helsgaun (2000). An effective implementation of the Lin–Kernighan traveling salesman heuristic. European Journal of Operational Research, 126(1), 106–130. DOI: 10.1016/S0377-2217(99)00284-2. [Google Scholar] [Crossref]

8. L., Wang, J., Cai & M., Li (2020). An adaptive multi-population genetic algorithm for the travelling salesman problem. Information Sciences, 512, 1051–1064. https://doi.org/10.1016/j.ins.2019.10.046 [Google Scholar] [Crossref]

9. Z., Xu, Q., Chen, & S., Lin (2022). Hybrid ACO-SA algorithm with pheromone redistribution for real-world multi-city routing. Swarm and Evolutionary Computation, 68, 101001. https://doi.org/10.1016/j.swevo.2021.101001 [Google Scholar] [Crossref]

10. H., Tan, Y., Wu, J., Zhang, & J., Zhang (2023). Study on a hybrid algorithm combining enhanced ant colony optimization and double improved simulated annealing via clustering in the travelling salesman problem. PeerJ Computer Science, 9, e1609. https://doi.org/10.7717/peerj-cs.1609 [Google Scholar] [Crossref]

11. B., Zheng & H., Du (2023). Real-world TSP benchmarking using geographic road network data: A systematic review. Computers & Operations Research, 150, 106078. https://doi.org/10.1016/j.cor.2022.106078 [Google Scholar] [Crossref]

12. Egba, A.F. & Okonkwo, R.O. (2026). Benchmarking ant colony optimization and simulated annealing on Nigerian Travelling Salesman problem instances, International Journal of Research and Innovation in Applied Sciences (IJRIAS), Vol. XI, Issue VIII, pp. [page numbers]. [Google Scholar] [Crossref]

13. M., Dorigo, V., Maniezzo, & A., Colorni (1996). Ant system: optimisation by a colony of cooperating agents. IEEE transactions on systems, man, and cybernetics, part b (cybernetics), 26(1), 29-41. [Google Scholar] [Crossref]

14. M., Dorigo & L.M., Gambardella (2002). Ant colony system: a cooperative learning approach to the travelling salesman problem. IEEE Transactions on Evolutionary Computation, 1(1), 53-66. [Google Scholar] [Crossref]

15. T., Stützle & H.H., Hoos (2000). MAX–MIN ant system. Future Generation Computer Systems, 16(8), 889–914. https://doi.org/10.1016/S0167-739X(00)00043-1 [Google Scholar] [Crossref]

16. C., Blum (2005). Ant colony optimization: Introduction and recent trends. Physics of Life Reviews, 2(4), 353–373. https://doi.org/10.1016/j.plrev.2005.10.001 [Google Scholar] [Crossref]

17. X., Pan, Y., Zhao & K., Tang (2021). Enhanced ant colony optimization with adaptive parameter control for large-scale TSP. Expert Systems with Applications, 176, 114856. https://doi.org/10.1016/j.eswa.2021.114856 [Google Scholar] [Crossref]

18. A. S. B., Shahadat, M. A. H., Akhand & M. A. S., Kamal (2022). Visibility adaptation in ant colony optimization for solving traveling salesman problem. Mathematics, 10(14), 2448. https://doi.org/10.3390/math10142448 [Google Scholar] [Crossref]

19. K., Tang, X.-F., Wei, Y.-H., Jiang, Z.-W., Chen & L., Yang (2023). An adaptive ant colony optimization for solving large-scale traveling salesman problem. Mathematics, 11(21), 4439. https://doi.org/10.3390/math11214439 [Google Scholar] [Crossref]

20. Y.,He, X., Liu, & J., Zhang (2021). A novel hybrid ant colony optimization algorithm for the travelling salesman problem. Applied Soft Computing, 104, 107178. https://doi.org/10.1016/j.asoc.2021.107178 [Google Scholar] [Crossref]

21. K. I., Rufai O.L., Usman, O.O., Olusanya and O.B., Adedeji (2021). Solving Travelling Salesman Problem using an Improved Ant Colony Optimization Algorithm. University of Ibadan Journal of Science and Logics in ICT Research (UIJSLICTR), Vol. 6 No. 2, pp. 158- 170 [Google Scholar] [Crossref]

22. S., Kirkpatrick, C. D., Gelatt, & M. P., Vecchi (1983). Optimization by simulated annealing. Science, 220(4598), 671–680. https://doi.org/10.1126/science.220.4598.671 [Google Scholar] [Crossref]

23. C., Voudouris & E. P. K., Tsang (1999). Guided local search and its application to the travelling salesman problem. European Journal of Operational Research, 113(2), 469–499. DOI: 10.1016/S0377-2217(98)00099-2. [Google Scholar] [Crossref]

24. J., Zhang & M., Sun (2022). Adaptive parameter tuning in simulated annealing for combinatorial optimization: A benchmarking study. Applied Soft Computing, 118, 108495. https://doi.org/10.1016/j.asoc.2022.108495 [Google Scholar] [Crossref]

25. B., Nguimeya Tsofack, G. B., Jagho Mdemaya, M. M., Zekeng Ndadji, M., Ndognkom Manga & M., Velempini (2026). A New Approach to Efficiently Solving the Traveling Salesman Problem (TSP) by Combining Artificial Intelligence Techniques and Ant Colony Metaheuristics. Algorithms, 19(7), 552. https://doi.org/10.3390/a19070552 [Google Scholar] [Crossref]

26. P., Stodola, K., Michenka, J., Nohel & M., Rybansky (2020). Hybrid algorithm based on ant colony optimization and simulated annealing applied to the dynamic traveling salesman problem. Entropy, 22(8), 884. https://doi.org/10.3390/e22080884 [Google Scholar] [Crossref]

27. Y., Jiang, X., Hu, & X., Liang (2022). Comparative analysis of metaheuristic algorithms for multi-city route optimization in developing urban networks. Engineering Applications of Artificial Intelligence, 110, 104718. https://doi.org/10.1016/j.engappai.2022.104718 [Google Scholar] [Crossref]

28. M., Mavrovouniotis, C., Li & S., Yang (2017). A survey of swarm intelligence for dynamic optimization: Algorithms and applications. Swarm and Evolutionary Computation, 33, 1–17. https://doi.org/10.1016/j.swevo.2016.12.005 [Google Scholar] [Crossref]

29. D. A. F., Anggraeni, V. R., Dianutami & R., Tyasnurita (2024). Investigation of simulated annealing and ant colony optimization to solve delivery routing problem in Surabaya, Indonesia. Procedia Computer Science, 234, 592-601. [Google Scholar] [Crossref]

• The Impact of Ownership Structure on Dividend Payout Policy of Listed Plantation Companies in Sri Lanka
• Urban Sustainability in North-East India: A Study through the lens of NER-SDG index
• Performance Assessment of Predictive Forecasting Techniques for Enhancing Hospital Supply Chain Efficiency in Healthcare Logistics
• The Fractured Self in Julian Barnes' Postmodern Fiction: Identity Crisis and Deflation in Metroland and the Sense of an Ending
• Impact of Flood on the Employment, Labour Productivity and Migration of Agricultural Labour in North Bihar