A Novel Insertion Solution for the Travelling Salesman Problem

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.