First Attempt at a Solution
And yes, a capital S solution. I need to make the triangular matrix that I talked about last time. This was kind of fun. I’m not a big python user so I took this opportunity to turn out some code I would reject if it crossed my desk at work. But, it’s only a blog and it runs! You can see triangle.py at GitHub.
This is heavily based on the Olsen code but there are a few things to note. The first is that the all_waypoints variable is an array of lat/long and human readable names. This way I don’t have to see 42.777500, -72.423222 but instead I see Ashuelot Bridge, Winchester.
Olsen uses the python combinations function. This is great since for his purposes all he needs is all the combinations. I need an array, which has order, it’s an array, not a set. There is an array of distances, that’s the triangle, and an array of places.
I spent about an hour thinking how I could take this unordered combination and making it into an array. This is a classic XY Problem. I didn’t need to do that, my real problem was that I needed a triangular matrix. Right then the solution was clear, nested for loops! So I wrote code like:
for num, waypointPair1 in enumerate(all_waypoints, start=1):
for num2, waypointPair2 in enumerate(all_waypoints, start=1):
Easy, right? But later I needed to run the loop again. So I have this code:
for num3, waypointPair1 in enumerate(all_waypoints, start=1):
I’m sorry, that’s crap. num, num2, num3? I had to do that because python appears to be a loosely scoped language. I really don’t know, so don’t quote me. But I had an error in my second loop, I was referencing num2 before it had been declared. The debugger showed a value for it. That should have been out of scope. So I gave all four variables crap names. This is programming, not engineering I guess.
I ran it and got my triangle matrix and my places array and then I was off to the races with python-mip! You can see the cb53-mip.py file on GitHub. Yeah, 53. You see, I’m using the parking coordinates, not the bridge coordinates. And Flume and Sentinel share a parking lot.
So I ran it, and waited and waited.
Cbc0010I After 23,900,784 nodes, 27,365 on tree, 1,090,945 best solution, best possible 821551.36 (221,753.65 seconds)
That’s more than 61 hours of run time! And the solution, 1,090,945 meters, is almost 678 miles. I had, what, 643 miles by hand? That’s even worse than the genetic algorithm.
I have an answer thanks to Wit Jakuczu on the python-mip mailing list.
Check code from this section – https://docs.python-mip.com/en/latest/custom.html MIP is not the best approach to TSP problem but lazy constraints and initial solutions and cuts help a lot.
So that’s where I’m going next.