IAM-TSP: Iterative Approximate Methods for Solving the Travelling Salesman Problem

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.

@article{Alkafaween2023,
  title     = {IAM-TSP: Iterative Approximate Methods for Solving the Travelling Salesman Problem},
  journal   = {International Journal of Advanced Computer Science and Applications},
  volume    = {14},
  number    = {11},
  year      = {2023},
  publisher = {The Science and Information Organization},
  author    = {Esra’a Alkafaween and Samir Elmougy and Ehab Essa and Sami Mnasri and Ahmad S. Tarawneh and Ahmad Hassanat},
  doi       = {10.14569/IJACSA.2023.0141143},
  url       = {https://doi.org/10.14569/IJACSA.2023.0141143}
}