Metrics
5 File views/ downloads
157 Record Views
Journal article
Revisiting Traveling Salesman Problem (TSP): Analysis of GA and SA based solutions
International Journal of Recent Contributions from Engineering, Science & IT, Vol.9, pp.44-56
9
2021
Abstract
The purpose of this study to analyze genetic algorithm (GA) and simulated annealing (SA) based approaches applied to well-known Traveling Salesman Problem (TSP). As a NP-Hard problem, the goal of TSP is to find the shortest route possible to travel all the cities, given a set of cities and distances between cities. In order to solve the problem and achieve the optimal solution, all permutations need to be checked, which gets exponentially large as more cities are added. Our aim in this study is to provide comprehensive analysis of TSP solutions based on two methods, GA and SA, in order to find a near optimal solution for TSP. The results of the simulations show that although the SA executed with faster completion times comparing to GA, it took more iterations to find a solution. Additionally, GA solutions are significantly more accurate than SA solutions, where GA found a solution in relatively less iterations. The original contribution of this study is that GA based solution as well as SA based solution are developed to perform comprehensive parameter analysis. Further, a quantifiable comparison is provided for the results from each parameter analysis of GA and SA in terms of performance of solving TSP.
Files and links (1)
Related links
Details
- Title
- Revisiting Traveling Salesman Problem (TSP)
- Publication Details
- International Journal of Recent Contributions from Engineering, Science & IT, Vol.9, pp.44-56
- Resource Type
- Journal article
- Publisher
- Kassel University Press GmbH; Germany
- Series
- 9
- Copyright
- Attribution 3.0 Austria (CC BY 3.0 AT)
- Identifiers
- 99380090879406600
- Academic Unit
- Intelligent Systems and Robotics
- Language
- English