Biking 118 non-intersecting miles in Brooklyn

Introduction

Earlier this year, my goal was to get a Long Tiny Loop of score 30.0 or greater. I ended up falling short with a 29.75 which really annoyed me. Sooo, I set a new goal of scoring at least 40 by the end of the year. It took three attempts, I got a flat tire, and had to hop a barbed wire fence… But I eventually got it.

Path Design

Based on the design process from my first Long Tiny Loop attempt, I had a general idea of what I wanted to keep and what I wanted to improve for my second attempt. I knew that the QGIS Python plugin I had written for my first Long Tiny Loop was great at helping me design paths that were nearly optimal, but I also knew that I wanted to do better than “nearly” optimal this time.

Because of the combinatorial nature of this problem, the search space very quickly becomes intractable making any type of full path optimization impossible. To overcome this limitation, I ended up subdividing the search space into a number of smaller regions. For the regions that could be filed with long straight, tightly packed lines I just used my QGIS Python plugin. With the keyboard shortcuts dialed in, I was able to make quick work of these areas. After all, you can’t do much better than long, straight, tightly packed lines. But what about the regions that don’t support this type of geometry?

For these smaller sub-regions in which a clear solution wasn’t immediately apparent, I built out a genetic algorithm for finding it. However, before any path optimization could happen, the underlying OpenStreetMap network graph needed a little cleaning. Multi-lane roads were merged into single edges, complex intersections were consolidated, and spurious nodes were removed. Below is an example of one such region.

I experimented with a few different optimization approaches before settling on an evolutionary scheme. Because a path in this case is just an ordered list of graph edges, its description (number of parameters) is constantly changing. This is unlike most optimization scenarios in which the number of parameters remains fixed throughout the process (for example: airfoil aerodynamic shape optimization). This variability lends itself nicely to a genetic representation. It also helps that implementing evolutionary strategies is pretty easy.

Like most evolutionary algorithms, there are three main stages: selection, crossover, and mutation. When one sequential pass of these three stages has been completed, a new “generation” is produced and the process is repeated. After a few thousand generations, usually something useful emerges. Below are some implementation details for the curious:

Selection — Within the context of an evolutionary process, we need some way of determining who gets selected to pass on their genetic traits. Given a population of Long Tiny Loop paths (“individuals”) the length (“fitness”) of each individual can be determined. At this point, I usually default to the roulette wheel selection criteria for determining crossover pairing which is exactly what I did here. What this means is that paths with a higher fitness (longer length) are proportionally more likely to get selected for breeding. Additionally, 5% of the fittest individuals were carried over into the next generation unchanged (“elitism”).

Crossover — After two paths (“parents”) have been selected, they must be combined into a new single path (“offspring”) which will progress forward to the next generation. Because of the high degree of variability between paths, the range of crossover possibilities also varies drastically. Although only one offspring gets created, two parent paths can often generate hundreds of potential solutions. Each one possessing a unique combination of their parents’ DNA that has been spliced together in a way that forms a valid Long Tiny Loop path. Below is a fairly typical example of crossover.

Mutation — Over the course of evolution, if a population lacks sufficient genetic diversity it is susceptible to collapsing into a few highly fit individuals. To avoid this from happening, a small number of individuals are randomly selected for mutation. The number of new offspring which which will incur a mutation is dependent upon the mutation rate and is usually set at around ~5%. In this case, a mutation takes the form of a random perturbation along the path. It can appear as one or more additions, subtractions, or some combination of both. Below are a few mutation examples.

Once everything had been implemented, I could begin generating an optimal path. The initial population was seeded with 1000 valid Long Tiny Loop paths that were randomly generated. I then evolved this population for 40k generations…

The whole process didn’t take that long, so I ran it a bunch of times while experimenting with different parameter settings. The solution almost always converged to the same result which was reassuring. Below is the convergence history from one of the regions I optimized.

Just for reference, over the course of about five minutes in QGIS I was able to create a path 3772m long. The final optimized path ended up at 4170m yielding an additional 398m (+10.5% improvement).

After iterating back and forth for a while between my manual work in QGIS and the genetic algorithm I ended up with the final solution seen below. One critical design aspect that I wanted to ensure on my second attempt was having a decent buffer on my “expected” score. Last time my goal was to get at least a 30.0, so I designed a path that scored a 30.2 thinking that would suffice. Unfortunately, I ended up 0.45 short so I wanted at least a +1.0 margin of safety on my expected score this time. Overall it ended up coming out to roughly 118 miles (190km) with a 41.03 Long Tiny Loop score.

Just for a reference, here is what the new route looks like compared to my first attempt (yellow on left) which was roughly 66 miles long and scored a 29.75 on Long Tiny Loop.

Unfortunately, just like my first attempt this one too resides in deep Brooklyn. An area so ugly and full of single occupancy vehicle traffic that it might as well be Jersey.

Results

As I alluded to earlier, I ran into a few minor setbacks when I went out to actually complete the route. In the end though, I had fun and I ended up successfully completing it with a score of 40.51 and a total distance of 118.39 miles (190.54km) [strava activity -> here].

I like the idea of trying to increase my Long Tiny Loop score by 10 points each year, so I guess 2022 will hopefully see a score of at least 50?

Thanks for reading!

- Nathan