Shortest Overall Distance

We’ve been working toward the solution to TSP by completing all the preparations and can finally come to our traveling salesperson’s rescue.

TSP is about reducing the cost function as much as possible. Simply put, it’s about keeping the total distance traveled on the closed route as small as possible. It’s what is called a combinatorial optimization problem. It’s NP-hard, meaning that finding an optimal solution for large problem instances is computationally challenging. Consequently, many heuristicsHeuristics for TSP are designed to quickly find a reasonably good solution that is close to the optimal solution, without necessarily finding the optimal solution itself. Heuristics work by exploring the search space of possible solutions in an intelligent and efficient manner, using techniques such as local search, greedy algorithms, and randomized algorithms. have been developed to find near-optimal solutions in a reasonable amount of time.

Solving TSP

For a brief recap, view the distance matrixA distance matrix is a matrix that represents the distances between a set of objects. The matrix contains the pairwise distances between every pair of objects in the set. for all stores.

How do we find the overall shortest route out of all the distances?

NP-hard problem

TSP is an NP-hard problem, but this doesn’t mean an instance of the problem will be hard to solve. It means that there exists no single algorithm that produces the best solution in polynomial time. In simple words, when there are a lot of places to visit in TSP, it’s not practical to check every possible route to find the shortest one. It would take too much time and computer power.

But what we can do is calculate the number of different possibilities. With a small number of stores, we can apply brute force to get the optimum solution. In the end, it’s just a matter of RAM and time. If you try to solve TSP with your personal computer, you might encounter this message more than once:

As a rule of thumb, it can be said that beyond nine locations, the number of combinations increases exponentially. We’ll go over this in the Brute Force lesson.

As the number of stores increases, the number of possible ...