How to find the optimal cycling route
Here’s a thought experiment for you. Say you went out and rode every street in your suburb. What would the distance of that ride be? What if you did it again, but tried to keep the distance as short as possible? How would you go about finding the optimal route? And how do you think that optimal route would compare to your initial attempt?
Over the past month or so my friend and colleague Andy van Bergen and I have been trying to answer those very questions, with more than a little help from an old cycling buddy. Before we dive into the details though, let’s take a step back and set the scene.
Back in April, with all of the CyclingTips Melbourne crew working from home thanks to the coronavirus lockdown, Andy and I set ourselves a challenge: to ride every street in our local suburb of Ivanhoe, without consulting a map once. It took several weeks of planning, reconnaissance rides, and breaking the suburb down into manageable chunks, but on May 8 we went out and did it. It took nearly four hours of riding and 85 km to cover every street. Well, almost every street, depending on how you feel about “roads” that masquerade as car parks.
In the weeks and months that followed, our ‘Burbing’ continued. It felt best to stay close to home while riding so tackling more nearby suburbs seemed like a good way to keep things interesting. On May 16 I rode all of East Ivanhoe without a map (on my second attempt). On May 30 I did the same in Alphington on my third attempt. And then, on June 8, Andy and I joined VeloClub member — and weekly Zwift group ride leader — Aaron Keeffe to tackle hilly Eaglemont, also without a map (at that time you could ride with more than one person).
I’ll remember that day for a few reasons: the searingly cold air at the start, Aaron’s forethought to bring a thermos of coffee to the start (and one of peppermint tea for Andy, who’s still off caffeine), and Aaron’s wife Belinda bringing us more hot drinks and croissants mid-ride. It was the perfect Burbing.
A few weeks later I went and snagged Fairfield on my second go which left me with five Burbings (again depending on how you feel about roads that are actually carparks).
A short time later, Jim Crumpler, a guy Andy and I have known for years through cycling (also a VC member), started working on a Burbing-inspired routing project. He’d watched Andy, myself and a bunch of others tackle local suburbs during ‘iso’, and figured he’d put his IT skills to use, concocting a software application that would devise the optimal Burbing route for a given area.
I got excited when I saw his project — as I wrote in my original article on CyclingTips, the idea of optimising a Burbing ride seems like a logical extension once you’ve tackled a suburb once. Being able to use a computer program to help check your work afterwards? Sweet. I reached out to Jim and asked if he’d be happy to help Andy and I with a little project.
The idea was simple: Andy and I would ride a given suburb a few times and see if we could optimise our route to make the ride as short as possible. Jim, meanwhile, would work his magic to devise the optimal route for that suburb, which he wouldn’t share with us until we’d tried it ourselves a few times. When he did share the solution, we’d be able to see how close we got and how our strategy compared to that used by Jim’s application.
Jim graciously agreed, and kept tinkering with his program. Andy and I put our heads together (1.5 metres apart, naturally) and started spending some time in our target suburb: Bellfield.
That tiny red square in north east Melbourne is Bellfield.
Bellfield is the perfect suburb for this sort of experiment. For starters, it’s just a couple of kilometres from home for both Andy and I but crucially, it’s tiny — less than 1 square kilometre in area. This means it’s relatively quick to ride, and doing it multiple times over the space of several weeks wouldn’t feel like a chore.
While Bellfield was the perfect suburb for the challenge, it did have one drawback: a short section along Bell Street to the Darebin Creek where Bellfield meets Preston. This stretch is an awful section of an already terrible road for cyclists — it’s narrow, there’s plenty of traffic, and the road is often covered in all manner of debris. Not only that but when you reach the creek, getting back to Bellfield proper means either heading up a footpath, or crossing four lanes and a median strip on Bell St then riding the same horrible stretch in the opposite direction. No thanks.
It mightn’t look too bad, but this section of Bell St is no good to ride.
Andy and I decided we’d ride this 400 metre section of Bell St in our first Bellfield Burbing — so we could say we’d done the whole suburb — but that we’d skip it on subsequent rides. When liaising with Jim, the area we asked him to create a route for was Bellfield minus the Bell Street horrorshow.
The part of Bellfield we were trying to optimise for. Note that the section of Bell St between Liberty Parade and Darebin Creek (north west corner) has been excised.
On June 25 Andy and I had our first crack at Bellfield. As with all of our previous suburbs we didn’t use a map during the ride. We weren’t worried about efficiency at all on this attempt — it was simply about setting a baseline and getting another suburb ticked off.
With minimal reconnaissance or preparation we very nearly got it first go — only the pesky Willow Court evaded us. A couple weeks later, on July 7, we went back and had another go, again just trying to set a baseline distance. This time we managed to cover every street in a total of 19.3 km. Subtracting the awful Bell Street out-and-back we were left with a distance of 18.6 km for the area we were trying to optimise.
Our first successful attempt at Bellfield. The area we were interested in was the above minus the Bell St chunk in the north west corner.
On July 16, we went back to Bellfield again, this time with a plan to reduce the distance as much as we could. We didn’t plan a strategy out beforehand and again we didn’t look at a map during the ride. This time we skipped the Bell St extension and got a total of 17.5 km — an improvement of 1.1 km (or 5.9%) compared to our previous ride. We came away from that ride thinking we could have been more efficient again — we’d doubled up on a section of Bell St that we really didn’t need to. But with time against us — I was moving house a week later — it was time to wrap up the project.
We got back in touch with Jim and asked him to generate the optimal route for our version of Bellfield — the most efficient way of visiting every street.
Before we get to the route Jim’s program produced, let’s take a moment to discuss how his application actually works.
Jim’s program is written in Python. On the left you can see it creating the GPX file line by line.
It turns out this route optimisation challenge has a name: the “route inspection problem”, or the “Chinese Postman Problem”, named in honour of Chinese mathematician Kwan Mei-Ko in 1960. In a Facebook post about his project, Jim described the problem as “a maths nightmare” and said that while the solution is “well known” that “doesn’t mean easy”.
“I work in ‘IT’, which doesn’t imply being a programmer, but I always tinker with code,” Jim told me. “I have a degree in electronic engineering ([which] includes computer science), but there’s so many diverse areas that you would never look at. This stuff is pure maths (solving ‘graph network’ problems), and geospatial data and tools, and OpenStreetMap and shapefiles, etc. There’s libraries to help do a lot of this stuff in simple ways, but I didn’t know the background, so it took weeks to learn geospatial concepts, projections, data models, OpenStreetMap data, graph theory, various optimisation algorithms.
“I’ve worked on it most nights for a month or so. Most of that time was learning, which is the main objective here for me.”
OpenStreetMap is a gold mine for anyone looking to dive into mapping data and create their own projects. This map shows every road in the visible area.
So how does it actually work? As Jim explains, the application starts with OpenStreetMap data then takes the following steps:
“Find all the roads within a suburb boundary. Find every intersection and count the number of roads going into that intersection. If there’s an odd number of roads at the intersection, it means you’re going to have to ride one of those roads twice (to get in and out). From one odd-node intersection, you’re going to have to get to another odd-node, so build a combination of all pairs of odd intersections and find the list that has the shortest total distance. Throw these new paths in with even-intersections, and ride them all!”
Jim explains that the application isn’t as concerned with the order the roads are ridden in, nor where the route starts; it’s more concerned with “how to get between all these odd intersections without going too far.”
For context, our version of Bellfield has 118 “odd intersections” which means the program generates a list containing thousands of combinations of odd intersections. Even still, it takes Jim’s application about 15 seconds to produce an optimal route for Bellfield.
A node map of our Bellfield area. Red nodes have an odd number of streets into the intersection; blue nodes have an even number.
The route created by Jim’s app isn’t perfect. The program currently can’t factor in one-way roads, and with the northern border of Bellfield being in the central median of Bell St, the optimal route ended up going the wrong way on Bell St for 150 metres. Still, one minor issue like this wasn’t going to stop Andy and I from riding it — it just meant we’d need to make a quick visit to a footpath.
One of the niftiest parts about Jim’s application is the fact it can produce a GPX file of the optimal route, ready to be uploaded to your routing website of choice, or to a GPS device. Andy and I were a little concerned that the intricate nature of the route would prove too much for our GPS devices, so instead of risking a unit meltdown, I went through and wrote out turn-by-turn instructions for the entire route which Andy and I could follow.
And so, late last week, armed with a double-sided sheet of hastily scribbled instructions, Andy and I set out to ride Jim’s optimal route for Bellfield, to see how the program’s Burbing strategy compared to our own.
Our hand-written notes for the optimal Bellfield Burbing.
We noticed a few differences with the computer-designed route. For starters it seemed almost random in how it moved through the suburb, even though it’s clearly the opposite. Our own strategy was a methodical one: tackle one east-west street, doing all of its side streets, then tackle the next east-west street and repeat the process. The computer-generated route features almost none of this — instead it seems to meander around the suburb, leaving streets behind then picking them up later.
On several occasions while following Jim’s route Andy and I rode past a street we hadn’t done and one of us would say “what about that one?” — the idea of leaving streets behind was anathema to our own strategy. But the optimal route always came back to those streets at some point. Unlike us, Jim’s algorithm doesn’t have to worry about forgetting a street it’s ridden past.
The impact of this strategy was far fewer U-turns than what we’d done in our attempts. As a result the ride felt like it flowed a lot better (the fact we were following a set route, rather than making it up on the fly, probably helped too).
We noticed something else about the algorithm’s more-fluid, meandering route. Where our usual strategy was to ride the outline of Bellfield first then break the suburb into an east and a west section — separated by the north-south-running Oriel Road — Jim’s program jumped back and forth between sections, and did the suburb outline in pieces rather than in one solid effort. Again, the program doesn’t need to worry about forgetting sections like we do.
In the end, by following Jim’s route we managed to complete our whole target area in 15.6 km — 3 km shorter than our first successful attempt (16.1% more efficient), and 1.9 km shorter than the second (10%). I’m pretty happy with how close we got to the optimal solution!
The final result.
There’s so much to love about cycling: the fitness, the challenge, the social aspect, the sense of adventure, and a whole lot more. That it makes projects like this possible is yet another thing to love about it. I had a blast working on this in recent months and I’m sure it won’t be the last such ride I do.
A big thank you to Andy for his company and interest in tackling this project with me, and to Jim for his time and efforts on such a cool piece of software. Maybe if enough of us bombard Jim in the comments section below he’ll give his program a little more polish and make it available for everyone to play with!
In closing, I thought I’d share another optimal routing solution that Jim’s program was able to create, this time for something quite a bit larger. Here’s the most efficient way to cover every road in the entire locality of Dargo in East Gippsland, roughly 300 km east of Melbourne. If that looks like a massive ride, well, you’re right. In Jim’s words: “Dargo is 2,392 km and 73,000 m of climbing, and I bet most of that would be extreme 4WD tracks.”
Any takers?
While it took Jim’s app around 15 seconds to calculate the optimal route for Bellfield, this monster took more than 15 hours.
The post How to find the optimal cycling route appeared first on CyclingTips.