Spatial algorithms under the hood III: The Traveling Salesperson Problem

The Traveling Salesperson problem (TSP) is a problem that I wanted to better understand for a long time. The problem itself is simple to explain: Imagine a salesperson who needs to travel to different cities and back to the home city - in which order do the cities visited make up the shortest overall distance? When it comes to applications, the TSP does not have to be strictly geospatial: The distance can be replaced by any value, such as cost (e.g flight tickets) or time. The solution to the problem is far less simple: In fact, there are many solutions, some heuristic (i.e. approximations) and some exact, some computationally more or less intensive. It might be worth to note that the TSP is considered a Graph Theory problem, but for this post knowing about Graph Theory is not strictly necessary. Instead, I want to explore the simplest way to solve the TSP in an exact manner and compare it with an approximation (and hopefully explore more advanced alternatives in the future!).

Let’s jump into the logic of the exact algorithm first. The basic way to solve this problem is to find all possible combinations of cities and select the combination - or tour - of cities that makes up the shortest overall distance. This idea illustrated for 4 cities named A,B,C and D in Fig. 1.

TSP with four cities

Let’s have a look at how this could be done in code too:

#Get distance between 2 points
def dist(point1, point2):
    return ((point1[0] - point2[0])**2 + (point1[1] - point2[1])**2) ** 0.5

#Total distance for each tour
def calcDist(points):
   totalDist = sum([dist(points[i], points[i - 1]) for i in range(len(points))])
   return totalDist

#Get tour with shortest distance from an array of tours
def shortest(points):
   return min(points, key = calcDist)

#TSP brute force main function
def tsp_brute(points):
   return f"shortest path: {shortest([points for points in itertools.permutations(points)])}"

The main function tsp_brute() takes an array of tuples as input and shuffles the array around using Python’s itertools module, while the helper functions defined on top calculate the total distance of each tour. Although this probably the simplest way to solve this problem, it is also the least effective way. Let’s investigate why. As seen above, for 3 cities B,C,D (minus the first city A because it cannot change position), we can calculate the amount of possible combinations like this:

3 x 2 x 1 or 3! = 6

Ok, but what if an Amazon delivery truck has to visit 100 addresses per day? How many possible tours will we have to check before we know which one is the shortest tour? Let’s checkÒBut what if an Amazon delivery truck has to visit 100 addresses per day? How many possible tours will we have to check to find the shortest tour? Let’s check:

100 x 99 x 98 x 97 x...1 or 100! = 9332621544394415268169923885626670049071596826438162146859296389521759999322991560894146397615651828625369792082722375825118521091686 400000000000000000000000

Oh gawd. A running time of n! is not a good idea. Do we have any alternatives? So we know that the tour that we found is exactly the shortest one because we calculated it. However, for the sake of speed, it might not always be necessary to find the shortest tour but rather a tour that is close to the shortest tour. There are exact algorithms that perform better than our brute force approach, but let’s also look at an approximation that will find a, but not necessarily the shortest tour: The nearest neighbor algorithm does pretty much exactly what you think it would do. For each city, it will simply find it's the nearest neighbor and stitch them together to create a tour.

#Helper function to return nearest neighbor of one point
def find_nn(p, unvisited):
	return min(unvisited, key = lambda x: dist(x , p))

#TSP nearest neighbor main function
def tsp_nn(points, startPoint):
	visited = [startPoint]
	unvisited = points
	unvisited.remove(startPoint)
	totalDist = 0

	while(len(unvisited) >= 1):
		nn = find_nn(visited[-1], unvisited)
		unvisited.remove(nn)
		visited.append(nn)
	return visited

This approach is dramatically faster than going through n! combinations: If we benchmark both algorithms we find that for 9 cities, tsp_brute() will take 2.7 seconds and tsp_nn() will take only 0.00045 seconds to run! Here's the full Github Repo for all spatial algorithms that I explored so far. Cheers!