Future of Information and Communication Conference (FICC) 2024
4-5 April 2024
Publication Links
IJACSA
Special Issues
Future of Information and Communication Conference (FICC)
Computing Conference
Intelligent Systems Conference (IntelliSys)
Future Technologies Conference (FTC)
International Journal of Advanced Computer Science and Applications(IJACSA), Volume 14 Issue 11, 2023.
Abstract: TSP is a well-known combinatorial optimization problem with several practical applications. It is an NP-hard problem, which means that the optimal solution for huge numbers of examples is computationally impractical. As a result, researchers have focused their efforts on devising efficient algorithms for obtaining approximate solutions to the TSP. This paper proposes Iterative Approximate Methods for Solving TSP (IAM-TSP), as a new method that provides an approximate solution to TSP in polynomial time. This proposed method begins by adding four extreme cities to the route, a loop, and then adds each city to the route using a greedy technique that evaluates the cost of adding each city to different positions along the route. This method determines the best position to add the city and the also the best city to be added. The resultant route is further improved by employing local constant permutations. When compared to existing state-of-the-art methods, our experimental results show that the proposed method is more capable of producing high-quality solutions. The proposed approach, with an average approximation of 1.09, can be recommended for practical usage in its current form or as a pre-processing step for another optimizer.
Esra’a Alkafaween, Samir Elmougy, Ehab Essa, Sami Mnasri, Ahmad S. Tarawneh and Ahmad Hassanat, “IAM-TSP: Iterative Approximate Methods for Solving the Travelling Salesman Problem” International Journal of Advanced Computer Science and Applications(IJACSA), 14(11), 2023. http://dx.doi.org/10.14569/IJACSA.2023.0141143
@article{Alkafaween2023,
title = {IAM-TSP: Iterative Approximate Methods for Solving the Travelling Salesman Problem},
journal = {International Journal of Advanced Computer Science and Applications},
doi = {10.14569/IJACSA.2023.0141143},
url = {http://dx.doi.org/10.14569/IJACSA.2023.0141143},
year = {2023},
publisher = {The Science and Information Organization},
volume = {14},
number = {11},
author = {Esra’a Alkafaween and Samir Elmougy and Ehab Essa and Sami Mnasri and Ahmad S. Tarawneh and Ahmad Hassanat}
}
Copyright Statement: This is an open access article licensed under a Creative Commons Attribution 4.0 International License, which permits unrestricted use, distribution, and reproduction in any medium, even commercially as long as the original work is properly cited.