-
Escaping the Cold & Bees
February 18, 2023 It’s 6AM and it’s 28 degrees. This isn’t cool, ok, it’s cold, but not cool. You see, water freezes at 32 and our water pipes could freeze. There are two options at this point: 1) pull the covers up over my head and go back to sleep and wait until Susan gets up to make coffee, 2) get up and see if things are broken. You see, if she can make coffee, things aren’t broken. Susan made coffee. Yay! I had left the water hose hooked up over night just since I didn’t want to put it away. Fortunately, it was an expandable one and it didn’t…
-
Phoenix & Back – 2023 – Days 1 & 2
February 17, 2023 We left our house around 7:45 AM, on February 16th, 2023. Destination, Phoenix AZ. Temperature was below freezing the night before so I didn’t fill the water tanks until that morning. The goal was to make it to Bear DE, we had reservations at Lums Pond State Park. We had hoped to get there around 4pm, especially to visit with my brother who could come down from Philadelphia for dinner. Of course I had neglected to tell him this. LOL. He wasn’t able to make it and it was a good thing he didn’t. We had bad traffic in spots and didn’t get there until dark, about…
-
Shortest Path
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…
-
Second Solution, First Failure
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…
-
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…
-
A Genetic Diversion
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…
-
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…
-
The Traveling Salesperson Problem
The Traveling Salesperson Problem, aka TSP, is a classic problem in Computer Science. In it, the traveler wants to visit all the cities on their route and travel the least amount of distance. To quote Wikipedia, It is an NP-hard problem in combinatorial optimization, important in theoretical computer science and operations research. The important part to note here is “NP-hard,” which means “If P ≠ NP, then NP-hard problems cannot be solved in polynomial time.“ And Britanica says “This is an example of an NP-complete problem (from nonpolynomial), for which no known efficient (i.e., polynomial time) algorithm exists.“ NP-hard and NP-Complete are classes of Computer Science problems that have been…
-
First Route By Hand
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…
-
Messing About With a Route
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…