A Novel Method to Solve Travelling Salesman Problem Using Sequential Constructive Crossover Using Map/Reduce Framework

Anitha Rao, Sandeep Kumar Hegde

Abstract: The Travelling Salesman Problem (TSP) is well known in the field of combinatorial optimization. Since it is an NP-complete problem, there is no efficient method to solve this problem and give the best result. Many algorithms are used to solve travelling salesman problem. Some algorithms give optimal solution, but some other algorithms give the nearest optimal solution. The genetic algorithm is a heuristic method which is used to improve the solution space for the Travelling Salesman Problem. The genetic algorithm results in nearest optimal solution within a reasonable time. This paper mainly focuses on the various stages of genetic algorithm and comparative study of various methods used in the genetic algorithm. The paper also proposes a method to solve the travelling salesman problem using Sequential Constructive Crossover operator and hence improve the quality of solution space.

Keywords: Travelling Salesman Problem, Genetic Algorithm, Selection, Sequential Constructive Crossover, Mutation