The Travelling Salesperson Problem is a famous problem in computer science. The gist of it is as follows:

“Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city and returns to the origin city?” It is an NP-hard problem in combinatorial optimization, important in operations research and theoretical computer science.

Wikipedia

To attempt to solve this problem and visualize the progress, I turned to Processing’s excellent P5xjs and the equally amazing Genetic Algorithm tutorials by Dan Shiffman. My approach began as a brute force method and has been built up to its current state of using a genetic algorithm.

You can see the code in action here: sspboyd.ca/tsp/

How does the algorithm work?

The algorithm works by running 2000 test routes at a time and finding the shortest route of the bunch. This shortest route becomes the basis for the next generation of 2000 routes where each new test route makes tiny changes to the current best route from the previous generation. And then process continues.

Early Prototype

So how do we know when it is done? How do we know it’s found the optimal route???

We don’t.

That’s one of drawbacks of this method. We can look at the route and use a quick eye test if there aren’t too many cities, but once the number of cities gets much past 50, it is really hard to just look and see. It is a fascinating example of how human perception works vs computer algorithm but that is whole other topic to discuss some other time!

The Code

There is a lot still to be done with this algorithm and visualization. I’ll update this post as changes and improvements are made.

In the meantime, feel free to checkout the code on GitHub. There are several branches each showing a different algorithm for trying to solve the puzzle.

Thanks!

I’d love to hear from you if you find this interesting or have suggestions or questions. There are a bunch of ways to reach me, or use any of the social links included on the site.

Thanks for coming by!