Planning the Perfect Hike with NetworkX and OpenStreetMap
How to build an open-source hike-planning app and route optimization engine
Any avid hiker will tell you that the key to a good experience on the trail is adequate preparation. Should I pack rain gear? How long will I have to walk between water sources? What is the best shelter for the terrain and season?
The most important question is also the simplest – where am I going to go?
Guidebooks provide useful information about the key attractions in a particular park or region, but the details can be outdated or difficult to adapt to your preferences. Apps like AllTrails have revolutionized hike planning by crowdsourcing popular routes, photos, and reviews. However, many of their "Premium" features, like the ability to print maps or download them for offline use, require a paid subscription. Further, by distilling a complex trail system into a few curated hikes, I often feel limited by the options listed in AllTrails’ search results.
Thus, I set out to build my own open-source hike-planning app and route optimization engine that supplement the functionality of proprietary sites. In this article, I’ll walk through (pun intended) the independent components of the system and show how they come together in a demo. Just want to see the code? Check out the repository here.
Data Sources
When it comes to free datasets for route planning, OpenStreetMap is the clear choice. In fact, even AllTrails adapts their global trail database from OSM’s Overpass API, filtering for only the walkable way segments.
One of the pain points of working with geospatial data is that it comes in a wide range of file formats, each with their own strengths and weaknesses. In this project, I used different data structures for storage, visualization, and analysis of the trail maps.
For the route planning task, a graph-based representation makes sense; trails, like roads, are made up of nodes (intersections) and edges (path segments). This allows us to leverage graph algorithms like Djikstra’s algorithm in our route optimization function.
My strategy for this particular component of the app is nothing new, as there is already a broad ecosystem of tutorials and libraries dedicated to graph-based way planning. Tools like OSMnx provide a high-level interface to query the OSM dataset by geocode (e.g. "Shenandoah National Park, Virginia, USA") and convert the response into NetworkX graphs. Below is the load_map function that I use to download trail data and save the geometric information in graph- (for efficient computation) and GeoJSON-based (visualization) formats.
However, a unique aspect of planning hiking routes is that in addition to latitude and longitude, elevation is a critical third dimension to the design space. Like any good trail map, our tool should be keenly aware of topographic features.
My custom elevation API uses high resolution radar data collected in 2000 by the Space Shuttle Endeavor. For about 18GB of hard drive space, the SRTM GL3 dataset covers nearly 120M square kilometers of Earth’s landmass in 90m increments. Using the rasterio library, we can extract elevation profiles from path segments without loading the full map into memory:
Not bad, right? It is interesting to note that Google currently charges $5 per 1000 requests to their Elevation API, but thanks to NASA and a few lines of code, we can get the same high-quality results, free of charge.
Application and UI
Dash is my preferred framework for building interactive dashboards in Python. By abstracting the frontend into customizable components, it allows data scientists to focus on the functionality of their use case, rather than design. Since there are already dozens of excellent Dash tutorials and examples, I’ll focus on the layout and logic of my specific application.
As you might expect, the UI is focused on the map, which utilizes Mapbox’s topographic tileset. A dropdown allows you to select from cached trail systems, or you can download new ones by geocode.
Once a region is selected, the OSM trail network is visualized using the dash-leaflet library. As your planned route materializes on the 2-dimensional map (more on this in the next section), the accompanying elevation profile is plotted in real-time.
Route Planning Engine
My app allows the user to plan their hike using one of two "modes". In "Custom" mode, you simply click on intersections around the map and see your route come to life, one segment at a time. Behind the scenes, we try to intelligently connect points using a shortest path algorithm. In the following animation, we see a user-defined route taking shape in Cuyahoga National Park.
The auto mode is a bit more interesting. My goal here was to create a constrained optimization function that considers the main factors I’d look for when planning a loop:
- Elevation gain
- Distance
- Traversing as much unique trail as possible (i.e. minimize the amount of backtracking on the same paths at multiple points in the hike)
Mathematically, the optimal loop will satisfy the following:
Where P is the path, d(P) is the path distance, D is the target distance, r(P) is the fraction of traversed nodes that are unique (e.g. an out-and-back would have an r-value of 0.5), e(P) is the elevation gain of the path, and E is the target elevation gain.
Traversing a cyclic graph to find available loops is also a non-trivial task. In the end, I opted for an approach that combines shortest paths and simple cycles, which are paths that do not contain any repeat nodes.
Clicking the map near a trail intersection defines the root node for the find_best_loop function, i.e. the terminus of the loop. This enables users to automatically generate hikes that start and end at a key location, like a parking lot or trailhead. Below, the algorithm suggests a rigorous trek over Old Rag Mountain in Shenandoah National Park to meet the supplied constraints.
An interesting aside about calculating cumulative elevation gain – surprisingly, there is no clear mathematical definition. You can imagine that if you included every segment with a positive slope, even relatively flat, but bumpy paths could result in significant elevation changes. The key is to smooth the curves by adding a rolling threshold (a user-defined hyperparameter), as described in this article.
Exporting Routes to Navigation Tools
Once you’ve planned the perfect hike, you’ll want to export it as an orienteering-friendly format. For a hard copy version, the map and elevation profile can be printed directly from the UI.
However, users can also export their routes as GPX files (yet another geospatial format) and upload them to AllTrails, Gaia, Google Maps, and other GPS tracking applications.
Now, you can navigate your custom route from your phone, just like any other curated AllTrails hike!
Wrapping Up
In this demo, we leveraged open-source geographic datasets from OSM and NASA to build a functional hike planning application. Using a combination of graph theory, numerical analysis, and domain expertise, we came up with a mathematically-sound route optimization engine to automatically find complete loops that meet individual goals.
I’m looking forward to continuously improving the UI and underlying algorithms. If you’d like to run the code for yourself, see the full repository on Github.
References
Aric A. Hagberg, Daniel A. Schult and Pieter J. Swart, "Exploring network structure, dynamics, and function using NetworkX", in Proceedings of the 7th Python in Science Conference (SciPy2008), Gäel Varoquaux, Travis Vaught, and Jarrod Millman (Eds), (Pasadena, CA USA), pp. 11–15, Aug 2008
Map data copyrighted OpenStreetMap contributors and available from https://www.openstreetmap.org
NASA Shuttle Radar Topography Mission (SRTM)(2013). Shuttle Radar Topography Mission (SRTM) Global. Distributed by OpenTopography. https://doi.org/10.5069/G9445JDF. Accessed: 2022–08–30
Share This Article
Towards Data Science is a community publication. Submit your insights to reach our global audience and earn through the TDS Author Payment Program.
Write for TDS
