A COMPARATIVE STUDY BETWEEN THE NEAREST-NEIGHBOUR ALGORITHM AND ITS VARIANTS FOR SOLVING THE EUCLIDEAN TRAVELING SALESMAN PROBLEM

Authors

  • Lilysuriazna Raya
  • Safaa Najah Saud

Abstract

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.

Downloads

Download data is not yet available.

Downloads

Published

2020-12-31

How to Cite

Lilysuriazna Raya, & Safaa Najah Saud. (2020). A COMPARATIVE STUDY BETWEEN THE NEAREST-NEIGHBOUR ALGORITHM AND ITS VARIANTS FOR SOLVING THE EUCLIDEAN TRAVELING SALESMAN PROBLEM. PalArch’s Journal of Archaeology of Egypt / Egyptology, 17(10), 938-945. Retrieved from https://www.archives.palarch.nl/index.php/jae/article/view/4743