A Dynamic-start, Dynamic-end Insertion Heuristic for Solving the Traveling Salesperson Problem
International Journal of Innovations in Science and Technology · 07.02.2026 · 307
DOI: 10.33411/ijist/ojs1733 ↗Kurz gefasst
Fachartikel in der Zeitschrift International Journal of Innovations in Science and Technology, online erschienen am 07.02.2026. Verfasst von Poorab Gangwani und 6 weiteren Autor:innen. Die Arbeit nennt 13 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
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(n2) time complexity while improving practical performance, making ILNI a computationally efficient and structurally robust alternative to classical nearest insertion heuristics.
Zitieren
APA
Gangwani, P., Lodhi, U., Owais, M., Yazdani, S. S., Farooq, A., Farrukh, Q., & Rasheed, K. (2026). A Dynamic-start, Dynamic-end Insertion Heuristic for Solving the Traveling Salesperson Problem. International Journal of Innovations in Science and Technology, 307. https://doi.org/10.33411/ijist/ojs1733
Vancouver
Gangwani P, Lodhi U, Owais M, Yazdani SS, Farooq A, Farrukh Q, et al. A Dynamic-start, Dynamic-end Insertion Heuristic for Solving the Traveling Salesperson Problem. International Journal of Innovations in Science and Technology. 2026:307. doi:10.33411/ijist/ojs1733
BibTeX
@article{Gangwani2026,
author = {Gangwani, Poorab and Lodhi, Uzair and Owais, Muhammad and Yazdani, Syed Samar and Farooq, Afifa and Farrukh, Qazi and Rasheed, Khalid},
title = {A Dynamic-start, Dynamic-end Insertion Heuristic for Solving the Traveling Salesperson Problem},
journal = {International Journal of Innovations in Science and Technology},
year = {2026},
pages = {307},
doi = {10.33411/ijist/ojs1733}
}
EUVIMED