The following tutorial will run you through the steps to setup the core components needed for an opensource routing “solution”. So if you’re like me and have eagerly been awaiting something similar, read on.

The following guide is largely based on the tutorial found at the Cartoweb WIKI and its associated readme. Many thanks need to be directed at the cartoweb developers, in particular Paschain for compiling a working win32 dll and a system than can easily be built upon. Many thanks.

If you would like some background on the djikstra shortest path algorithm try the following resources.

General info
Various C/VB/PHP implementations
Step by step Animation

Lets get started.

1. Download PostgreSQL 8.1 or higher.

The win32 installer is recommended and makes installation easy. A stable PostGIS is included in the installation of PostgreSQL so no more downloads like previous releases I usually include all developer options in the install by habit, this shouldnt be neccessary but just make sure plpgsql language is checked when installing.

2. Download the pgdijkstra package from cartoweb

3. Extract pgdijkstra.dll into X:\..\PostgreSQL\8.1\lib

4. Lets create a new database to hold the routing data ..

createdb -U username dbname
Password:
CREATE DATABASE

5. Time to ensure plpgsql is initialised on our new db

createlang plpgsql -U chris roads

6. Last thing we need to do is insert the new routing functions ..

psql -U chris roads -f “D:\Program Files\PostgreSQL\pgdijkstra\dijkstra.sql”
Password for user chris:
CREATE FUNCTION
CREATE FUNCTION
CREATE FUNCTION
CREATE FUNCTION

psql -U chris roads -f “D:\Program Files\PostgreSQL\pgdijkstra\dijkstra_postgis.sql”
Password for user chris:
CREATE FUNCTION
CREATE FUNCTION
CREATE FUNCTION
CREATE FUNCTION
CREATE TYPE
CREATE FUNCTION
CREATE FUNCTION

Now assuming all the installation went A’ok then its time to start inserting our data and creating the graphs! Again, all credits go to the cartoweb guys, especially Paschain for their hard work. The following steps are reworked from the official readme

7. If you havent already converted your data into a postgis table, lets use shp2pgsql on my road dataset and create a “roads” table. Be prepared to wait a while if its a large dataset while each feature is inserted.

shp2pgsql D:\roads.shp roads > roads.sql

then run the SQL inserts into the db

psql -d roadsdb -f roads.sql

8. If you come from a background used to using web frontends such as phpMyAdmin, id highly suggest installing phpPgAdmin. While the diehards will scoff, it does tend to make handling the usual db functions a lot easier

9. Almost all road datasets wont have the necessary target_id and source_id for the graph creation. Luckily there is a assign_vertex_id function to automatically generate each id from the start and end node of the line string.

Add 3 new columns to your roads table source_id(integer) target_id(integer) if you dont already have similar from/to node columns that you can rename. If you dont, use the following function to generate source/target id’s based on the distance given.

For example, using the below will group all nodes within a distance of 0.1 to the same vertex id. Obviously, depending on your units and accuracy you may wish to drop the number down to something more suitable. The smaller the unit, the longer the procedure will take

SELECT assign_vertex_id(’graph2′, 0.1);

Luckily my road dataset already had such from/to nodes so all was needed was a simple column rename.

10. Now we are ready to begin generating the graph edges and vertices.

SELECT create_graph_tables(’roads’, ‘int4′);

This procedure will create 2 new tables, roads_vertices and roads_edges. If your source and target id’s are not using int4 as a type, you will need to modify the SQL procedure and remove the int4 dependancy. Otherwise, cross your fingers and wait for the tables to be populated.

11. As you can see we need to populating the cost weighting for each edge. There is a update_cost_from_distance function by default that simply calculates the length of the edge and uses this as the weight. Obviously if you would like to formulate a more complex algorithm for your weights such as using distance, road type, speed etc. then you will need to edit this function. Its easy to do so feel free to have a play.

Lets use plain distance for now,

SELECT update_cost_from_distance(’roads’);

12. We’re pretty much done. Time to generate a shortest path! Using shortest_path_as_geometry we can pass the start and end points for our route. The function expects the node target/source id’s from the original roads table. So lets manually select a couple and try running it.

SELECT gid, astext(the_geom) FROM shortest_path_as_geometry(’roads’, 179551, 179681);

