Donate using PayPal

CycleStreets blog

News from CycleStreets

Archive for May, 2011

Hiring soon – to work on routing engine challenges

Saturday, May 21st, 2011

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.

CycleStreets campaigner toolkit bid wins GeoVation contest!

Friday, May 6th, 2011

We’re pleased to announce that our bid, for a comprehensive online campaigning toolkit to assist cycle campaign groups around the UK, is a winner in the GeoVation contest!

It brings £27,000 for the development of a toolkit which, in the words of one supporter, should be “a hugely important step forward for all cycle campaigning groups”.

Turning problem reports into implemented solutions

Our bid was one of 155 ideas submitted to the GeoVation challenge, on the theme of “How can we improve transport in Britain?”. Our bid was shortlisted, and we attended the GeoVation Camp in March to help develop the proposal amongst a total of 30 ideas invited. We were one of the final ten proposals, and took part in a Dragon’s Den -style pitch on Wednesday.

We were delighted to be picked as one of the winners who share the £150k pot of funding.

   

Photos by Ordnance Survey, licenced CC BY-NC 2.0

Martin Lucas-Smith, who presented the bid alongside CycleStreets’ routemaster, Simon Nuttall, said:

“We were delighted to be picked by the Ordnance Survey’s judges as one of the winners. The £27,000 of funding will enable us to get this much-needed project off the ground.

“As a member of one of the many local cycle campaign groups who will benefit, I’m all too aware of the large number of issues on the street network that need improvement, and the difficulty of managing this deluge of problems.

“The new system will help campaigners around the country convert these problem reports into prioritised, well-evidenced solution proposals. It should help them work more productively with local councils to see changes implemented.”

We’d like to thank all the groups who provided quotes of support for our bid, including the CTC, Cyclenation, London Cycling Campaign, and a variety of groups around the country. We’re working to provide you with a really great, useful and user-friendly system that will save a lot of time and effort.

Some of the things the new system will be able to do are:

  • Enable members of the public and campaigners easily to pinpoint where cycling is difficult
  • Help groups prioritise what to work on
  • Pull in planning application data automatically, so that potential issues needing attention are readily accessible
  • Automatically notify and involve people who cycle through an area – who therefore have an interest in seeing issues fixed
  • Make geographical data such as collision data and accessibility analysis easily available, to provide context
  • Enable simpler and more focussed discussion based on specific issues, groups of issues, or themes
  • Enable best practice to be ‘pulled-in’ to discussions, by providing off-the-shelf examples shared from elsewhere in the UK
  • Enable groups to include LA contacts in these discussions if they wish
  • Enable groups to assemble ‘solution’ resources so that problems can be resolved on the ground
  • Give groups a variety of ways of publishing their activity on their website easily.

GeoVation is run by the Ordnance Survey, and uses funding from the Technology Strategy Board and Ideas In Transit, and the Department for Transport. It runs challenges to address specific needs within communities, which may be satisfied in part through the use of geography.

We’ll have more details soon about the next steps. As the plans develop, we’ll be issuing calls for comments from groups in the cycling community, before we start with any coding.

We’re delighted also that MySociety’s strong bid for a mobile version of their forthcoming FixMyTransport was another winner – congratulations to them!

We welcome your feedback, especially to report bugs or give us route feedback.

My comments relate to: *






Your comments: *
URL of page: * https://www.cyclestreets.net/footer.html
How did you find out about CycleStreets?:
Your name:
Our ref: Please leave blank - anti-spam measure

* Items marked with an asterisk [*] are required fields and must be fully completed.