UNRAVELING TRAVELLING SALESMAN PROBLEM BY GENETIC ALGORITHM USING M-CROSSOVER OPERATOR

Travelling Salesman Problem (TSP) is a NP - Hard problem and one of the most studied problems related to many research areas. The main aim of this problem is to search the shortest (or cheapest) tour for a salesman to visit all cities exactly once and finally return to the starting city. Many real life problems which are a variant of TSP would be solved easily if the Travelling Salesman Problem could be solved that efficiently. Applications of Travelling Salesman Problem consists of Vehicle Routing, Job Sequencing, Computer Wiring, etc. Since brute force approach is an infeasible option, heuristics approach can be fairly relied upon to solve these kind of problems where heuristics approach utilizes much less computing power. Although solution from heuristics approach may not be the best solution, it surely provides much better solution. Genetic algorithm is one such heuristic search technique which is based upon genetic and natural selection. Genetic algorithm can perform this task by applying three operators viz. selection, crossover and mutation. In this paper, the authors propose a new crossover operator model (called m-crossover) of genetic algorithm to solve the travelling salesman problem. The proposed model is able to produce 18 different valid offspring chromosomes from any two valid parent chromosomes and select best two offspring chromosomes from the newly generated 18 chromosomes. We compared the efficiency of our crossover operator with existing crossover operators viz. Partially Mapped Crossover, Order Crossover, Cycle Crossover. Experimental results by applying our new crossover approach prove that it is faster at searching better solutions that the compared crossover operators. In addition to this, challenges and constraints of the proposed research work are also discussed.