A Hybrid Heuristic Algorithm for the Euclidean Traveling Salesman Problem

In this paper, we propose hybrid algorithm, 2-opt optimal (2-opt) heuristic mutation with nearest neighbor (NN) tour construction, for solving traveling salesman problem (TSP). In this method, we first initialize suboptimal solution with the help of NN tour construction then DPX crossover is being used and after that 2-opt heuristic method is applied to refine solution for global optimality. Standard benchmark data from TSPLIB is used to evaluate the performance of proposed algorithm. The proposed algorithm gives better performance in term of best and average error. The proposed algorithm decreases the best error values in comparison to other methods with the ratio in between 19.13% and 90.55% and average error values between 32.16% and 86.10%.