Open Access

ARTICLE

A Novel Insertion Solution for the Travelling Salesman Problem

by Emmanuel Oluwatobi Asani^1,2,3, Aderemi Elisha Okeyinka⁴, Sunday Adeola Ajagbe^5,6, Ayodele Ariyo Adebiyi¹, Roseline Oluwaseun Ogundokun^1,2,7,*, Temitope Samson Adekunle⁸, Pragasen Mudali⁵, Matthew Olusegun Adigun⁵

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:

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

Received 21 November 2023; Accepted 19 March 2024; Issue published 25 April 2024

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

---