{"id":5317,"date":"2019-04-26T10:31:50","date_gmt":"2019-04-26T17:31:50","guid":{"rendered":"http:\/\/www.christofteuscher.com\/aagaa\/?p=5317"},"modified":"2023-03-27T14:47:00","modified_gmt":"2023-03-27T21:47:00","slug":"an-optimal-solution-to-the-oregon-badlands-challenge","status":"publish","type":"post","link":"https:\/\/christofteuscher.com\/aagaa\/an-optimal-solution-to-the-oregon-badlands-challenge\/","title":{"rendered":"An Optimal Solution to the Oregon Badlands Challenge"},"content":{"rendered":"\r\n

To honor the tenth anniversary of the Oregon Badlands Wilderness<\/a> designation, the Oregon Natural Desert Association (ONDA)<\/a> is hosting a six-month long exploration challenge<\/a>:<\/p>\r\n\r\n\r\n\r\n

\r\n
\r\n “There are 50+ miles of trails in the Badlands. Can you hike, horseback ride, or run them all?” [Source: https:\/\/onda.org\/Badlands-Challenge<\/a>]\r\n <\/div>\r\n <\/div><\/p>\r\n\r\n\r\n\r\n

I bet one can, but how?<\/p>\r\n\r\n\r\n\r\n\r\n\r\n

\"\"\r\n
Nope, nowhere did I say that I will ever do this challenge! [2021 update: I did.]<\/figcaption>\r\n<\/figure>\r\n\r\n\r\n\r\n

The problem<\/h4>\r\n\r\n\r\n\r\n

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?<\/p>\r\n\r\n\r\n\r\n

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<\/strong>. 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?<\/p>\r\n\r\n\r\n\r\n

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?<\/p>\r\n\r\n\r\n\r\n

Thankfully, modern graph theory<\/a> provides us with a rich toolset to get to the bottom of this problem. Let’s get started!<\/p>\r\n\r\n\r\n\r\n\r\n\r\n

\"\"<\/a>\r\n
Figure 1<\/strong>. Oregon Badlands map with all trails, distances, and trailheads. Source: ONDA<\/a>. Download the pdf<\/a>.<\/figcaption>\r\n<\/figure>\r\n\r\n\r\n\r\n

A bit of graph theory<\/h4>\r\n\r\n\r\n\r\n

A graph <\/strong>G<\/strong><\/em>\u00a0= (<\/strong>V<\/strong><\/em>,\u00a0<\/strong>A<\/strong><\/em>)<\/strong> is composed by a set of nodes<\/strong> (or vertices) V<\/em> and a set of edges<\/strong> (or links) A<\/em>. Edges can be directed<\/strong> or undirected<\/strong>. Figure 2 shows both a directed<\/a> and an undirected<\/a> graph.<\/p>\r\n\r\n\r\n\r\n

\"\"\r\n
Figure 2<\/strong>. A graph is composed by a set of nodes (or vertices) and a set of edges (or links). Links can be directed or undirected. Left: a directed graph. Right: an undirected graph.<\/figcaption>\r\n<\/figure>\r\n\r\n\r\n\r\n

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<\/strong>, 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<\/strong>. The graph edges A<\/strong>, i.e., the black lines, represent trails. The |A|= 32 edges<\/strong> 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).<\/p>\r\n\r\n\r\n\r\n

 <\/p>\r\n\r\n\r\n\r\n

\"\"<\/a>\r\n
Figure 3<\/strong>. A graph representation of the Oregon Badlands trail system. Nodes (red) represent trailheads or trail intersections. Node IDs are shown in red. Edges (black) represent trails. Each edge has an associated “cost,” i.e., the length of the trail segment (in miles). The graph is undirected because the edges, i.e., the trails, do not have a direction.<\/figcaption>\r\n<\/figure>\r\n\r\n\r\n\r\n

The problem reformulated<\/h4>\r\n\r\n\r\n\r\n

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? <\/strong><\/p>\r\n\r\n\r\n\r\n

This is different from the Traveling Salesman Problem<\/a><\/em> (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.<\/p>\r\n\r\n\r\n\r\n

Luckily our problem has a name and a solution as well: it’s called the Chinese Postman Problem<\/a><\/em> (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<\/strong>. Chinese mathematician Kwan Mei-Ko studied that problem in 1960. For more info, see for example here (pdf)<\/a>. There are many interesting variants of this problem, such as the Rural Postman Problem<\/em> (RPP) or the Windy Postman Problem<\/em> (WPP). Needless to say that most of these problems \u2013 and obviously their solutions \u2013 are hugely important for modern logistics that involve vehicle routing, delivery planning, scheduling, etc.<\/p>\r\n\r\n\r\n\r\n

An undirected graph that has a closed route, i.e., a circuit, that visits every edge exactly once is called an Eulerian circuit<\/strong><\/a>. An\u00a0Eulerian trail<\/strong> (or Euler walk)<\/strong> 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<\/a>, we can see right away that our trail graph in Figure 3 does unfortunately not<\/em> 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.<\/p>\r\n\r\n\r\n\r\n

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.<\/p>\r\n\r\n\r\n\r\n

The solution<\/h4>\r\n\r\n\r\n\r\n

There are thankfully several algorithms and solvers for the Chinese Postman Problem<\/a><\/em> (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:<\/p>\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n
Distance, total<\/td>\r\n65.4mi<\/td>\r\n<\/tr>\r\n
Distance, crossed once<\/td>\r\n50.1mi<\/td>\r\n<\/tr>\r\n
Distance, doublebacked<\/td>\r\n15.3mi<\/td>\r\n<\/tr>\r\n
Trail segments, total<\/td>\r\n45<\/td>\r\n<\/tr>\r\n
Trail segments, doublebacked<\/td>\r\n13<\/td>\r\n<\/tr>\r\n
Trail segments, crossed once<\/td>\r\n32<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n\r\n

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.<\/p>\r\n\r\n\r\n\r\n

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<\/a>). I’ve created a spreadsheet with that info that one can use, copy, and download: http:\/\/bit.ly\/BadlandsSegments<\/a>. In addition, here is a downloadable pdf handout<\/a>.<\/p>\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n
Segment number<\/strong><\/td>\r\nStart node<\/strong><\/td>\r\nEnd node<\/strong><\/td>\r\nSegment distance [mi]<\/strong><\/td>\r\nCumulative distance [mi]<\/strong><\/td>\r\nDouble- backed<\/strong><\/td>\r\nTrail name<\/strong><\/td>\r\n<\/tr>\r\n
1<\/td>\r\n1<\/td>\r\n2<\/td>\r\n0.5<\/td>\r\n0.5<\/td>\r\nYes<\/td>\r\nTumulus<\/td>\r\n<\/tr>\r\n
2<\/td>\r\n2<\/td>\r\n4<\/td>\r\n1.5<\/td>\r\n2<\/td>\r\n\u00a0<\/td>\r\nTumulus<\/td>\r\n<\/tr>\r\n
3<\/td>\r\n4<\/td>\r\n6<\/td>\r\n3<\/td>\r\n5<\/td>\r\n\u00a0<\/td>\r\nTumulus<\/td>\r\n<\/tr>\r\n
4<\/td>\r\n6<\/td>\r\n7<\/td>\r\n2<\/td>\r\n7<\/td>\r\nYes<\/td>\r\nTumulus<\/td>\r\n<\/tr>\r\n
5<\/td>\r\n7<\/td>\r\n15<\/td>\r\n3.3<\/td>\r\n10.3<\/td>\r\n\u00a0<\/td>\r\nBadlands Rock<\/td>\r\n<\/tr>\r\n
6<\/td>\r\n15<\/td>\r\n10<\/td>\r\n2.7<\/td>\r\n13<\/td>\r\nYes<\/td>\r\nBadlands Rock<\/td>\r\n<\/tr>\r\n
7<\/td>\r\n10<\/td>\r\n11<\/td>\r\n0.3<\/td>\r\n13.3<\/td>\r\nYes<\/td>\r\nBadlands Rock<\/td>\r\n<\/tr>\r\n
8<\/td>\r\n11<\/td>\r\n10<\/td>\r\n0.3<\/td>\r\n13.6<\/td>\r\n\u00a0<\/td>\r\nBadlands Rock<\/td>\r\n<\/tr>\r\n
9<\/td>\r\n10<\/td>\r\n12<\/td>\r\n2.1<\/td>\r\n15.7<\/td>\r\n\u00a0<\/td>\r\nHomestead<\/td>\r\n<\/tr>\r\n
10<\/td>\r\n12<\/td>\r\n13<\/td>\r\n0.1<\/td>\r\n15.8<\/td>\r\nYes<\/td>\r\nFlatiron Rock<\/td>\r\n<\/tr>\r\n
11<\/td>\r\n13<\/td>\r\n14<\/td>\r\n1.9<\/td>\r\n17.7<\/td>\r\n\u00a0<\/td>\r\nAncient Juniper<\/td>\r\n<\/tr>\r\n
12<\/td>\r\n14<\/td>\r\n13<\/td>\r\n1.2<\/td>\r\n18.9<\/td>\r\n\u00a0<\/td>\r\nFlatiron Rock<\/td>\r\n<\/tr>\r\n
13<\/td>\r\n13<\/td>\r\n12<\/td>\r\n0.1<\/td>\r\n19<\/td>\r\n\u00a0<\/td>\r\nFlatiron Rock<\/td>\r\n<\/tr>\r\n
14<\/td>\r\n12<\/td>\r\n16<\/td>\r\n1.5<\/td>\r\n20.5<\/td>\r\n\u00a0<\/td>\r\nFlatiron Rock<\/td>\r\n<\/tr>\r\n
15<\/td>\r\n16<\/td>\r\n17<\/td>\r\n2<\/td>\r\n22.5<\/td>\r\n\u00a0<\/td>\r\nFlatiron Rock<\/td>\r\n<\/tr>\r\n
16<\/td>\r\n17<\/td>\r\n18<\/td>\r\n0.7<\/td>\r\n23.2<\/td>\r\nYes<\/td>\r\nMazama Ash<\/td>\r\n<\/tr>\r\n
17<\/td>\r\n18<\/td>\r\n23<\/td>\r\n0.7<\/td>\r\n23.9<\/td>\r\n\u00a0<\/td>\r\nMazama Ash<\/td>\r\n<\/tr>\r\n
18<\/td>\r\n23<\/td>\r\n19<\/td>\r\n0.7<\/td>\r\n24.6<\/td>\r\nYes<\/td>\r\nChitwood<\/td>\r\n<\/tr>\r\n
19<\/td>\r\n19<\/td>\r\n23<\/td>\r\n0.7<\/td>\r\n25.3<\/td>\r\n\u00a0<\/td>\r\nChitwood<\/td>\r\n<\/tr>\r\n
20<\/td>\r\n23<\/td>\r\n22<\/td>\r\n0.3<\/td>\r\n25.6<\/td>\r\n\u00a0<\/td>\r\nChitwood<\/td>\r\n<\/tr>\r\n
21<\/td>\r\n22<\/td>\r\n24<\/td>\r\n0.2<\/td>\r\n25.8<\/td>\r\nYes<\/td>\r\nChitwood<\/td>\r\n<\/tr>\r\n
22<\/td>\r\n24<\/td>\r\n22<\/td>\r\n0.2<\/td>\r\n26<\/td>\r\n\u00a0<\/td>\r\nChitwood<\/td>\r\n<\/tr>\r\n
23<\/td>\r\n22<\/td>\r\n21<\/td>\r\n0.7<\/td>\r\n26.7<\/td>\r\n\u00a0<\/td>\r\nChitwood<\/td>\r\n<\/tr>\r\n
24<\/td>\r\n21<\/td>\r\n20<\/td>\r\n3.2<\/td>\r\n29.9<\/td>\r\n\u00a0<\/td>\r\nChitwood<\/td>\r\n<\/tr>\r\n
25<\/td>\r\n20<\/td>\r\n21<\/td>\r\n1.8<\/td>\r\n31.7<\/td>\r\nYes<\/td>\r\nChitwood Cutoff<\/td>\r\n<\/tr>\r\n
26<\/td>\r\n21<\/td>\r\n20<\/td>\r\n1.8<\/td>\r\n33.5<\/td>\r\n\u00a0<\/td>\r\nChitwood Cutoff<\/td>\r\n<\/tr>\r\n
27<\/td>\r\n20<\/td>\r\n19<\/td>\r\n1.9<\/td>\r\n35.4<\/td>\r\n\u00a0<\/td>\r\nChitwood<\/td>\r\n<\/tr>\r\n
28<\/td>\r\n19<\/td>\r\n18<\/td>\r\n1.8<\/td>\r\n37.2<\/td>\r\n\u00a0<\/td>\r\nSand Lily<\/td>\r\n<\/tr>\r\n
29<\/td>\r\n18<\/td>\r\n17<\/td>\r\n0.7<\/td>\r\n37.9<\/td>\r\n\u00a0<\/td>\r\nMazama Ash<\/td>\r\n<\/tr>\r\n
30<\/td>\r\n17<\/td>\r\n5<\/td>\r\n0.8<\/td>\r\n38.7<\/td>\r\n\u00a0<\/td>\r\nMazama Ash<\/td>\r\n<\/tr>\r\n
31<\/td>\r\n5<\/td>\r\n17<\/td>\r\n0.8<\/td>\r\n39.5<\/td>\r\nYes<\/td>\r\nMazama Ash<\/td>\r\n<\/tr>\r\n
32<\/td>\r\n17<\/td>\r\n16<\/td>\r\n2<\/td>\r\n41.5<\/td>\r\nYes<\/td>\r\nFlatiron Rock<\/td>\r\n<\/tr>\r\n
33<\/td>\r\n16<\/td>\r\n15<\/td>\r\n1.1<\/td>\r\n42.6<\/td>\r\n\u00a0<\/td>\r\nThe Castle<\/td>\r\n<\/tr>\r\n
34<\/td>\r\n15<\/td>\r\n10<\/td>\r\n2.7<\/td>\r\n45.3<\/td>\r\n\u00a0<\/td>\r\nBadlands Rock<\/td>\r\n<\/tr>\r\n
35<\/td>\r\n10<\/td>\r\n8<\/td>\r\n5.1<\/td>\r\n50.4<\/td>\r\n\u00a0<\/td>\r\nDry River<\/td>\r\n<\/tr>\r\n
36<\/td>\r\n8<\/td>\r\n9<\/td>\r\n2.9<\/td>\r\n53.3<\/td>\r\nYes<\/td>\r\nDry River<\/td>\r\n<\/tr>\r\n
37<\/td>\r\n9<\/td>\r\n8<\/td>\r\n2.9<\/td>\r\n56.2<\/td>\r\n\u00a0<\/td>\r\nDry River<\/td>\r\n<\/tr>\r\n
38<\/td>\r\n8<\/td>\r\n7<\/td>\r\n0.5<\/td>\r\n56.7<\/td>\r\n\u00a0<\/td>\r\nTumulus<\/td>\r\n<\/tr>\r\n
39<\/td>\r\n7<\/td>\r\n6<\/td>\r\n2<\/td>\r\n58.7<\/td>\r\n\u00a0<\/td>\r\nTumulus<\/td>\r\n<\/tr>\r\n
40<\/td>\r\n6<\/td>\r\n5<\/td>\r\n2.2<\/td>\r\n60.9<\/td>\r\n\u00a0<\/td>\r\nMazama Ash<\/td>\r\n<\/tr>\r\n
41<\/td>\r\n5<\/td>\r\n3<\/td>\r\n1.5<\/td>\r\n62.4<\/td>\r\n\u00a0<\/td>\r\nBlack Lava<\/td>\r\n<\/tr>\r\n
42<\/td>\r\n3<\/td>\r\n4<\/td>\r\n0.6<\/td>\r\n63<\/td>\r\nYes<\/td>\r\nBasalt<\/td>\r\n<\/tr>\r\n
43<\/td>\r\n4<\/td>\r\n3<\/td>\r\n0.6<\/td>\r\n63.6<\/td>\r\n\u00a0<\/td>\r\nBasalt<\/td>\r\n<\/tr>\r\n
44<\/td>\r\n3<\/td>\r\n2<\/td>\r\n1.3<\/td>\r\n64.9<\/td>\r\n\u00a0<\/td>\r\nBlack Lava<\/td>\r\n<\/tr>\r\n
45<\/td>\r\n2<\/td>\r\n1<\/td>\r\n0.5<\/td>\r\n65.4<\/td>\r\n\u00a0<\/td>\r\nTumulus<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n

 <\/p>\r\n\r\n\r\n\r\n

\"\"<\/a>\r\n
Figure 4<\/strong>. Overlay map with trail intersections and trailhead node IDs (red) and the shortest route (blue). Click to enlarge.<\/figcaption>\r\n<\/figure>\r\n\r\n\r\n\r\n\r\n\r\n

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.<\/p>\r\n\r\n\r\n\r\n

I’ve created an animation so that you can better see the route. Direct URL: https:\/\/youtu.be\/90g1fKtVkgE<\/a><\/p>\r\n\r\n\r\n\r\n