ResearchBib Share Your Research, Maximize Your Social Impacts
Sign for Notice Everyday Sign up >> Login

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

Journal: IMPACT : International Journal of Research in Engineering & Technology ( IMPACT : IJRET ) (Vol.2, No. 6)

Publication Date:

Authors : ; ;

Page : 59-72

Keywords : Graph Theory; Minimum Distance; Minimum Cost; Route; Travelling Salesman;

Source : Download Find it from : Google Scholarexternal

Abstract

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.

Last modified: 2014-07-03 22:10:00