CycleStreets blog

CycleStreets will shortly be hiring a full-time core developer to work on our routing engine and website. The aim is to enable us to implement improvements to the routing and implement lots of feature requests a lot more quickly.

This is possible thanks to a series of contracts and grants we've recently obtained, some of which we've recently reported about on this blog.

Our core aim with CycleStreets is to create "routing that thinks like a cyclist". This means including some things, such as turn delays and complex rules that would seem to be challenging to implement with off-the-shelf engines.

We're therefore wanting to take someone on who is able to work on what are interesting computer science problems (as distinct from purely "web development"). However, we'd hope that a suitable person can help work on the website (e.g. backend/frontend integration, general web development. refactoring) as well.

Background info: about our routing engine

The CycleStreets routing system finds, quietest, fastest and balanced cycling routes between two points in the British Isles. It does this by building a route planning version of the map (known as a graph) for each of these types of route.

Each graph consists of vertices and edges that correspond to junctions and streets. On each graph the length of an edge corresponds to the cost for that route type of travelling along a street. So, roads and wide cycle tracks will have relatively short links on the graph for fastest routes, but the links that represent footpaths and bridleways where the cycling speed is slower will be longer. By contrast, on the graph for quietest routes, cycleways and park paths will be short relative to busy roads.

The optimal route of a certain type will then be the shortest path on the graph for that type.

So there are two main parts to the CycleStreets routing system: (1) Building the graphs (2) Finding the shortest path. The quality and performance of CycleStreets is governed by how well we do 1 and 2 respectively.

The current OpenStreetMap (OSM) map of UK & Ireland contains 2 million streets that pass through 20 million points. Streets are usually represented by their centre line, with nodes at junctions. The characteristics of each street, including for example the type of road, whether it is hilly, has a cycle lane, or is a one-way street are used to measure the suitability for cycling. In graph theory speak, they translate into the cost of an edge.

These costs are measured during our daily translation of OSM's UK & Ireland map into a graph by application of a series of rules.

That system is currently rather more complex and opaque than we'd like. Choosing the right values for all of those numbers has been an iterative process as we've tuned the routing engine, often in response to our user's feedback.

We need to:

• Review the ruleset, re-examining the assumptions they are based on and the order they are applied
• Make it much clearer to users how the rules have influenced the chosen route (this will confer greater confidence in the generated advice)
• Include additional sources of information (more information to be published soon on this)
• Handle junctions better, which is of particular interest currently.

Here in more detail is discussion on some of these:

Junctions – reducing wiggly routes

Simple graphs constructed from maps of street centre-lines lack are limited in their capacity to express how easy it is to cycle through a road junction. This series of photos introduces the problem.

In essence, the simple graph cannot represent banned turns, and nor can it indicate that a right turn across a busy road might incur quite a wait until it is safe to cross. However, some of the turn delay modelling can be derived automatically, knowing the 'before' and 'after' street types, and the turn angle. We believe that accurately representing that sort of information has the best chance of improving the quality of routes recommended by CycleStreets.

The way this route wiggles on and off Glasgow Road is a good example of this problem. (NB Click on the + button in the top-right corner of the map and switch to the OpenCycleMap view to get a better map background.)

Implementing turn delays at every node presents real challenges in terms of the use of a standard A* routing engine. This is further more difficult given the need to avoid very large amounts of RAM being needed.

Solving this problem is a significant technical challenge. It needs to be transparent so that there is a clear link between each piece of data and each rule used in the solution and the decisions that a knowledgeable cyclist would make. The solution must also be scalable, so that neither the amount of time taken to find a route nor the amount of data required to represent the problem, increase significantly. That will make it attractive and manageable. A solution also needs to avoid creating excessive hardware cost requirements.

Finding the shortest path

Shortest path algorithms are very familiar to computer science students, and there are many well established standard techniques that solve the problem. CycleStreets currently uses the A* algorithm, which is implemented in a combination of a Python program and a C++ module.

The 2 million streets and 20 million points of the map, become 5 million edges, and 4 million vertices in a graph. These are compressed by a non-standard technique, called Cell Optimisation (Cello), into 2 million edges and 1 million vertices.

The Python/C++ program can scan the compressed graph to find a route from Land's End to John O'Groats in 2.1 seconds. The vast majority of routes we're interested in are about 10 miles, which can be solved by this program in milli-seconds.

The process of interpreting the generated route from a list of edges and vertices into an itinerary that includes street names and turn directions – the 'unpacking stage' – and storing in a database takes much longer. Performance seems to vary quite a bit, sometimes its very quick but it can take several seconds to process, even for a typical-sized route.

