Traveling Salesman Problem Algorithm

I'd suggest fullscreen.

A genetic algorithm based traveling salesman problem project I implemented recently inspired me to explore an idea I had in the 90s to solve a particular version of the problem: where travel cost is proportional to distance. In the real world, this is often not the case, but in some applications it is, such as PC board drilling. It works like this: create an initial tour with only just enough cities to form a convex hull around the remaining ones, then use a greedy algorithm to add interior cities one at a time. Since this can lead to loops, I then run a de-looping routine on it. Correcting the loops turns out to be faster and better than preventing loops during the greedy process itself as well as being simpler. The video of the process has been slowed down about a thousand times.

It performs about 2% worse than my genetic algorithm based solution, but also about 2% better than a standard greedy algorithm followed by a de-looping routine, and could be made considerably faster than a GA based one for larger problems. The test version I did was written quickly with little attention to performance, but could be improved fairly easily. Doubt I would need such a thing, but it feels good to have finally tried it.