Background on the Traveling Salesperson Problem

Mathematical classification

This course is designed to be as practical as possible, so mathematical details are explained only as necessary. However, it’s useful to classify the problem mathematically at the beginning for a better understanding.

The task is to find the shortest overall route between different destinations: the salesperson visits several stores in succession and returns to the starting point by covering the shortest overall distance.

In the context of TSP, the total distance traveled must be reduced as much as possible. That is the cost function, which we want to optimize as much as possible. Although the explanation is simple, this problem is quite complex. Let’s calculate the distance between all 13 stores from A to M and place them in a distance matrix.

We can see how it quickly becomes complicated to calculate the shortest total distance because there’s no general formula for this combinatorial optimization problem. Instead, we have to calculate it for all possible combinations to get the exact value. As the number of stores increases, the number of possible combinations increases exponentially. For example, if there are three stores (A, B, and C), there are six possible routes (A to B to C, A to C to B, B to A to C, B to C to A, C to A to B, and C to B to A). The salesperson returns to the starting point at the end. Therefore, the sequence StoreA to StoreB to StoreC is the same route as from StoreB to StoreC to StoreA. Therefore, with three locations, there are only two different route lengths. One is the route from StoreA to StoreB to StoreC, and the other is StoreA to StoreC to StoreB. The other possible routes differ in the routing, but the length of the route doesn’t differ.

As we’ve already seen in the previous lesson, with five ...