An Optimal Solution to the Oregon Badlands Challenge

To honor the tenth anniversary of the Oregon Badlands Wilderness designation, the Oregon Natural Desert Association (ONDA) is hosting a six-month long exploration challenge:

I bet one can, but how?

The problem

The map below (Figure 1) shows all 13 major trails. There’s a bunch of smaller connector segments in addition. So how does one go about completing all of these trails?

Of course you could do them one after another, in whatever order feels good. Yet, for this blog post I’m interested to find the shortest possible route that visits each and every trail at least once. Hmmm?! At which of the 5 trailheads does one start? And in what order does one complete the trails? How does one avoid having to complete some trail segments more than once? Is it better to start at one trailhead and to finish there as well? Or are there shorter routes that start at one trailhead but end somewhere else?

If you try to answer these questions by exploring possible solutions by hand, you will very quickly realize that such an attempt is utterly futile. There are simply too many combinations to explore. Also, how would you know that a given sequence is actually the shortest one?

Thankfully, modern graph theory provides us with a rich toolset to get to the bottom of this problem. Let’s get started!

A bit of graph theory

A graph G = (V, A) is composed by a set of nodes (or vertices) V and a set of edges (or links) A. Edges can be directed or undirected. Figure 2 shows both a directed and an undirected graph.

The above trail map from Figure 1 can straightforwardly be transformed into an abstract undirected graph. The graph is undirected because trails don’t have a direction. Figure 3 shows a visualization that retained the spatial location of the trailheads and trail intersections. The graph nodes V, i.e., the red dots, represent the trail intersections and trailheads (nodes 1, 9, 11, 14, and 24). Node IDs, which are essentially an arbitrary but unique number, are indicated in red. There’s a total of |V| = 24 nodes. The graph edges A, i.e., the black lines, represent trails. The |A|= 32 edges between the nodes represent trails. Each edge has an associated “cost,” which in our case is nothing more than the length of the trail segment measured in miles (indicated in bold/black).

The problem reformulated

Now that we have an abstract undirected graph with |V| = 24 nodes and |A| = 32 edges, we can really get down to business. Given the list of nodes V and the list of edges A (including their distance), what is the shortest possible route that visits each and every edge (i.e., trail) at least once?

This is different from the Traveling Salesman Problem (TSP), which seeks the shortest possible route that visits each and every node at least once. If we’d apply a TSP algorithm, we’d end up with a solution that visits all trail intersections, but not necessarily all trails.

Luckily our problem has a name and a solution as well: it’s called the Chinese Postman Problem (CPP) and is part of a more general class of route inspection problems. The CPP consists in finding the shortest closed route (or circuit) that visits each and every edge of a connected, undirected graph. Chinese mathematician Kwan Mei-Ko studied that problem in 1960. For more info, see for example here (pdf). There are many interesting variants of this problem, such as the Rural Postman Problem (RPP) or the Windy Postman Problem (WPP). Needless to say that most of these problems – and obviously their solutions – are hugely important for modern logistics that involve vehicle routing, delivery planning, scheduling, etc.

An undirected graph that has a closed route, i.e., a circuit, that visits every edge exactly once is called an Eulerian circuit. An Eulerian trail (or Euler walk) in an undirected graph is a walk that visits each edge exactly once. Note that, as opposed to the circuit, the Eulerian trail does not end where it starts. From the list of properties for an Eulerian circuit to exist, we can see right away that our trail graph in Figure 3 does unfortunately not have an Eulerian circuit. That’s not quite good news because it means that one will have to visit one or more edges several times.

Because most people are probably interested to start/finish at the same trailhead for the Oregon Badlands Challenge, we shall focus on a circuit here, but alas not an Eulerian one.

The solution

There are thankfully several algorithms and solvers for the Chinese Postman Problem (CPP). I’ll spare you all the technical details and present you with the solution to our problem. Here’s a summary of the most important solution details:

That means if one wants to visit all trails in a single push and start/finish at the same trailhead, one will have to complete a distance of 65.4 miles, that is 15.3 miles longer than the sum of all trails. As we already knew, there wouldn’t be a solution that visits each and every edge once and only once. In fact, 13 trail segments will have to be crossed twice.

The optimal trail sequence is listed in the table below. It shows the node IDs from Figure 3. An overlay map with the same IDs is shown in Figure 4. The circuit starts at node 1, which is the Tumulus trailhead (and the infamous start of the famous Oregon Desert Trail). I’ve created a spreadsheet with that info that one can use, copy, and download: http://bit.ly/BadlandsSegments. In addition, here is a downloadable pdf handout.

As you will notice quickly, the algorithm does not care about following particular trails, i.e., complete the Badlands trail first, then do the Dry River trail, etc. Well, why would it? That’s just a human thing we feel we have to perhaps do. Instead, the algorithm switches trails in a way that does not seem to make much sense, at least not without seeing the big picture.

I’ve created an animation so that you can better see the route. Direct URL: https://youtu.be/90g1fKtVkgE

The route is provably the shortest possible route that visits each and every trail at least once. There may be other routes that are equally short, but none will be shorter. Well, I should say there clearly care other routes that are equally short. For example, several of the out-and-backs can be done from one side or the other. That leads to the same overall distance, but the sequence would be different. If you are willing to start and finish at different trailheads, that’s a separate story that I’m not addressing in this post.

No matter what you end up doing, enjoy it, remember that you are a guest in nature, and be safe. Safety last.

Notes

Here are a few notes about route variants:

• Since the above-presented route visits all 5 trailheads, you can start at any of them and simply do the sequence from there. The total route length will be unchanged.
• Some out-and-backs can be done from two sides. Either way will lead to the same total distance.
• Some loops can be done clockwise or counter-clockwise. Either way will lead to the same total distance.
• You could shorten the total distance by starting and finishing at different trailheads. The above-presented route is only optimal if the start/finish trailhead is identical.
• You could further shorten the route if you would allow cross-country travel. The above-presented route assumes that you are always staying on trails.

Resources

• ONDA Badlands Challenge: https://onda.org/Badlands-Challenge
• Oregon Desert Trail: https://onda.org/regions/oregon-desert-trail