Improvement of the Nearest Neighbor Algorithm for Traveling Salesman Problem

The Traveling Salesman Problem (TSP) is a non-deterministic polynomial (NP) hard problem that has been used in a variety of disciplines of science and technology. Various optimization techniques have been developed by scientists and researchers to solve it effectively and efficiently. Among these algorithms, heuristic algorithms are much more suitable to tackle with this complex problem. One of the simplest and easily implementable heuristic algorithms for TSP is Nearest Neighbor Algorithm (NNA). However, its solution quality suffers from randomness owing to the optimization process. In this project, we improve the basic NNA for symmetric TSP. In fact, the improved version of NNA is a deterministic approach, which starts with an edge consisting of the closest two cities, and then connects them simultaneously with the closest cities one by one-on-one ends until feasible routes are formed. The experiments are conducted on a collection of benchmark symmetric TSP datasets taken from TSPLIB to evaluate the algorithm. It is observed from the experimental results, the improved NNA outperforms basic NNA in terms of solution quality as well as the computational time.

• Supervision