Open Access iconOpen Access

ARTICLE

crossmark

A Novel Insertion Solution for the Travelling Salesman Problem

Emmanuel Oluwatobi Asani1,2,3, Aderemi Elisha Okeyinka4, Sunday Adeola Ajagbe5,6, Ayodele Ariyo Adebiyi1, Roseline Oluwaseun Ogundokun1,2,7,*, Temitope Samson Adekunle8, Pragasen Mudali5, Matthew Olusegun Adigun5

1 Department of Computer Science, Landmark University, Omu Aran, 251103, Nigeria
2 SDG 11 Group, Landmark University, Omu Aran, 251103, Nigeria
3 Department of Computing, MiVA University, Abuja, 900211, Nigeria
4 Department of Computer Science, Ibrahim Badamasi Babangida University, Lapai, 911101, Nigeria
5 Department of Computer Science, University of Zululand, Kwadlangezwa, 3886, South Africa
6 Department of Computer & Industrial Production Engineering, First Technical University, Ibadan, 200243, Nigeria
7 Department of Multimedia Engineering, Kaunas University of Technology, Kaunas, LT-44249, Lithuania
8 Department of Computer Science, Colorado State University, Fort Collins, 80523, USA

* Corresponding Author: Roseline Oluwaseun Ogundokun. Email: email

Computers, Materials & Continua 2024, 79(1), 1581-1597. https://doi.org/10.32604/cmc.2024.047898

Abstract

The study presents the Half Max Insertion Heuristic (HMIH) as a novel approach to solving the Travelling Salesman Problem (TSP). The goal is to outperform existing techniques such as the Farthest Insertion Heuristic (FIH) and Nearest Neighbour Heuristic (NNH). The paper discusses the limitations of current construction tour heuristics, focusing particularly on the significant margin of error in FIH. It then proposes HMIH as an alternative that minimizes the increase in tour distance and includes more nodes. HMIH improves tour quality by starting with an initial tour consisting of a ‘minimum’ polygon and iteratively adding nodes using our novel Half Max routine. The paper thoroughly examines and compares HMIH with FIH and NNH via rigorous testing on standard TSP benchmarks. The results indicate that HMIH consistently delivers superior performance, particularly with respect to tour cost and computational efficiency. HMIH's tours were sometimes 16% shorter than those generated by FIH and NNH, showcasing its potential and value as a novel benchmark for TSP solutions. The study used statistical methods, including Friedman's Non-parametric Test, to validate the performance of HMIH over FIH and NNH. This guarantees that the identified advantages are statistically significant and consistent in various situations. This comprehensive analysis emphasizes the reliability and efficiency of the heuristic, making a compelling case for its use in solving TSP issues. The research shows that, in general, HMIH fared better than FIH in all cases studied, except for a few instances (pr439, eil51, and eil101) where FIH either performed equally or slightly better than HMIH. HMIH's efficiency is shown by its improvements in error percentage (δ) and goodness values (g) compared to FIH and NNH. In the att48 instance, HMIH had an error rate of 6.3%, whereas FIH had 14.6% and NNH had 20.9%, indicating that HMIH was closer to the optimal solution. HMIH consistently showed superior performance across many benchmarks, with lower percentage error and higher goodness values, suggesting a closer match to the optimal tour costs. This study substantially contributes to combinatorial optimization by enhancing current insertion algorithms and presenting a more efficient solution for the Travelling Salesman Problem. It also creates new possibilities for progress in heuristic design and optimization methodologies.

Keywords


Cite This Article

APA Style
Asani, E.O., Okeyinka, A.E., Ajagbe, S.A., Adebiyi, A.A., Ogundokun, R.O. et al. (2024). A novel insertion solution for the travelling salesman problem. Computers, Materials & Continua, 79(1), 1581-1597. https://doi.org/10.32604/cmc.2024.047898
Vancouver Style
Asani EO, Okeyinka AE, Ajagbe SA, Adebiyi AA, Ogundokun RO, Adekunle TS, et al. A novel insertion solution for the travelling salesman problem. Comput Mater Contin. 2024;79(1):1581-1597 https://doi.org/10.32604/cmc.2024.047898
IEEE Style
E.O. Asani et al., "A Novel Insertion Solution for the Travelling Salesman Problem," Comput. Mater. Contin., vol. 79, no. 1, pp. 1581-1597. 2024. https://doi.org/10.32604/cmc.2024.047898



cc This work is licensed under a Creative Commons Attribution 4.0 International License , which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
  • 196

    View

  • 99

    Download

  • 0

    Like

Share Link