Mir Mohammad Alipour

There are some approximation algorithms for travelling salesman problem, whose approximation ratios are tight. So, it is a challenge to transform the obtained approximate solution into a nearly optimal solution. the genetic algorithm is an evolutionary algorithm and 2-opt heuristic method is a local search algorithm; then, a hybrid algorithm is developed to improve an approximate solution and to avoid from such a local optimal solution. The genetic algorithm does not yield high quality population for the initial approximate solution, because of local optimality; 2-opt heuristic as well needs many iterations to obtain a good solution. The Christofides algorithm provides a 1.5-approximate solution for the symmetric travelling salesman problem, where the arc costs satisfy the triangle inequality. So, the approximate solution is applied to produce the initial population for the genetic algorithm. Then, the crossover and the mutation operators produce some offspring by 2-opt heuristic method. Therefore, the hybrid algorithm could produce a near optimal solution in a reasonable iteration. It is implemented on some travelling salesman instances, and the results determine the hybrid algorithm efficiency.