Tackling the travelling salesman problem: prologue

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):

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.

5 thoughts on “Tackling the travelling salesman problem: prologue

  1. Great start John, I’m interested to see where you go with this.

    It’ll be neat to see your Python code too, you’ll obviously be combining expressibility and functionality in a reasonably optimum number of lines.

    Are you thinking of doing any real-simple-GUI output too?

    Ian.

  2. I think I’ll start off with just same basic image output using PIL, rather than get way-laid with a GUI for now. Might create a simple HTML report too, so you can browse through the various solutions found.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>