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 solving this sort of problem and better yet, since the TSP is a classic computer science problem, there was sample code for it. I’m taking about Google’s OR-Tools.
OR-Tools is an open source software suite for optimization, tuned for tackling the world’s toughest problems in vehicle routing, flows, integer and linear programming, and constraint programming.
I quickly plugged my data into their sample code, ran it, and it pretty much instantly told me the solution. But, it was something like 1 -> 4 -> 13, giving me the path based upon the indices of the bridges. It was a quick bit of programming to print out both the names and the coordinates so I could plot them. Of course, I’ve uploaded cb-or.py to GitHub. But I know what you want to see. And there you have it. The path!
Am I done? No, you need to know the list of bridges, in order!
- Ashuelot Bridge, Winchester
- Coombs Bridge, Winchester,
- Slate Bridge, Swanzey
- Denman Thompson Bridge, Swanzey
- Sawyer’s Crossing, Swanzey
- Carleton Bridge, Swanzey
- County Bridge, Hancock
- Heniker Bridge, Heniker
- Rowell’s Bridge, Hopkinton
- Railroad Bridge, Hopkinton
- Dalton Bridge, Warner
- Waterloo Bridge, Warner
- Bement Bridge, Bradford
- Cilleyville Bridge, Andover
- Keniston Bridge, Andover
- Sulphite Bridge, Franklin
- Smith Bridge, Plymouth
- Blair Bridge, Campton
- Turkey Jim’s Bridge, Campton
- Bump Bridge, Campton
- Squam Bridge, Ashland
- Durgin Bridge, Sandwich
- Whittier Bridge, Ossipee
- Albany Bridge, Albany
- Saco River Bridge
- Swift River Bridge
- Bartlett Bridge, Bartlett
- Honeymoon Bridge, Jackson
- Stark Bridge, Stark
- Groveton Bridge, Northumberland
- Columbia Bridge, Columbia
- Pittsburg-Clarksville Bridge, Pittsburg
- Happy Corner Bridge, Pittsburg
- River Road Bridge, Pittsburg
- Mechanic Street Bridge, Lancaster
- Mt.Orne Bridge, Lancaster
- Sentinel Pine Bridge, Lincoln
- Clark’s Bridge, North Woodstock
- Swiftwater Bridge, Bath
- Bath Bridge, Bath
- Bath-Haverhill Bridge, Bath
- Edgell Bridge, Lyme
- Packard Hill Bridge, Lebanon
- Meriden Bridge, Plainfield
- Blow-Me-Down Bridge, Cornish
- Cornish-Windsor Bridge, Cornish
- Dingleton Hill Bridge, Cornish
- Blacksmith Shop Bridge, Cornish
- Wright’s Bridge, Newport
- Pier Bridge, Newport
- Corbin Bridge, Newport
- Mcdermott Bridge, Langdon
- Prentiss Bridge, Langdon
Am I done?
No…
There’s still the trip planning but also, the disturbing part. I don’t know if this is correct.
You see, this route is 1,018,296 meters, or 632.7 miles. And remember the wrong solution from python-mip, it was 961,591 meters, or 597.5 miles. That’s a really big difference. Both are less than the “by hand” version of 676 miles. But wow.
And I’m not sure how to proceed from here. The map looks good, it looks believable. But there’s a potential 35 mile gap. I need to look into this some more.