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.