A COMPARATIVE STUDY BETWEEN THE NEAREST-NEIGHBOUR ALGORITHM AND ITS VARIANTS FOR SOLVING THE EUCLIDEAN TRAVELING SALESMAN PROBLEM - Lilysuriazna Raya; Safaa Najah Saud (PalArch's Journal of Archaeology of Egypt / Egyptology, 2020)
The Euclidean travelling salesman problem is a subcase of metric travelling salesman problem which also considered as NP-complete and typically solved using numerous heuristics methods. One of the most natural heuristics is the Nearest-Neighbour (NN) algorithm. In this paper, we propose a new hybrid heuristic approach based on the NN and Two Directional Nearest-Neighbour (2NN) algorithms for solving the travelling salesman problem. The underlying idea is to take advantage of these algorithms by fixing a certain number of cities to be inserted in the solution tour either by using the NN or 2NN algorithm. The number of cities is determined by the contribution ratio . If cities are selected following the NN algorithm, then the remaining cities will be selected following the 2NN algorithm and vice versa. The performance of this proposed hybrid heuristic is evaluated by using 12 TSP benchmark problems and the experimental results are empirically compared with the NN and 2NN approaches, respectively. The analysis shows that the proposed algorithm has a better performance than the conventional NN and 2NN heuristic with the average percentage of error of less than 13%. Since IoNN has tremendously improved the NN and 2NN solution, it has a great potential to be used as a construction heuristic in other heuristic or metaheuristic approaches.