COMPARISON OF TRAVELLING SALESMAN PROBLEM OUTPUT USING NEAREST NEIGHBOUR AND GENETIC ALGORITHMS

albin Lamichahane
2020
BSc.CSIT
Semester 7
Downloads 5

Travelling Salesman Problem is an intensively studied problem in the field of Combinatorial Optimization. Being an NP-Hard problem, it is widely studied in the area of optimization. A problem is NP-Hard if its approximate solution is derived from the solution of the NP problem, i.e., an algorithm that is used to solve an NP problem can be modified to find the approximate solution to an NP-hard problem. The main objective of TSP is to find the minimum distance by traversing each of the given set of cities at least once and then traversing back to the start city. The project is aimed to provide a method for solving TSP using both Genetic and nearest neighbor Algorithms and provide efficient results and compare the result generated from both algorithms. The comparison depends on parameters of the number of cities that have both passed through algorithms and the result is calculated and checked based on their distance and execution time. To classify which algorithm produces the best optimal performance, several algorithms can be compared for solving the TSP under some conditions. Also, this project provides a comparison between the two algorithms based on various parameters that help to choose the better algorithm as per the needs. In the end, through the number of test cases, the obtained output is compared between the Nearest Neighbor and Genetic algorithm. Nearest Neighbor always provides a suboptimal path for the given number of cities while the Genetic algorithm provides a better result for the smaller number of cities. But for a larger number of cities, the execution time of the algorithm drastically increases making it hard to generate the optimal path better than Nearest Neighbor.

combinatorial optimization
Constraints
Genetic Algorithm
Time Table generation.
K nearest neighbor classifier
np-hard

Similar Projects