Yes, we are here! I have a shortest path between the 53 covered bridges in New Hampshire. (And if you’re just join now, yes, I know there are 54 bridges, it just that two of them share the same parking coordinates.) How did I find it? I reset to square one. I don’t have the computer science chops to understand why the pthon-mip solution wasn’t working for me, so I googled. And yes, I started off googling. But this time I hit something new. I don’t know if I missed it before or if it is new code, but I found a new open source package that would perfect for…

Wow, it’s been awhile since I posted, which was on January 26th. That’s because I don’t like failure and failure was where I wound up. But let’s back up a bit. I was referred to Developing Customized Branch-&-Cut algorithms on the python-mip site. So I went back there and grabbed their sample code showing a Branch and Cut solution. When reading over the program I noticed that it was not using a triangular matrix, but a rectangular one. This is because the distance from A to B might not be the same as the distance from B to A! You can have one way streets or bridges, or whatever. And…

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…

In the previous blog I mentioned that I had settled on some open source python, python-mip, to generate my route. It had code like this: distances in an upper triangular matrix dists = [[83, 81, 113, 52, 42, 73, 44, 23, 91, 105, 90, 124, 57], This is an array of data that represents the distance between all the destinations. I needed to make the same list but for my bridges. In Computing the optimal road trip across the U.S, Randal S. Olson has given us code to do that. So I installed the various python packages, got my google maps API Key, and ran the program. It failed. The…

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…

Before diving into computer approaches, I’d thought I’d do it old-school, by hand. Well, as old school as Google Maps is. Google Maps only lets you put in 10 destinations so I’ll break the trip up into section. This works out fairly well since the bridges mostly occur in clusters. I’ll start at Bridge #1, the Ashuelot Bridge in Winchester NH. Why this one? There are many reasons. First, it is number 1, how can I not start there. It is also the southernmost bridge, so it is a good candidate for being correctly placed when we get the real route done. But most importantly, I have a picture of…

The map from the previous post showed some nice clusters of bridges. I shouldn’t have been surprised, early one I posted an tiny, ancient, map that showed the bridges but the clusters were pretty hard to see. One I had the google maps up though they were easy to see. I’ve circled them on this image and then drew a rough route around them. This show what the approximate path will likely be. Lets drop those cities in google maps and make a quick and dirty route. Winchester, Concord, Plymouth, Conway, Lancaster, Pittsburg, Lincoln, Bath, Lebanon and Winchester to close the loop. Lets digress a moment though before, why a…

If you’re not into data, like I am, you might be wondering why I spent hours making that CSV file. That’s a reasonable question. The thing is, once you have your data all nice and pretty, then you never ever have to type it in again and, better still, you can do all sorts of things with it. I wanted to put up a map showing all the bridges. So I went to google maps, hit the “hamburger menu” in the upper right and selected Your Places. And yes, that really is called a hamburger menu. It is made up of three slices, 2 buns and the protein. And no,…

If you live in New England, you’ve seen one, the iconic covered bridge. They were built for practical reasons, an uncovered wooden bridge has a lifespan of about 20 years, a covered bridge can last for 100. I guess there were over 100,000 at the peak in the United States but now there are only about 750. [citation needed] But one cannot deny the charm of a rustic covered bridge over a quiet stream or a roaring waterfall. So are there only 54 in New Hampshire? There are many lists about, but many are on private property and many aren’t historic, that’s when we just decide to trust the government!…