Book Details

MMCTS: AN ADAPTIVE HYBRID MMAS–MCTS FRAMEWORK FOR THE TRAVELING SALESMAN PROBLEM

International Journal of Computer Science (IJCS) Published by SK Research Group of Companies (SKRGC)

Download this PDF format

Download

Abstract

The traveling salesman problem (TSP) is an NP-hard problem with significant theoretical and practical implications. This paper presents a hybrid MMAS–MCTS algorithm for the Traveling Salesman Problem that incorporates an adaptive last-mile intensification mechanism to improve solution quality near convergence. The proposed framework integrates a stagnation-aware MCTS destroy-and-repair strategy with regret-based reconstruction and progressive widening to enhance exploration while preserving promising solution structures. As the search converges, adaptive 2-opt and lightweight 3-opt refinements are employed to strengthen exploitation and further improve solution quality. Experimental evaluations on TSPLIB benchmark instances demonstrate the effectiveness of MMAS–MCTS, which achieves optimal solutions for many instances and maintains very small optimality gaps on larger problems. Comparative analyses further show that the proposed approach consistently outperforms conventional MMAS and MMAS augmented with 2-opt/3-opt local search in terms of solution quality and robustness.

References

  1. Little, J.D., Murty, K.G., Sweeney, D.W., Karel, C.: An algorithm for the traveling salesman problem. Oper. Res. 11(6), 972–989 (1963)
  2. Gutin, G., & Punnen, A. P. (Eds.). (2006). The traveling salesman problem and its variations (Vol. 12). Springer Science & Business Media.
  3. Applegate, D.L., Bixby, R.E., Chvátal, V., Cook, W.J.: The Traveling Salesman Problem: A Computational Study. Princeton University Press, Princeton (2011)
  4. Y. Hu, Z. Zhang, Y. Yao, X. Huyan, X. Zhou and W.S. Lee, A bidirectional graph  neural            network         for traveling salesman problems on arbitrary symmetric graphs. Eng. App. Artif. Intell. 97 (2021) 104061.
  5. Cri?an, G. C., Pintea, C. M., & Palade, V. (2017). Emergency management using geographic information systems: application to the first romanian traveling salesman problem instance. Knowledge and Information Systems, 50(1), 265-285.
  6. J. Li, M. Liu and P. Liu, Route optimization of multi-vehicle cold chain logistics    for       fresh agricultural   products. J. China Agr. Univ. 26 (2021) 115.
  7. Lu, Z., Wu, K., Bai, E., & Li, Z. (2025). Optimization of multi-vehicle cold chain  logistics  distribution  paths  considering  traffic congestion. Symmetry, 17(1), 89.
  8. H. Katagiri, G. Qingqiang, W. Bin, T. Muranaka, H. Hamori and K. Kato, Path optimization            for       electrical        pcb inspections with alignment operations using multiple cameras. Proc. Comput. Sci. 60 (2015) 1051–1060.
  9. Al-Janan, D. H., & Liu, T. K. (2016). Path optimization of CNC PCB drilling using hybrid Taguchi genetic algorithm. Kybernetes, 45(1), 107-125.
  10. Monroe, J. G., Allen, Z. A., Tanger, P., Mullen, J. L., Lovell, J. T., Moyers, B. T., ... & McKay, J. K. (2017). TSPmap, a tool making use of traveling salesperson problem solvers in the efficient and accurate construction of high-density genetic linkage maps. BioData mining, 10(1), 38.
  11. Z. Liu, H. Lou, K. Xie, H. Wang, N. Chen, O.M. Aparicio, M.Q. Zhang, R. Jiang     and     T.            Chen,  Reconstructing         cell cycle pseudo time-series via single-cell transcriptome data. Nat. Commun. 8 (2017) 22.
  12. Na??cz-Charkiewicz, K., & Nowak, R. M. (2022). Algorithm for DNA sequence assembly by quantum annealing. BMC bioinformatics, 23(1), 122.
  13. Lawler, E. L. (1985). The traveling salesman problem: a guided tour of combinatorial optimization. Wiley-Interscience Series in Discrete Mathematics.
  14. Alkhalifa, R., Alkhomayes, F., Almazroua, B., Alhaidan, D., Alothman, M., & Almuhaidib, J. (2025). A comparative review of parallel exact, heuristic, metaheuristic, and hybrid optimization techniques for the traveling salesman problem. arXiv preprint arXiv:2505.18278.
  15. Williamson, D. P., & Shmoys, D. B. (2011). The design of approximation algorithms. Cambridge university press.
  16. Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., & Protasi, M. (1999). Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer.
  17. Saller, S., Koehler, J., & Karrenbauer, A. (2025). A survey on approximability of traveling salesman problems using the TSP-T3CO definition scheme. Annals of Operations Research, 351(3), 2129-2190.
  18. Rego, C., Gamboa, D., Glover, F., & Osterman, C. (2011). Traveling salesman problem heuristics: Leading methods, implementations and latest advances. European journal of operational research, 211(3), 427-441.
  19. Marinakis, Y. (2024). Heuristic and metaheuristic algorithms for the traveling salesman problem. In Encyclopedia of optimization (pp. 1-12). Cham: Springer International Publishing.
  20. Rosenkrantz, D. J., Stearns, R. E., & Lewis, II, P. M. (1977). An analysis of several heuristics for the traveling salesman problem. SIAM journal on computing, 6(3), 563-581.
  21. Boussaïd, I., Lepagnot, J., & Siarry, P. (2013). A survey on optimization metaheuristics. Information sciences, 237, 82-117.
  22. Talbi, E. G. (2009). Metaheuristics: from design to implementation. John Wiley & Sons.
  23. Helsgaun, K. (2000). An effective implementation of the Lin–Kernighan traveling salesman heuristic. European journal  of operational research, 126(1), 106-130.
  24. Coulom, R. (2006, May). Efficient selectivity and backup operators in Monte-Carlo tree search. In International conference on computers and games (pp. 72-83). Berlin, Heidelberg: Springer Berlin Heidelberg.
  25. Potvin, J. Y. (1996). Genetic algorithms for the traveling salesman problem. Annals of Operations Research, 63, 337–370.
  26. Larrañaga, P., Kuijpers, C. M. H., Murga, R. H., Inza, I., & Dizdarevic, S. (1999). Genetic algorithms for the travelling salesman problem: A review of representations and operators. Artificial Intelligence Review, 13(2), 129–170.
  27. Kennedy, J., Eberhart, R.C.: A discrete binary version of the particle swarm algorithm.  In:  1997  IEEE  International  Conference  on Systems, Man, and Cybernetics. Computational Cybernetics and Simulation, vol. 5, p. 4104–4108 (1997)
  28. Poli, R., Kennedy, J., Blackwell, T.: Particle swarm optimization:An overview. Swarm Intell. 1, 33–57 (2007)
  29. Bertsimas, D., Tsitsiklis, J.: Simulated annealing. Statist. Sci. 8(1),10–15 (1993)
  30. Corana, A., Marchesi, M., Martini, C., Ridella, S.: Minimizing multimodal functions of continuous variables with the “simulated annealing” algorithm-corrigenda for this article is available here. ACM Trans. Math. Softw. (TOMS) 13(3), 262–280 (1987)
  31. Glover, F., Laguna, M.: Tabu search. In: Du, D.Z., Pardalos, P.M.(eds.) Handbook of Combinatorial Optimization. Springer, Boston (1998)
  32. Glover, F.: Tabu search–part ii. ORSA J. Comput. 2(1), 4–32 (1990)
  33. Dorigo, M., & Gambardella, L. M. (1997). Ant colonies for the travelling salesman problem. BioSystems, 43(2), 73–81.
  34. A. Colorni, M. Dorigo, and V. Maniezzo, “Distributed optimization by ant colonies,” Proceedings of the First European Conference on Artificial Life,pp. 134–142, 1991.
  35. 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.
  36. Stützle, T., & Hoos, H. H. (2000). MAX–MIN ant system. Future generation computer systems, 16(8), 889-914.
  37. Bai, Z., Snášel, V., Vo, B., Kong, L., & Wang, X. (2023, October). A hybrid algorithm acs-ga for solving the traveling salesman problem. In International Conference on Genetic and Evolutionary Computing (pp. 71-82). Singapore: Springer Nature Singapore.
  38. Wu, Y., Wang, H., Li, M., Tan, H., Wang, D., & Sheng, M. (2025). The Adaptive two-stage ant colony simulated annealing algorithm for solving the traveling salesman problem. RAIRO-Operations Research, 59(2), 1199-1213.
  39. Tian, Y., Zhang, J., Wang, Q., Liu, S., Guo, Z., & Zhang, H. (2024). Application of hybrid algorithm based on ant colony optimization and sparrow search in UAV path planning. International Journal of Computational Intelligence Systems, 17(1), 286.
  40. Wang, Y., & Han, Z. (2021). Ant colony optimization for traveling salesman problem based on parameters optimization. Applied Soft Computing, 107, 107439.
  41. Liu, H. DAACO: adaptive dynamic quantity of ant ACO algorithm to solve the traveling salesman problem. Complex & Intelligent Systems. 9, 4317–4330 (2023).
  42. Dorigo, M., & Stützle, T. (2004). Ant Colony Optimization. MIT Press.
  43. Bullnheimer, B., Hartl, R. F., & Strauss, C. (1999). A New Rank Based Version of the Ant System: A Computational Study. Central European Journal for Operations Research and Economics, 7(1), 25–38.
  44. Lin, S. (1965). Computer solutions of the traveling salesman problem. Bell System Technical Journal, 44(10), 2245-2269.
  45. Lin, S., & Kernighan, B. W. (1973). An effective heuristic algorithm for the traveling-salesman problem. Operations research, 21(2), 498-516.
  46. Browne, C. B., Powley, E., Whitehouse, D., Lucas, S. M., Cowling, P. I., Rohlfshagen, P., ... & Colton, S. (2012). A survey of monte carlo tree search methods. IEEE Transactions on Computational Intelligence and AI in games, 4(1), 1-43.
  47. Chaslot, G. M. J., Winands, M. H., Herik, H. J. V. D., Uiterwijk, J. W., & Bouzy, B. (2008). Progressive strategies for Monte-Carlo tree search. New Mathematics and Natural Computation, 4(03), 343-357.
  48. Solomon, M. M. (1987). Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations research, 35(2), 254-265.
  49. Ropke, S., & Pisinger, D. (2006). An adaptive large neighborhood search heuristic  for  the  pickup  and  delivery  problem  with  time windows. Transportation science, 40(4), 455-472.
  50. Kocsis, L., & Szepesvári, C. (2006, September). Bandit based monte-carlo planning. In European conference on machine learning (pp. 282-293). Berlin, Heidelberg: Springer Berlin Heidelberg.
  51. Janjarassuk, U. (2024, May). Hybrid Ant Colony Optimization Method for the Traveling Salesman Problem. In 2024 9th International Conference on Business and Industrial Research (ICBIR) (pp. 292-295). IEEE.

Keywords

Traveling Salesman Problem. Max–Min Ant System. Monte Carlo Tree Search. Hybrid Metaheuristics. Adaptive Last-Mile Intensification. Destroy–Repair Search. Local Search.

Image
  • Format Volume 14, Issue 2, No 05, 2026
  • Copyright All Rights Reserved ©2026
  • Year of Publication 2026
  • Author Ahmad Hilal Al-Kurdi, Mariam Zmirly
  • Reference IJCS-748
  • Page No 016-033

Copyright 2026 SK Research Group of Companies. All Rights Reserved.