Contents:
Plug-in routing
Summary of how OSM data becomes routing data
- Map data is imported from OSM (openstreetmap) and used to construct vertex and edge tables in the CycleStreets database. (Edges and Vertices are the classic terminology used in graph theory.)
- The cost of travelling along an edge is known as the weighting. To accommodate a range of route types, each edge has a set of weightings. There are weightings for the length, time, busyness and balanced measures, corresponding to the shortest, fastest, quietest and balanced route types. The weigtings of all the edges for all the route types are all calculated during the import.
- The whole import currently lasts 12 hours. The result is a set of database tables consuming 4.5 GB that repesent routing graphs for each route type.
- The goal of the journey planning engine is to find the shortest total weighting between any two vertices for a given route type, as fast as possible (ideally less than a second for routes of up to 50km).
Parts 1-3 of this diagram show how an OpenStreetMap is converted into structures for routing in CycleStreets. Part 4 shows the additional structure that needs to be re-created to plan routes between arbitary start and finish points.
Interfacing to other routing engines
That graph is stored in these two main database tables:
- Vertices
- These are stored in a spatially indexed table and contain fields for longitude, latitude and elevation of the vertex.
- Edges
- These are also stored in a table that has a spatial index. The important fields are the startVertexId and finishVertexId, which refer to the vertices. For each route type there's a weighting for travelling along that edge in each direction. For example for the shortest routes, the weighting is 'length', which records the distance in metres for travelling along the edge in one direction. There's also the 'antiLength', which measures the distance in the opposite direction. These are usually the same, but a value of 0 in the antiLenth field would indicate a one-way street. The anti-fields are usually quite different for the fastest routes, where the weightings measure time in seconds. For an edge that represents a two-way street that goes up hill, the values of 'time' and 'antiTime' could, for example, be 50 seconds to ride up, and 10 seconds to come down.
The route type defines which of the set of weightings from the edges table to use.
Join to the Graph
The start and finish points of a journey are not usually at a vertex. This is because vertices only occur at junctions, bends or at the ends of ways. In those cases, CycleStreets interpolates the streets and generates extra temporary vertices at the start and finish points. It creates extra temporary edges that link those vertices to the permanent vertices of the graph.
The plug-in router should be designed to handle these extra temporary additions to the permanent network, for routing.
It is possible for the plug-in to work out those extra temporary vertices and edges itself. However, to do that effectively it would need access to the OSM tables so that it could interpolate the streets itself. A further issue is that CycleStreets uses a routing structure compression technology, called Cello. The effect of that is to reduce the number of edges and vertices by pre-tightening the network. The local network around the start and finish points has to be restored in order to guarantee the best route will be found. A plug-in wouldn't know how Cello had compressed the network. This is the other main reason why it should not get involved in creating the additional temporary links.
CycleStreets stores the routing information in MySQL tables. They may not be stored in the most useful format for a plugin.
Calling the Plug in Search
The parameters passed in to the plug in search include:
- start vertex
- finish vertex
- routing dimension - i.e. which set of edge weightings will be used.
- additional temporary vertices and edges - tuples describing the vertices and edges.
- other options - these are performance settings for the routing engine.
The returned values:
- The distance travelled
- Whether a route was found
- Whether a list of the edges was compiled successfully
- Other detail - such as what engine algorithms were used.
