A comparative study of heuristic and exact algorithms: the case of cheapest insertion heuristic and branch and bound algorithm

Abdulkareem, Shams Raed; Elaibi, Waleed Mohammed

doi:10.37652/juaps.2025.165439.1711

	A comparative study of heuristic and exact algorithms: the case of cheapest insertion heuristic and branch and bound algorithm
Journal of University of Anbar for Pure Science
Volume 20, Issue 2, August 2026, Pages 386-394 PDF (1.17 M)
Document Type: Research Paper
DOI: 10.37652/juaps.2025.165439.1711
Authors
Shams Raed Abdulkareem¹; Waleed Mohammed Elaibi^* ²
¹Department of Statistics, College of Administration and Economics, Mustansiriyah University, Iraq
²Department of Statistics, College of Administration and Economics, Mustansiriyah University
Abstract
The Traveling Salesman Problem (TSP) is one of the most prominent combinatorial optimization problems, attracting significant interest in both research and practical applications. This paper compares the performance of two approaches for solving the TSP: the Cheapest Insertion Heuristic (CIH) and the Branch-and-Bound (B&B) algorithm. The results show that CIH produced a route of 584 km. This approach is simple and fast to execute, but it provides approximate solutions and does not guarantee optimality. In contrast, B&B was effective in finding the optimal solution by relying on lower-bound (LB) calculations and systematically eliminating nonpromising branches. The best route obtained using B&B was A → D → C → B → E → A. The comparison suggests that CIH is more suitable for large-scale problems requiring quick solutions, whereas B&B is preferable when obtaining the optimal solution is essential, despite its higher computational cost and longer execution time.
Keywords
Branch and bound algorithm; CIH; Geographic Information Systems (GIS); traveling salesman problem

References
[1] Bavishi T, Shekhar S. Application of Geographic Information System (GIS) in Watershed Management. Plant Archives. 2025;25(Special Issue (ICTPAIRS-JAU)):483-8. ICTPAIRS-JAU Special Issue, January 2025. 10.51470/PLANTARCHIVES.2025.v25.SP.ICTPAIRS-069 [2] Asani EO, Okeyinka AE, Ajagbe SA, Adebiyi AA, Ogundokun RO, Adekunle TS, et al. A Novel Insertion Solution for the Travelling Salesman Problem. Computers, Materials & Continua. 2024;79(1):1581-97.10.32604/cmc.2024.047898 [3] Alatartsev S, Augustine M, Ortmeier F.Constricting Insertion Heuristic for Traveling Salesman Problem with Neighborhoods.Proceedings of the International Conference on Automated Planning and Scheduling. 2013;23(1):2-10.10.1609/icaps.v23i1.13539 [4] Chacón J, Irigaray C, Fernández T, El Hamdouni R. Engineering Geology Maps: Landslides and Geographical Information Systems.Bulletin of Engineering Geology and the Environment. 2006;65(4):341-411.10.1007/s10064-006-0064-z [5] Curtin KM. Network Analysis in Geographic Information Science: Review, Assessment, and Projections. Cartography and Geographic Information Science. 2007;34(2):103-11. 10.1559/152304007781002163 [6] Demez H. Combinatorial Optimization: Solution Methods of Traveling Salesman Problem [Master’s thesis]. Famagusta, North Cyprus: Eastern Mediterranean University; 2013. Department of Mathematics; supervisor: Arif Akkeleş.Available from: https://hdl.handle.net/11129/654 [7] Davendra D, editor. Traveling Salesman Problem, Theory and Applications.Rijeka, Croatia: InTech; 2010.10.5772/547 [8] Dawood SM, Elaibi WM, Chachan HA. Solving the Fuzzy Assignment Problems via Utilizing Branch and Bound Algorithm—Practically Treated. Italian Journal of Pure and Applied Mathematics. 2022;48:481-90. Available from: https://ijpam.uniud.it/journal/onl_2022-48.htm [9] Elaibi WM, Rahi ARK. The Lowest Merit Index in the Branch-and-Bound Algorithm of Structure a Railway Network with Application. In: AIP Conference Proceedings. vol. 2475. AIP Publishing; 2023. p. 080003. 2nd International Conference on Mathematical Techniques and Applications (ICMTA2021).10.1063/5.0102767 [10] Hu P. Travel the Same Path: A Novel TSP Solving Strategy; 2022. Available from: https://arxiv.org/abs/2210.05906 [11] Işık EE, Şimşir M. Maximizing Total Net Profit for Traveling Salesman Problem with Profits Using Metaheuristic Algorithms. The European Journal of Research and Development. 2023;3(1):46-59. 10.56038/ejrnd.v3i1.228 [12] Kianfar K. Branch-and-Bound Algorithms. In: Cochran JJ, editor. Wiley Encyclopedia of Operations Research and Management Science. John Wiley & Sons; 2011. 10.1002/9780470400531.eorms0116 [13] Mele UJ, Gambardella LM, Montemanni R.A New Constructive Heuristic Driven by Machine Learning for the Traveling Salesman Problem. Algorithms. 2021;14(9):267.10.3390/a14090267 [14] Papadimitriou CH, Steiglitz K.Combinatorial Optimization: Algorithms and Complexity.Mineola, NY: Courier Corporation; 1998.Unabridged reprint of the 1982 Prentice-Hall edition [15] Rosenkrantz DJ, Stearns RE, Lewis PM II. An Analysis of Several Heuristics for the Traveling Salesman Problem. SIAM Journal on Computing. 1977;6(3):563-81.10.1137/0206041 [16] Renaud J, Boctor FF, Ouenniche J. A Heuristic for the Pickup and Delivery Traveling Salesman Problem. Computers & Operations Research. 2000;27(9):905-16. 10.1016/S0305-0548(99)00066-0 [17] Sinaga RP, Marpaung F. Perbandingan Algoritma Cheapest Insertion Heuristic Dan Nearest Neighbor Dalam Menyelesaikan Traveling Salesman Problem. Jurnal Riset Rumpun Matematika dan Ilmu Pengetahuan Alam. 2023;2(2):238-47.10.55606/jurrimipa.v2i2.1614 [18] Sui J, Ding S, Huang X, Yu Y, Liu R, Xia B, et al.A Survey on Deep Learning-Based Algorithms for the Traveling Salesman Problem.Frontiers of Computer Science. 2025;19(6):196322. Published online 12 December 2024.10.1007/s11704-024-40490-y [19] Utomo RG, Maylawati DS, Alam CN. Implementasi Algoritma Cheapest Insertion Heuristic (CIH) dalam Penyelesaian Travelling Salesman Problem (TSP). Jurnal Online Informatika. 2018;3(1):61-7. 10.15575/join.v3i1.218 [20] Mohd Yunus MZ, Hassan H.Managing Road Maintenance Using Geographic Information System Application. Journal of Geographic Information System. 2010;2(4):215-8.10.4236/jgis.2010.24030
Statistics Article View: 128 PDF Download: 345