Let’s Find Some Code
There is a lot of code out there for solving a Traveling Salesperson Problem, aka TSP. It is of great interest to computer scientists all over the world. I was looking for something that satisfied several constraints:
- It must be free. Both from a cost standpoint but also from an Open Source standpoint. Doillar free because I’m cheap. :- ) But I also want this to be generally available, because, well, why not?
- I wanted it to be in a language that I was familiar with but also provided a learning opportunity. Python was my first choice. C and C++ solutions weren’t as interesting to me, just like specialized languages weren’t that interesting.
- I wanted a provable optimal solution, not a best effort. This was challenging to find because the problem is so interesting that many researches have code that implements a non-optimal, but interesting, approach. This is a direct result of the problem being interesting to Computer Scientists! There is such cool stuff, like Genetic Algorithms, or Ant Colonies. See 11 Animated Algorithms for the Traveling Salesman Problem for a quick overview of 11 ways to solve the TSP.
- I wanted it to run without too much effort, I didn’t want buggy code. I actually downloaded very little code. Here’s a hint to open source developers. A ReadMe and some examples go a long way to making me care about your project.
These constraints eliminated Concorde, which is a real shame, since William Cook’s web site is a treasure trove of information about TSP, Held-Karp, and Dantzig, Fulkerson and Johnson’s solutions. But, the code is in C and not open sourced. I’m 99.999% certain I be allowed to use it, since my usage here is clearly academic, but I just didn’t want to go down that path. But still, go to that site.
If you go to GitHub.com, searching for TSP, you’ll find a million links to code. I got to see code that was poorly documented, code that written at NASA, code that’s written in computer languages I don’t understand, and code that was written in cultural languages I don’t understand.
But I eventually found a package that I’m pretty certain will work. python-mip. It is in Python, it is open sourced, the examples run, and more importantly, one of the examples is the TSP!
The one weird thing that I found is that their example isn’t as well documented as one would hope for. For example, we have this code.
# names of places to visit places = ['Antwerp', 'Bruges', 'C-Mine', 'Dinant', 'Ghent', 'Grand-Place de Bruxelles', 'Hasselt', 'Leuven', 'Mechelen', 'Mons', 'Montagne de Bueren', 'Namur', 'Remouchamps', 'Waterloo']
and this matrix:
# distances in an upper triangular matrix
dists = [[83, 81, 113, 52, 42, 73, 44, 23, 91, 105, 90, 124, 57],
One would guess that these are distances between Antwerp and Bruges and then Antwerp and C-Mine but if you go to google maps they’re not. But… they are close. I think that they didn’t use Google Maps for their distance calculation. You see, one could be asking for shortest time, shortest distance, shortest distance walking etc… And it also depends on current road conditions! The first time I tried this I got 89km between Antwerp and Bruges, it is 109km today, because the bridge on the E34 Zeekanaal Gent-Terneuzen, Belgium is closed right now. And hey, they got the bridge on the R4 is open now.
But this code runs and it is the code I’ll use.
Next up, getting the data.