A COMPARATIVE STUDY OF BRUTE FORCE METHOD, NEAREST NEIGHBOUR AND GREEDY ALGORITHMS TO SOLVE THE TRAVELLING SALESMAN PROBLEM

A salesperson desires to travel from a city to all the other cities exactly once a time to sell his products and return back to the city where he started from. He wants to cover this in minimum time with minimum distance while travelling. This paper discuss on a proper path of travelling Salesman. TSP is an application of graph theory. In the term of graph theory, given a list of cities and their pair-wise distance, the task is to find a shortest possible tour (Hamiltonian Cycle) that visits every city exactly once. Even though TSP is an easy to understand, but it is very difficult to solve. Researchers have proven that Travelling Salesman Problem is NP-complete. This paper explains a simple demonstration of the uses of modern graph theory by formulating a “plan of travel” between five metro cities: Delhi, Kolkata, Mumbai, Sheila, and Ahmadabad. The procedure included the utilization of the four major algorithms in graph theory to create a “plan of travel” that would model the more sophisticated technology used by computer system like map quest. This paper focused on finding the route with the lowest cost and the route with smallest distance. We also study the history and growth of TSP by graph theory.