Open AccessRevisiting Traveling Salesman Problem (TSP): Analysis of GA and SA based Solutions
Author(s) -
Darius Bethel,
Hakkı Erhan Sevil
Publication year - 2021
Publication title -
international journal of recent contributions from engineering, science and it
Language(s) - English
Resource type - Journals
ISSN - 2197-8581
DOI - 10.3991/ijes.v9i2.22317
Subject(s) - travelling salesman problem , mathematical optimization , genetic algorithm , set (abstract data type) , computer science , mathematics , order (exchange) , solution set , finance , economics , programming language
The purpose of this study to analyze genetic algorithm (GA) and simulated an-nealing (SA) based approaches applied to well-known Traveling Salesman Prob-lem (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 re-sults of the simulations show that although the SA executed with faster comple-tion times comparing to GA, it took more iterations to find a solution. Additional-ly, 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.