This issue will grow in significance as the number of users of CycleStreets continues to grow, and as new ways of using the routing system emerge.

We want to make the performance aspect of the routing itself, as well as the 'unpacking' stage, as fast and efficient as possible.

More types of route

There is a growing clamour for many more customisable types of routing. Ultra-quiet routes, routes where there is no dismounting and routes that are indifferent about hills.

We should also consider taking into account intermittent links, such as ferry crossing times, or gates that are closed at night.

Our system uses pre-compiled graphs, so each new routing type potentially means adding a new graph. Ulitmately RAM sizeputs a cap on that approach.

Are you the kind of person who can tackle these interesting problems?

We think that these and other challenges form interesting computer science problems.

Do get in touch if you'd be interested in an informal discussion to discuss things further. A formal job description and other details, including application deadlines and details will be online very shortly.

Fancy taking in an exciting new research project?

Interested in talking about your motivations and experiences of using CycleStreets?

The Ideas in Transit Project at the University of the West of England Bristol is working with CycleStreets to investigate how and why people use CycleStreets and what they think about it.

They are searching for people to help with their research:

We would like to interview you, the users. It would only take around 40 minutes of your time and we could meet you at your place of work or another suitable location (a library, café, etc.), whatever is easiest for you. We will be offering a £20 voucher for Evans Cycles to each participant as a thank you.

If you are interested in taking part, please contact Tilly at Tilly.Line@uwe.ac.uk.

In town somewhere unfamiliar and don’t know how to get home? Want to avoid a hilly area for your cycle journey? Know about main roads but don’t know the quiet route home? Found somewhere that needs cycle parking or infrastructure improvements which you’d like to tell others about?

An iPhone app has been the number-one feature request we’ve received over the past six months. So …

We’re extremely pleased to announce that we’ve obtained significant funding for a full CycleStreets iPhone app, from the Rees Jeffreys Road Fund.

The Rees Jeffreys Road Fund grant is for £5,000, which will be split between mobile development costs and improvements to the core journey planning algorithm/speed to support mobile use. We’re extremely grateful to the Trustees of the Fund for their support – their funding has enabled this much-requested new interface for CycleStreets to come about.

CycleStreets for iPhone will include the Journey Planner, Photomap (including photo upload) and other CycleStreets features.

We are also seeking further funding of £2-5k to cover the remaining costs. This will enable us to add more functionality more quickly, including getting the Photomap into the initial release.

We’ve engaged mobile developer Alan Paxton to carry out this work for us, who is kindly undertaking the Objective-C coding work below a commercial rate.

CycleStreets for iPhone will be released free of charge. (A future version may add paid-for features such as streetname voice emulation which have knock-on costs.)

Here are some early development screenshots!

Other platforms?

We would love to cover other platforms, in particular Android, as soon as possible, although we have no identified funding at present, nor do we have expertise ourselves in the coding required. Development time donations would be welcome from people with knowledge of developing for Android :)

It is also a high priority in our interface development programme to create a generic HTML interface more suitable for mobile devices, i.e. with bigger buttons, a cut-down feature set and quicker downloads. Again, we welcome offers of expertise or coding to help this happen more quickly!

Other mobile apps using CycleStreets routing coming soon!

Some other forthcoming mobile apps will be using CycleStreets routing, via our API – which is really great news! (These will include CycleStreets routing in some form but are not due to feature the Photomap and other parts of CycleStreets.)

Forthcoming apps include:

• The exciting new BikeHub app, which will include a bike shop finder, journey planner and more!
• For London, the London Cycle Hire App, which will help you find one of the 400 cycle docking stations in Central London so you can pick up or drop off a bike – and then plan a cycle journey from there!
• TrackMyJourney, a Java-based app (targeted to Nokia, Sony Ericsson and BlackBerry platforms) for location tracking, map display, navigation and route plotting

If you have an app that would be interested in using our routing, do check out our API pages.

We are working solidly at present to improve the routing speed/resilience and deal with over-wiggly routes. Improvements will be experienced automatically by API users as we roll these improvements out.

Research-based routing

We are partners in a grant bid to one of the UK Research Councils with some academic colleagues in the other place (Oxford!) for a collaborative project to look at cycling habits and data collection to measure behaviour and impact of cycling interventions. We think there is a lot of scope for adaptive routing – a new field for cycling, and this grant bid is something we’re very excited about. It will require a lot more development work than the basic iPhone app outlined above will include. We are hoping to hear back within the next few weeks and have our fingers crossed!