An Efficient Approach to Solve Travelling Salesman Problem

Abstract

Travelling salesman problem is a very old mathematical problem. It models a scenario where a salesman has many cities to visit in shortest possible time. Given the distance among the cities, he must calculate the shortest route. Researchers have been working with Travelling Salesman problem for over centuries. Many models have been introduced to solve this legendary mathematical problem. In this Research Work, genetic algorithm is used to solve Travelling Salesman Problem. Genetic algorithm is a technique used for estimating computer models based on methods adapted from the field of genetics in biology. To use this technique, one encodes possible model behaviors into ''genes". We designed a new crossover technique to increase the efficiency of crossover operator of GA for TSP. We also apply map reduce algorithm to efficiently solve the TSP.