Indian Journal of Science and Technology

Abstract

Objectives: Travelling Salesman Problem is a well known NP-Complete problem. It has many application areas in science and engineering. NP-Complete problems are most difficult problems in computer science. Methods/Statistical Analysis: These problems are not solvable using tradition algorithms till date. Soft computing techniques such as Genetic Algorithm (GA) can be used to solve such problems. In this paper Travelling Salesman problem has been solved using Genetic Algorithm. The proposed algorithm modifies the traditional genetic algorithm. Proposed algorithm generates some chromosome using greedy approach and adds these chromosomes in initial population. It also proposes a new greedy cross over operator for genetic algorithm. Findings: The implementation results of proposed algorithm prove that proposed algorithm performs better as it find out paths of less path length as compared to the optimal path known till date. Application/Improvements: This work is helpful in finding optimal or near optimal solutions of TSP. The algorithm can find application in all the relevant areas of science and engineering where TSP is used such as robot arm movement, drilling electronic boards etc.

Keywords: Travelling Salesman Problem, Genetic Algorithm, Crossover, NP-Complete Problems