Travelling Salesman Problem Analysis

A COMPARITIVE STUDY OF NEAREST NEIGHBOUR ALGORITHM AND GENETIC ALGORITHM IN SOLVING TRAVELLING SALESMAN PROBLEM

Ajaz Ahmed Khan
Electronics and communication department
SSGI FET
Bhilai, India ajz70277@gmail.com Mrs. Himani Agrawal Electronics and communication department
SSGI FET
Bhilai, India

Abstract—In this paper, we have used two algorithms, i.e. the Nearest Neighbor algorithm and Genetic Algorithm to solve the Travelling Salesman problem. The Travelling Salesman problem is a widely studied problem in computational mathematics. In the Travelling Salesman problem, a salesman has to visit all the cities first and then move to the same city from where it has started its whole journey. One of the concerns here with this problem, here is that the salesman cannot visit a single city twice. There are several optimization techniques such as ant colony optimization, particle swarm optimization, genetic algorithm, nearest neighbor algorithm, etc. out of which we have solved Travelling salesman problem using a Genetic algorithm and Nearest neighbor algorithm. In our paper, we have shown that for the same group of cities plotted at different location, Genetic Algorithm …show more content…
At Symmetric TSP, the distance between each city is same in the opposite direction as shown in Fig.2. In Asymmetric TSP, there may be or may not be pah exist between two cities. Many approximations and heuristic algorithm have been utilized to find the solution of the Travelling Salesman problem. Some of them are ant colony optimization, particle swarm optimization, genetic algorithm, nearest neighbor algorithm, etc. out of which we have utilized Genetic Algorithm and Nearest Neighbor Algorithm. In the later part, we have explained both Nearest Neighbor Algorithm and Genetic Algorithm in Section