Jump into the car for the road trip of a lifetime! (part 2)

[#1]

In an earlier post, I laid out my plans for creating a road trip map across all the major US Highways. I discussed how I set up the network and the algorithm I used to find the path. In this post, I’ll show you the resulting paths I found and how I narrowed in on my ultimate road trip.

Before making my first run of the search algorithm, I made a quick summary of my network to see if there were any additional constraints I could add to help find a path. Turns out, there were a few:

• Hwy 3 only intersects two other highways: Hwy 2 and Hwy 4. This meant that either the sequence 2-3-4 or 4-3-2 would be a fixed part of the path.
• Hwy 48 also only intersects two other highways: Hwy 33 and Hwy 11. This meant that either the sequence 33-48-11 or 11-48-33 would be a fixed part of the path.
• Hwy 57 technically only connects with one other highway: Hwy 83. Its terminuses are at the Mexican border and I-35 toward San Antonio. However, it was pretty close to Hwy 90, so it was very tempting to let it connect to that one. But, rules are rules, right? … Say, isn’t that John Sall over there?! Yeah, over there!... It’s not?... You sure?... Man, I could’ve sworn it was him. Anyway, as I was saying, Hwy 57 connects to only Hwys 83 and 90 so that meant either the sequence 83-57-90 or 90-57-83 would be a fixed part of the path.
• Finally, Hwy 46 only connects to two other highways: Hwy 1 and Hwy 9. However, this is an interesting case as these “two” intersections are actually just one intersection. You see, where this intersection takes place (in Palisades Park, NJ), Hwy 1 and Hwy 9 run concurrent with one another. So this meant that either one of 1-46, 9-46, 46-9, or 46-1 would be a fixed point on the path. Furthermore, this also meant that the path would either start or end with Hwy 46.

Round 1: Search!

After carefully putting these constraints into my algorithm, I decided to start the path with Hwy 46 and run the algorithm. There were a few highways left out, so I used Method 1 of the Filling the Gap methods to fit them back in (the “graft and retry” approach). After three retries …success!! Figure 1 shows the raw output of this first attempt.

Figure 1: Raw output of first attemptThis was a bit too clunky for my taste, so I went in and, with some friendly assistance from Google Maps, filled in some of the lines with extra points to add a bit more curvature and follow the actual route more closely. I also added in a Marker Type column to my data, which I could use to identify major cities and landmarks along my path. To keep from crowding the graph with too many markers, I copied the Latitude column, deleted the values in that column that were not associated with a major city or landmark, and then made the points use that column as its “Y-axis” (you can do this by selecting the Variables arrow under the appropriate group in JMP Graph Builder). By the way, the background maps I’m using here are Street Map view with the US states imposed (the border lines are set to a slightly darker grey than the default).

After this bit of tidying up, I get the path shown in Figure 2.

Figure 2: Cleaned version of first attempt

I can imagine some of your responses to this map being among the following:

• Gaaaahhhh!! What is that?! It’s hideous!! It looks like someone gave a 2-year-old a fine tip marker and a map of the USA on which to draw.
• So I can just make out where you start and where you end, but how on earth do you get there? I thought the Spaghetti Intersection in Atlanta, GA, was bad….
• Hey, you completely missed my state!! (from residents of California, Arizona, Rhode Island and Maine).
• What’s with the trip through Canada? (This one’s easy. Fun fact: Hwy 2 is split into an eastern and western portion by design! To traverse all of it, a detour into Canada is required. No complaints here!).

OK, OK, so I admit there are quite a few issues with that first attempt. The most notable for me was the fact that it missed several states completely, which certainly would not do for a road trip across the country (sorry, Alaska and Hawaii; I hope you understand). So why were these states being left out? Well, to answer that question, I did what I should have done in the first place: plot the network!!

Figure 3 shows the highway network I compiled as described in the previous post.

Figure 3: The highway intersection network visualized

 From this figure, we can clearly see why those states were missed.

• There are no intersections in California, only ends or beginnings (there’s a profound statement there somewhere).
• There is only one intersection in Maine, which happens to be between Hwys 1 and 2 in Houlton. This intersection could have easily been passed over in the path search.
• There are only two intersections in Arizona; Hwys 60 and 95 (left) and Hwys 60 and 70 (right). Same reasoning as the previous point.
• There is only one intersection in Rhode Island: Hwys 6 and 44.

Round 2: The Highly Anticipated Sequel!

With the information gleaned from Figure 3 in hand, it was time to add in a few more constraints to ensure that every state was visited and sufficiently so.

• In order to ensure California is visited, I decided to have the path start with Hwy 101, which extends along nearly the entire coast of the state starting in Los Angeles. The path would still need to end with Hwy 46.
• There are four connection options for the next highway after Hwy 101. I initially chose to start with Hwy 26 as this option takes you through Portland and by Mt. Hood.
• I extended the 4-3-2 fixed point to now include Hwy 1. This forces Maine to be part of the path, although it no longer allows for extended travel on Hwy 2 (sorry, Canada).
• I added a fixed point of 60-70 and 93-95 to the path, which would ultimately result in the chain 93-95-60-70 or vice versa being part of the path due to the nature of the algorithm. This forces Arizona to be part of the path and has the added bonus of making Las Vegas a part as well. You’re welcome.
• I also decided to add Hwy 52 to the 83-57-90 chain since Hwys 52 and 83 intersect in Minot, ND. This allowed for greater coverage of North Dakota. All states should share the love.

With these new constraints added, I re-ran the algorithm and had only one highway left out. So I used Method 2 of the Fill the Gap methods to add it back in (the “try every option” method). After some cleaning, this resulted in the map shown in Figure 4.

Figure 4: The second attempt at a road tripWell, at least every state has some coverage now, though it is still a bit messy. One thing I still wasn’t too keen on with this trip is the loop there in Wyoming. It turns out that Hwys 87 and 85 run pretty much concurrently with I-25 from Denver down, which is why they show up the way they do here. Also, it looks like Washington state gets hardly any coverage, as does Vermont. So I added a few more constraints (including switching to a Hwy 101 – Hwy 12 start) and got the path shown in Figure 5.

Figure 5: Yet another attempt at a road tripLooking a bit better now. Still a lot of overlapping with some parts of the path, but not as bad as the round 2 version, in my opinion.

So it seems I was able to address the “missing states” problem with these last two paths. However, there is still quite a bit of craziness going on in the layout. It feels like this post has run its course, so in the next one, I’ll discuss some adjustments I made to try and clean up the path further and show my final path.

[Milo]

Nice job! I'm curious what the total mileage is for the various routes. Do you have an easy way to calculate that? 

[calking]

I have the way I did it...though I can guarantee it wasn't very easy. Essentially, as I was filling out some of the path, I calculated both the driving time and distance using Google Maps. I had two other columns that would then keep track of the cumulative time and distance. It was rather painstaking as I had to make sure the route followed the highway, which was made more difficult when it followed next to an interstate as Google kept insisting on taking that interstate. In the end, I did calculate the total distance for the round 2 map and got close on the round 3 map and they were both on the order of 36,000 miles (roughly 650 hrs of driving time). 

I imagine you could approximate the total distance by taking the Euclidean (as the crow flies) distance between stops. You'd obviously miss out on some of the details of certain roads, but I'm sure it would be close enough for practical use. There are ways to do that using SAS, but I'm not sure how to do that in JMP just yet.