Nearest Neighbor Heuristic for Traveling Salesman Problem

Traveling Salesman Problem

Introduction

The traveling salesman problem is a well-known mathematical problem in which one tries to find the shortest route that passes through a set of points only once. The problem was first formulated in 1930 and is one of the most intensively studied problems in optimization. Since TSP is NP-hard, The time complexity exponentially increases to solve large problems with guaranteed optimality. TSP is to find the shortest hamiltonian cycle in a graph. There are several algorithms used to find optimal tours, but, none leads to feasible solutions for large instances since they all grow exponentially.

Nearest Neighbor

This is the most straightforward TSP heuristic method. The main objective of this algorithm is to visit the nearest city(node). The time complexity of the Nearest Neighbor algorithm is O(n2). Some statistics show that the NNH produces tours that are on average 15% longer than the optimal tour.

Nearest Neighbour Heuristic,

1. Select a random city as a starting point.
2. Find the nearest unvisited city that is the closest to the most recently visited and go there.
3. Repeat step 2 until it returns back to a starting point.

Note that each city is visited only once except at the starting point.

Let’s discuss this with an example. In the below table, A, B, C, D & E are cities, and numbers are the distance to visit each city.

We arbitrarily choose to begin at city A and visit the nearest city in row A to city A. From this distance matrix, we find the nearest city to city A is city B. The distance is 60. Then, Let’s look at row B to find the nearest city. The nearest city to city B is city A. But, it is already visited. We cannot go back to city A since it violates the one-time visit constraint. The second nearest city is city E. So, let’s go to city E, and the distance is 79. Now, look at row E. The nearest city to city E is city A & B. But, already visited. So, let’s search for the unvisited neighbors corresponding to city E. The unvisited nearest neighbor to city E is city D. Note that city A and city B are closer than city D. However, they have chosen city D as the next neighboring city because city A and city B are already visited. Hence, The nearest city to city E is city D and the distance is 196. Now, Look at row D to find the neighboring city. The neighboring city to city D is city C which is not visited yet. So, we go to city C, and the distance is 113. Eventually, all the cities have been visited. To complete the cycle, We directly go from city C back to city A and the distance from city C to city A is 217.

Now we found a tour, ABEDCA, and the total distance is 665. The snippet implemented based on the nearest neighbor algorithm to solve Traveling salesman problems where traveling distance varies from city to city.

nearest neighbor heuristic for traveling salesman problem

source code available on my repo

Thank you

#travelingsalesmanproblem #nearestneighbor #shortestpath