TSP 2-opt algorithm: A path through 10000 cities

The Traveling Salesman Problem (TSP) is a classic, but notorious problem to solve. The idea behind the TSP is that you want to visit a number of locations, but you can only visit each location once. The more locations you have the more difficult it becomes to solve the problem. For example if you want to find the shortest path through 1000 cities you would have to try 1000!/2 combinations = undefined according to Google. And if the number is too big for google to figure out, you know it's big!

One way to solve the TSP problem is to use an Genetic Algorithm (GA), another way (or in combination with a GA) to solve the TSP problem is to use the 2-opt optimization algorithm (https://en.wikipedia.org/wiki/2-opt). The basic idea behind 2-opt is that you just test two pair of edges, and swap the connection if the path becomes shorter (hence the term "Swaps" in the video). You also need to reverse the path between the swaps.

We saw in an earlier video that the 2-opt is faster than the GA to find a short path through 1000 cities. In this video you can see how the 2-opt algorithm is finding a short, valid path through 10000 cities. You can see that the path is valid because no lines are crossing each other. If two lines are crossing you know there's a shorter path somewhere. It took roughly an hour to generate the solution, but I've sped up the video so you don't have to fall asleep!

I made this visualization in Unity using C# programming language. It is not open source yet but may be so in the future.

Follow me on Twitter: https://twitter.com/eriknordeus

#madewithunity #travelingsalesmanproblem #tsp #unity3d #2opt