You should now be looking at a list of MULTILINESTRING objects which make up the shortest path from your start to end vertex.

13. Visualising your shortest path is the next logical step. There are a number of ways doing this, such as passing the geometry to a vrml/javascript function or rendering it as an image. Luckily Paschain has included an easy way to insert the static path inside a Mapserver layer.

LAYER NAME "route" TYPE LINE STATUS DEFAULT CONNECTIONTYPE postgis CONNECTION "host=localhost dbname=roads user=chris password=pass " DATA "the_geom from (SELECT the_geom, gid from shortest_path_as_geometry('roads', 219102, 183552)) as route using unique gid using srid=-1" TEMPLATE "t" CLASS NAME "0" STYLE SYMBOL "circle" SIZE 7 COLOR 255 255 0 END END END

Please note that this method is very inefficient as each map refresh will recalculate the route and so putting a lot of unnecessary load on the database. Only use this a proof of concept for now

Lets compare the “shortest path” with a common driving directions site, whereis.com.au. As you can see, the route is different purely because of our simple algorithm to generate the weights.

I plan to release some at least two more articles that build on this introduction.The first will investigate how to tweak the weighting algorithm to more closely match the commercial routing option and the second will look at implementing a more dynamic, user friendly javascript option built into Ka-Map.

Stay tuned, hope i havent put too many of you to sleep

Update: Further investigation revealed that my GiST indexes weren’t built correctly and so i have since updated the timings on the postgis results. Thanks to Sean for pointing out my boo boo.

I have noticed a bit of interest especially on PostGIS‘ new implementation of a GiST spatial index to speed up its performance. What i think is lacking is that there is little to no documentation on how “much” faster spatial indexing (not to be confused with attribute indexes) performs.

So here we go, a simple benchmark in less than 15 mins

First up, my datasets. For the base data, i will use the roads dataset from my previous routing article.

The benchmark tests in this case will be a simple, arbitrary bbox on the following datasets interfacing with Mapserver 4.6 (win32).

Word of warning: Please dont take these results as gospel, its merely to highlight the performance differences across the board.

FYI:

• All data is in CRS 4326 (WGS84)
• The timings will be extracted using the debug output from mapserver
• Note the number of features in each query, the first obviously not being very realistic
• A WMS requests are for single layers only with the BBOX values below

1. 115.69402,-32.1273,116.09642,-31.86770 Features: 57564
2. 115.82508,-32.0358,115.93653,-31.97567 Features: 8408
3. 115.81400,-32.0493,115.86604,-32.02131 Features: 1389
4. 115.82171,-32.0405,115.84112,-32.03009 Features: 338

• ^ Created with the standard quadtree sizes determine by the shptree utility
• * Created with “CREATE INDEX roadsindex ON roadsindex USING GIST( the_geom GIST_GEOMETRY_OPS );” as per postgis documentation

I think the table speaks for itself, but im a little bit cautious about drawing too many conclusions. Most people are aware that PostGIS is slower than shapefiles, but thats a given. Most users who use PostGIS are using it for other reasons (such as for its geoprocessing functions).

The PostGIS guys have claimed about a 10% performance loss over shapefiles. In this little test it was indeed more than this, but i have no doubts that in the hands of a more experienced postGIS expert that they could certainly narrow down the gap further.
Fact of the matter is, spatial indexing is an important part of performance optimisation but should be considered with other methods such as view scale limiting, simplified symbolisation and feature generalisation. Unfortunately i dont have access to a mapserver hooked up with ArcSDE 9 or Oracle Spatial … could of made things interesting

Please, i make no attempts at claiming i am the master of all that is postgis and mapserver. If there is something glaringly obvious that i did not configure or did not include, please let me know and i will be happy to update the results.

Paul Spencer at DMSolutions has posted their latest demonstration of KA-Map which uses AJAX-esque technology to transform mapserver output into a tiled format similar to maps@google but with a lot more features.

Check out the demo site here. It is without a doubt the best demo i have seen showcasing Ka-Map and mapserver’s new WMS support for a time attribute. Excellent stuff … just make sure you press play !

ps. In a somewhat related line, anyone know of any projects working on an opensource routing solution? Let me know