Forest Park All Trails Challenge, and my 2020 Birthday Run

It started innocently enough with a geometry problem. A real head-scratcher: what is the best possible route that will travel the entirety of every trail of Forest Park in one push? Wouldn’t it be fun to run every trail in Forest Park this way? After all, the Forest Park Conservancy sponsors the All Trails Challenge- a yearly event where hikers can track their progress in completing all 83 miles of trail inside the park, so there’s precedent for hiking it… so why not run it all in one push? And what route would be the best to take?

There is a lot of literature on route optimization. It’s economically important and there is a branch of mathematics called graph theory that includes this subject. Similar problems are solved routinely for delivery services and logistics operations to minimize costs. Euler is credited as laying the groundwork for graph theory with his proof that no solution to the Seven Bridges of Königsberg problem existed (he solved it in 1736 at the age of 29).

The Seven Bridges of Königsberg problem is as follows: Is it  possible to take a walking journey across all seven bridges without having to cross any bridge more than once?

Euler defined the land masses (the nodes) as A, B, C, and D and the bridges (the edges or links) as a-g. It’s a little easier to see what’s going on with the interconnections once it’s defined this way, and I’ve drawn a graph below to help show the interconnection between the land masses and the bridges.

What Euler argued is that in order to travel each bridge (the edges or lines in the graph) once from one of the land masses (the nodes), then you must be able to enter and exit a given node an even number of times. You can only enter and exit a node an even number of times without repeating an edge (the interconnecting lines) if there are an even number of edges connected to the node. Since in the example above the nodes have an odd number of edges, there is no way to solve the Seven Bridges problem without repeating a bridge.

If a graph has nodes that are all even, then it is considered Eulerian, and a solution exists where each edge can be traveled exactly once in such a way that all edges of the graph are traveled. For our purposes this is an optimal solution to our problem of how to run every trail in Forest Park in a single push.

Unfortunately, Forest Park has lots of odd nodes, so at first, this seems impossible. In the map below, we can see some of Forest Park. I have only shown a small part of the park here to keep it simple for now.

The Forest Park Conservancy has a list of all the named trails that are part of the All Trails Challenge. From this list we find that in this part of the map, we must cover the Wildwood, Upper McLeay, Lower McLeay, Cumberland, and Tunnel trails. I have added nodes to the map at their intersections and endpoints below.

Then I connect the nodes with the appropriate edges to reconstruct the trail network as a graph. I’ve also added the length of the edges to the graph as well.

The next step is to identify all the nodes that are even (green) and all the nodes that are odd (red). Entry and exit nodes get +1 edge added to them (you can think of them being connected together through an edge). So node A is actually degree 2 (even) and node F is degree 3 (odd) since we have chosen to enter and exit the graph by these nodes. More on entrance/exit strategies later.

Since there are six odd nodes the graph is not Eulerian, so there is currently no way to create a route that traverses each edge once. If we pair the odd nodes by adding edges between them, then we can create a graph that has all even nodes. The trick to adding edges between the odd nodes is to do so in such a way that it minimizes the sum total distance of the added edges.

For example, I need to pair node F with another node. I can choose to pair with node E, since it’s close. Then I need to pair node D with another node, but I can’t use node E since it is now paired to node F. So I pair D with H. This leaves I to be paired with G. The sum of the added edges is 1.46 miles.

Alternatively, I could pair node F with node D through node B. Then pair E with H and G with I. The sum of these added edges is 1.52 miles. Since this is more added edge distance than the previous route, it is less optimal from a minimum distance perspective.

Look outside the box.

This is where I made my first mistake by failing to look outside the box. I did not consider running up Cornell Rd from the tunnel node G to the finish node F. I realized my shortsightedness while on the tunnel trail, but by that point it was too late since I still needed to backtrack in order to pick up the double edge between E and D. If we consider running up the road (it could be a little risky with traffic) then we have this graph:

Many routes are optimal

Now that the odd nodes are all paired, we can make a route that uses each edge in the graph.

At this stage it’s not too important the order in which the edges are completed since we’re only optimizing the total distance. Here’s another route with the same outcome- same paths covered, same distance, just a different order.

In fact, there may be many optimal solutions to an Eulerian graph, depending on the number of nodes and edges. More optimizations than distance are possible as well. For example some trails may be more optimal to travel twice instead of another due to hills, technical footing, or some other preference. These preferences can be weighted by adding or subtracting into the “distance cost” of the edge.

The Run

You get the idea with the route planning. I probably spent more time planning than I did running. So at 6 AM on my birthday Bree dropped me off at the zoo and I ran. And ran and ran and ran. Bree set up aid stations along the way at some prominent points (Thurman gate, bottom of FL #1, Newberry Rd, etc…). I had some great company along the way as well: my buddy Rick brought me popsicles and grilled cheese which was amazing. My buddy Scott ran with me a couple hours into the night which was cool. And Tom came out to cheer me on!

I got tired around 3 AM and took a dirtnap for an hour at the intersection of Leif and Tolinda for about an hour. This was the first time I have slept in a city park when I wasn’t drunk, so that’s exciting. The next morning Rick found me in my zombie-stupor-shuffle wandering around the North park and we did some more miles together. Bree picked me up and took me home when I was done. Thanks everyone for supporting me! It took me just under 29 hours to complete the route. I think I can spot the transition from Type I to Type II fun in the pictures below…