It has been a while since I’ve programmed in Python. I want to refresh my knowledge of the programming language while also answering a question that I have: What is the shortest route to all of the US National Parks? Answering this question will help me efficiently accomplish my dream of visiting all of the National Parks in the United States.
Okay, so, how to begin? Well we’ve already asked a question, but we need a few things to get started:
- List of National Parks in the US and their location
- Ability to measure distance between two places
- Algorithm to find the shortest distance as we travel from place to place
With a quick little Google search I found the Wikipedia page for the areas in the United States National Park System. It seems the National Park Service (NPS) is in charge of much more than just the National Parks! There are currently 421 ‘units’ that the NPS is responsible for, including National Monuments, Preserves, and Historic Sites. For now, let’s keep my dream realistic and only try to visit all 61 National Parks. Maybe later we can find efficient paths to other places and even see if we can add some stops along the way.
Unfortunately with all it’s collective wisdom, Wikipedia does not have GPS coordinates associated with the list of national parks, but latlong.net does! LatLong is missing a few national parks. To get started we will just use the 50 that are provided and find the missing 11 later. The data is in a semi-friendly table format, so I was able to copy/paste it into Google Sheets and then ‘Download as…” a CSV file. Now that we have our raw data that we can play with in Python: Step 1 complete!
Now we want to measure the distance between two places. Since we are on earth, the shortest distance between two places is not a straight line (unless you have a tunnel boring machine, which we don’t). So unless Elon Musk wants to donate his TBM, we will be constrained to traverse the surface of the earth to visit the National Parks. Take out your tinfoil hats because the earth is not round… well not perfectly round at least. In fact it is an oblate-spheroid, a shape that you can create if you press a soft orange down onto a tabletop. In order to measure distances accurately upon the earth’s oblate spherical surface, one must be an Earth Scientist with a concentration in geodesy; just kidding, there is a Python library called geopy that can do the math for us.
The final step is to develop an algorithm to find a shortest route as we travel from place to place. In fact, there is a name for this type of problem already: The Traveling Salesman Problem. A simple, but not optimal, way to solve the problem is to start at one point and then search for the nearest point. The result of the search will be the next location we visit. We do this search and visit routine until we have visited every location. This Nearest Neighbor approach may not yield the shortest overall route however. If we use the houses on the road in Figure 1 as an example we find that nearest neighbor is not the best approach when starting at house A. Nearest Neighbor would go A→B→C→D resulting in a total distance of 3+5+13 = 21km. The optimal path would visit D before going to B. The path being A→D→B→C with a total distance of 5+8+5 = 18km.
Even though Nearest Neighbor may not get us the overall shortest path, it is easy to implement. We will start with a list of National Parks and their coordinates, in no particular order, and choose a random starting point. We must remember to remove the starting point and each place we visit along the way from the list. If we don’t do this, we will end up in an infinite loop where we just keep visiting the place we are already at (it is the nearest after-all). As we visit places, we will record them into a linked list along with the distance to the next place. At the end, we can print out this linked list and it will be our shortest route!
*Waving Magic Programming Wand*…Release 1.0.0 of NPS_Coords on GitHub.
Aaaand we have a solution! Here is a CSV of the output, starting with Jackson Hole WY. Quite honestly, this output is pretty boring, but we will have to wait until the next blog post to really spice things up with some maps!
Future Ideas:
- Mapping the route
- Finding the best starting point
- Optimizing shortest route (trying other TSP algorithms)
- Using the Google Maps API to find shortest distance via roads.
- Heat maps to visualize common routes between all possible starting points.
- Mapping other types of locations, especially planetary bodies.