An Improvement to the 2-Opt Heuristic Algorithm for Approximation of Optimal TSP Tour
Applied Sciences · 20.06.2023 · 13 (12) · 7339
DOI: 10.3390/app13127339 ↗Kurz gefasst
Fachartikel in der Zeitschrift Applied Sciences, online erschienen am 20.06.2023. Verfasst von Fakhar Uddin und 6 weiteren Autor:innen. Die Arbeit wurde bisher 37-mal zitiert (Crossref) und nennt 27 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Ministry of Trade, Industry, and Energy (MOTIE), Korea Institute for the Advancement of Technology (KIAT).
Abstract (Originalsprache)
The travelling salesman problem (TSP) is perhaps the most researched problem in the field of Computer Science and Operations. It is a known NP-hard problem and has significant practical applications in a variety of areas, such as logistics, planning, and scheduling. Route optimisation not only improves the overall profitability of a logistic centre but also reduces greenhouse gas emissions by minimising the distance travelled. In this article, we propose a simple and improved heuristic algorithm named 2-Opt++, which solves symmetric TSP problems using an enhanced 2-Opt local search technique, to generate better results. As with 2-Opt, our proposed method can also be applied to the Vehicle Routing Problem (VRP), with minor modifications. We have compared our technique with six existing algorithms, namely ruin and recreate, nearest neighbour, genetic algorithm, simulated annealing, Tabu search, and ant colony optimisation. Furthermore, to allow for the complexity of larger TSP instances, we have used a graph compression/candidate list technique that helps in reducing the computational complexity and time. The comprehensive empirical evaluation carried out for this research work shows the efficacy of the 2-Opt++ algorithm as it outperforms the other well-known algorithms in terms of the error margin, execution time, and time of convergence.
Förderung
- Ministry of Trade, Industry, and Energy (MOTIE)
- Korea Institute for the Advancement of Technology (KIAT)
Zitieren
APA
Uddin, F., Riaz, N., Manan, A., Mahmood, I., Song, O., Malik, A. J., & Abbasi, A. A. (2023). An Improvement to the 2-Opt Heuristic Algorithm for Approximation of Optimal TSP Tour. Applied Sciences, 13(12), 7339. https://doi.org/10.3390/app13127339
Vancouver
Uddin F, Riaz N, Manan A, Mahmood I, Song O, Malik AJ, et al. An Improvement to the 2-Opt Heuristic Algorithm for Approximation of Optimal TSP Tour. Applied Sciences. 2023;13(12):7339. doi:10.3390/app13127339
BibTeX
@article{Uddin2023,
author = {Uddin, Fakhar and Riaz, Naveed and Manan, Abdul and Mahmood, Imran and Song, Oh-Young and Malik, Arif Jamal and Abbasi, Aaqif Afzaal},
title = {An Improvement to the 2-Opt Heuristic Algorithm for Approximation of Optimal TSP Tour},
journal = {Applied Sciences},
year = {2023},
volume = {13},
number = {12},
pages = {7339},
doi = {10.3390/app13127339}
}
EUVIMED