The Travelling Salesman Problem (TSP) is a classic combinatorial optimisation problem. It also happens to be a problem I have spent various parts of my life looking at.
At my first job out of uni we worked on solving real-world problems that usually involved the TSP in some fashion. Often the problems we tackled were, in effect, the TSP with extra constraints or variants along those lines. A straightforward example being having multiple "salesman" and trying to assign each one a route (that didn't overlap). The approach in that first job was mainly to use evolutionary algorithms.
Then during my MSc I took the course Nature Inspired Optimisation. This was by far my favourite course during my MSc and saw us applying different optimisation algorithms to several different problems. Kennon and myself were assigned the TSP to work on and had a lot of fun implementing various different algorithms to tackle it.
Anyway, I thought it would be interesting to give a brief guided tour of the different algorithms we used during the MSc to tackle the travelling salesman problem. I'm no expert, but I do have a fair bit of experience with this problem and there are some fairly straightforward algorithms out there, which are good to have in your arsenal.
So my intention for this series is to cover (over the next weeks/months/however long):
- Defining the Travelling Salesman Problem (and writing shared utility code)
- Hill-climbing (the simplest approach)
- Simulated annealing
- Evolutionary algorithms
That's the bare minimum for now. I may well cover a few more algorithms (e.g. ant algorithms), but those three algorithms provide quite a good starting point.
I will be writing everything from scratch, as I go, in Python. In general I'll be aiming for clarity of code - rather than pure speed and Python should work well for that purpose.