EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

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

Poorab Gangwani, Uzair Lodhi, Muhammad Owais, Syed Samar Yazdani, Afifa Farooq, Qazi Farrukh, Khalid Rasheed

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).

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →