We’ve obtained a £5,000 grant from the Technology Strategy Board’s Innovation Vouchers scheme, to work on some interesting routing challenges to help increase the quality of the routing we can offer.
Our core aim with CycleStreets is to create “routing that thinks like a cyclist”. One of these aspects is the way that cyclists treat junctions and turns, something that is not currently modelled in the engine. Another challenge that the grant can cover is our desire to incorporate changes to OpenStreetMap data into the routing engine shortly after they happen, rather than after a one-day import period. Both of these are challenging in the context of a routing engine that works over a heavily pre-compressed network and in an environment where expansion of hosting capacity is cost-constrained.
We’re therefore looking for someone with a computer science approach (as distinct from purely “web development”) who can work on these interesting challenges. 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 where this is required to implement these changes.
If you are interested to discuss this further, please contact us (by Friday 24th May 2013).
The work must be completed by 31st July 2013, and we are required to work with a company we have not worked with before. The £5,000 includes any VAT we are required to pay by the supplier. The supplier must be a public sector provider or a registered company.
Background info: about our routing engine
The CycleStreets routing system finds, quietest, fastest and balanced cycling routes between two points in the UK (and other countries being added). 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 millions of paths and nodes. 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 data into a graph by application of a series of rules.
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.
