Ant Colony Optimization for a 50 City Traveling Salesman Problem
A Parameterized Benchmark Study with Convergence Analysis
DOI:
https://doi.org/10.61704/pr.524الكلمات المفتاحية:
Traveling Salesman Problem; ant colony optimization; metaheuristics; swarm intelligence; benchmarking; convergence analysisالملخص
This paper evaluates Ant Colony Optimization (ACO) on a mid-scale Traveling Salesman Problem (TSP) with 50 cities. We present a complete problem formulation, a parameterized algorithmic design, and a compact experimental protocol that emphasizes interpretability via full methodological detail and a fully specified coordinate set. Two figures visualize the best route and the best-so-far convergence trajectory. With a standard ACO configuration (α=1, β=5, ρ=0.5), the best tour length is 566.75 distance units, an 18.4% improvement over a Nearest-Neighbor baseline (694.76). We analyze convergence behavior, sensitivity to key parameters, computational cost, and practical implications for early-stopping and reproducible benchmarking. The study positions these results within the TSP/ACO literature and offers concise recommendations for fair, mid-scale comparisons.
المراجع
Applegate, D., Bixby, R., Chvátal, V., & Cook, W. (2003). Implementing the Dantzig–Fulkerson–Johnson algorithm for large traveling salesman problems. Mathematical Programming, 97(1), 91–153. https://doi.org/10.1007/s10107-003-0440-4
Applegate, D. L., Bixby, R. E., Chvátal, V., & Cook, W. J. (2006). The traveling salesman problem: A computational study. Princeton University Press. http://www.jstor.org/stable/j.ctt7s8xg
Birattari, M. (2009). Tuning metaheuristics: A machine learning perspective. Springer. https://doi.org/10.1007/978-3-642-00483-4
Blum, C. (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
Croes, G. A. (1958). A method for solving traveling-salesman problems. Operations Research, 6(6), 791–812. http://www.jstor.org/stable/167074
Dorigo, M., Birattari, M., & Stützle, T. (2006). Ant colony optimization: Artificial ants as a computational intelligence technique. IEEE Computational Intelligence Magazine, 1(4), 28–39. https://doi.org/10.1109/MCI.2006.329691
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. https://doi.org/10.1109/4235.585892
Dorigo, M., Maniezzo, V., & Colorni, A. (1996). Ant system: Optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics – Part B: Cybernetics, 26(1), 29–41. https://doi.org/10.1109/3477.484436
Dorigo, M., & Stützle, T. (2004). Ant colony optimization. MIT Press. https://doi.org/10.7551/mitpress/1290.001.0001
Johnson, D. S., & McGeoch, L. A. (1997). The traveling salesman problem: A case study. In E. H. L. Aarts & J. K. Lenstra (Eds.), Local search in combinatorial optimization (pp. 215–310). John Wiley & Sons.
Liao, T., Socha, K., Montes de Oca, M. A., Stützle, T., & Dorigo, M. (2014). Ant colony optimization for mixed-variable optimization problems. IEEE Transactions on Evolutionary Computation, 18(4), 503–518. https://doi.org/10.1109/TEVC.2013.2281531
Lin, S. (1965). Computer solutions of the traveling salesman problem. The Bell System Technical Journal, 44(10), 2245–2269. https://doi.org/10.1002/j.1538-7305.1965.tb04146.x
Lin, S., & Kernighan, B. W. (1973). An effective heuristic algorithm for the traveling-salesman problem. Operations Research, 21(2), 498–516. https://doi.org/10.1287/opre.21.2.498
López-Ibáñez, J., Dubois-Lacoste, J., Cáceres, P., Birattari, M., & Stützle, T. (2016). The irace package: Iterated racing for automatic algorithm configuration. Operations Research Perspectives, 3, 43–58. https://doi.org/10.1016/j.orp.2016.09.002
Papadimitriou, C. H., & Steiglitz, K. (1998). Combinatorial optimization: Algorithms and complexity. Courier Corporation.
Reinelt, G. (1991). TSPLIB—A traveling salesman problem library. ORSA Journal on Computing, 3(4), 376–384. https://doi.org/10.1287/ijoc.3.4.376
Socha, K., & Dorigo, M. (2008). Ant colony optimization for continuous domains. European Journal of Operational Research, 185(3), 1155–1173. https://doi.org/10.1016/j.ejor.2006.06.046
Stützle, T., & Hoos, H. H. (2000). MAX–MIN ant system. Future Generation Computer Systems, 16(8), 889–914. https://doi.org/10.1016/S0167-739X(00)00043-1
التنزيلات
منشور
كيفية الاقتباس
إصدار
القسم
الرخصة
الحقوق الفكرية (c) 2025 Ali A. Al-Arbo, Younis A. Al-Arbo
هذا العمل مرخص بموجب Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
Copyright © 2025 by the authors. This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License (CC BY-NC-ND 4.0). You may not alter or transform this work in any way without permission from the authors. Non-commercial use, distribution, and copying are permitted, provided that appropriate credit is given to the authors and Al-Hadba University.
