A Dynamic-start, Dynamic-end Insertion Heuristic for Solving the Traveling Salesperson Problem

Abstract

The traveling salesperson problem (TSP) is one of the most extensively studied NP-hard combinatorial optimization problems with wide applicability in logistics, routing, manufacturing, and network design, making efficient heuristic solutions crucial for practical applications. This paper introduces the Ideal Link Nearest Insertion (ILNI) heuristic, a dynamic-start, dynamic-end insertion method that addresses the structural limitations of classical Nearest Insertion (NI) through dynamic route reconfiguration and path-based route initialization, maintaining an open path structure that allows endpoint insertions throughout the construction process. The proposed heuristic was evaluated on 1,100 randomly generated symmetric TSP instances ranging from 50 to 150 cities, repeated across ten independent iterations (11,000 total comparisons). Using LKH-3 as a reference solver, ILNI achieved a 4.3% improvement in average approximation ratio (2.3753 vs. 2.4819) and a 15.9% reduction in execution time (0.0127s vs. 0.0151s per instance) compared to classical NI. ILNI produced lower-cost tours in 67.3% of instances, demonstrating consistent superiority across all tested problem sizes. Paired t-tests conducted on all 11,000 paired observations confirmed statistically significant improvements in both solution quality and computational efficiency (p < 0.001). The proposed heuristic maintains O(n²) time complexity while improving practical performance, making ILNI a computationally efficient and structurally robust alternative to classical nearest insertion heuristics.