How *not* to build cycling routes 🔀

If you've used Huli to get some cycling routes, you'll have hopefully been able to get a number of route options in a few short seconds. But every time you hit that "Create Routes" button, it's not just the 10 routes you see getting built. A lot more is happening in the background, which is something I'll get on to in another post. Right now, I want to talk about the original approach we had. It was the wrong approach and it cost us a fair bit of time and head scratching. Let me explain.

Warning: This one gets a wee bit more technical than other blogs 🤓

They say that research is really just a long journey of discovering what doesn't work. This was a big part of our research at Huli during the early months.

Let's start with the most crude approach to tackling the problem of which way to turn at a junction. If you just set out on your bike, with no plan of where to go, which direction would you head out of your front door? What about at the end of that first street? At the end of the second street? At what point do you stop getting further from your home and start turning back towards it? If you picked all these things at random, would it be a good route? What if you tried 100 times? 1,000 times? Ok ok, let's look to see how this might work in practice.

Assume you live in a grid-system neighbourhood, where every block was 1km x 1km in size and you wanted to go on a walk. You head outside and make the decision to go a particular way. At every junction you reach, you have a choice of 3 options - turn left, turn right or go straight on (we'll assume no U-turns). Since we start off with 4 options from our home, and each of these has 3 options at their respective junctions, after 2 km we'll have 4 x 3 = 12 routes. If we went 3 km, this would become 4 x 3 x 3 = 36 routes. 4km? 108 routes... By 10km we'd have 236,196 route options. Wow ok, that grew FAST! In fact, the plot below shows just how fast the number of routes grow with the number of streets you traverse, with a few of the 4km route options shown by the red, green & yellow edges in the grid on the right. Perhaps worth mentioning at this point, that our average section length (distance between two junctions) in Huli is just 113m long, so the number of route options would increase much, MUCH faster than this!

Hopefully it's clear then that simply choosing a direction at random and checking the results is not a good solution for planning long bike rides! So, how do we improve on this? Well let's think about all the things we know we don't want to do:

1. We don't want to be stranded away from home after completing our desired distance
2. We don't want to just remain in one small area - we're on a bike, let's see the world!
3. We don't want to be traversing too many roads/paths that aren't "good" (I'm going to cover how we define this in a later post, so for now assume we just know what "good" is)
   

This is the set of requirements we used in the early days to try and turn the above routing nightmare, into a tech start-up's dream... It all hinged on combining the above limitations with one simple concept:

The ideal straight-line distance from the start/end locations, is some function of the total distance travelled

What I mean by this is that as we explore outwards from our start location, we monitor how far we've travelled on each journey and compare that to how far we are (in a straight line) from home. If we were too close or too far away, given how far we've gone, the journey gets discarded. Here's a few examples showing how this looks in practice. The route in red snakes its way around the local area (not very adventurous), the one in blue follows a perfect circle (ooo, nicely adventurous!) and the one in yellow goes almost out and back in a straight line (quite adventurous, but the 2nd half is in identical the first half, just in reverse, so not ideal).

From the perspective of route "quality", ignoring ALL of the other, many, many factors that play into how much one would enjoy a route, there's a clear loser here. It's nice to feel like we're exploring new places, so zig-zagging around our local streets is likely not going make the cut. Graphically, what this looks like in terms of the "as the crow-flies" distance from home (y-axis) vs. total distance travelled (x-axis) is:

You can see how, with the zig-zag route, we don't ever really get too far from home, even at the half way point. Ok, so what if we said that the circular route was "ideal" (I know that's not the reality, but it helps define the problem...) and we're willing to accept some threshold either side of that circle, else we consider the route "bad" and discard it. By doing this, we can check to see how we're doing, at regular intervals, as we explore out from the start point. Making sure the whole time that our straight line distance from home is within some acceptable range from our "ideal" value. Now we have control over how many of the routes we discard as things grow. Happy days! That means we solved the scaling problems, right?

Well, no. Not really. It did help for sure and using this approach alongside a load of other "good route" checks, we could find longer routes in reasonable times. But it fundamentally failed to address the main scaling issue. The fact that for every route we were exploring, the complexity of the problem increased at an increasing rate as we extended those routes. This is the first rule of algorithm development, and we were too focused on implementing something new and exciting, we failed to get the basics right first! We could solve the issue by really restricting how much deviation we would accept from the "perfect circle", but this just left us with a load of very circular routes... Also, not good.

Fast forward a few months and we had a new method for generating routes, which is what we continue to use today (albeit slightly more advanced than it was back then). So I guess all's well that ends well, but if you were one of our early users and were waiting 5 mins for those five 20km routes to come through, I apologise! Hopefully you've been able to find some nice long routes using Huli since.

I hope you've enjoyed learning a little more about how not to generate cycling routes, if you have any questions or comments, I'd love for you to get in touch at chris@huli.life, or you can get me on Twitter, Instagram or LinkedIn.