Tue, 2012/01/24 - 22:31 — laurent
## Building the Graph

## Routing

This post is the logical following of the previous post concerning creating a geospacial database from the OpenStreetMap OSM files. The next logical step is to create a routing function (the classic “from to”) by using the data uploaded in the previous post.

For this post, I have redesigned the OSM loader:

This loader now includes a post processing phase which constructs the routing matrix from the uploaded data. The routing matrix is a table named “path” which contains all the cost in seconds of going from one intersection to another. The path table only contains the cost of two directly connected nodes. An auxiliary table named “intersection” allows mapping a matrix row/column to a specific node id:

` `

In term of graph, the intersection table contains the list of vertices and the path contains the edge between each node.

In the OpenStreetMap database, the “way” references of lot of different concept. Here we are interested only on roads that could be used by cars. For this, we need to select ways containing a “highway” or a “junction” tag. If the way is a highway, the tag must reference a road usable by a car (not a track or a cycle lane).

To speed up the performance, the matrix builder creates a road table that contains all the roads from the list of ways:

` `

The “max speed” column of the Road table is computed in KPH by using the provided “maxspeed” tag or by using a predefined table on the highway type.

Once the list of road is defined, the first step of the matrix construction is to detect all nodes which are part of at least 2 roads or junctions. The easiest way is to simply expand the previous SQL statement and use an auto-join:

` `

The OSM loader uses this statement to directly construct the intersection table in just one query.

The second phase is to construct the matrix itself. For that, the loader needs to detect all the edge of the vertices defined in the intersection tables. This can also be done in just one SQL statement:

` `

This query returns all the elements needed to build the matrix:

WayID is the way identifier. LeftPos and RightPos reference the index in the WayNODE table of the “from” (left) and “to” (right) nodes. Oneway indicates if the road is one way. In this case, leftPos must be lower than rightPos. Highway indicates the road category. At the end leftIdx and rightIdx indicate the row/column index in the matrix.

The next step is to calculate the weight of the edge. For that the uploader simply uses the wayid, leftpos and rightpos columns. This is done in just one SQL statement:

` `

The loader calculates the distance between each selected point and compute the total distance in kilometre. The distance is converted in seconds by using the maxspeed already calculated when populating the road table. The resulting value is saved in the matrix as the weight between two edges.

Because this method uses the different indexes created during the upload phase, the different SQL statements perform well even on very large map (I have successfully tested them on the map of UK). Also they require little memory during the processing allowing the loader to work on large databases.

The classic algorithm for searching the shortest path in a graph is the Dijkstra’s algorithm. The problem is Dijkstra analyse each nodes by their distance with the start point. On a map, this means that Dijkstra will analyse each node in concentric circle around the start point even if this make little sense on the routing point of view.

The A* algorithm is a derivate from the original Dijkstra which adds an extra heuristic score for each node in order to offer a better prioritization of the graph exploration. For the routing, a classic way is to calculate the flying distance between the node and the goal. As our weights in the charts are expressed in seconds, the distance is divided by the average speed of all the roads crossing at the node. This makes nodes relaying motorways more attractive than nodes relaying local streets.

The result is quite dramatic in term of reduction of time spent during the graph exploration:

The last improvement is to run 2 A* search in parallel: one from start point to the end point and one in reverse. The path is found when a node is present in the two completed node list.

Attachment | Size |
---|---|

OSMUpload.zip | 5.09 MB |

MapRoutingDemo.zip | 2.79 MB |