Build your own routing solution

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.

gid target_id source_id astext
535
178964
179077
MULTILINESTRING((115.929608562 -31.81452766))
661
179216
179154
MULTILINESTRING((115.831206523 -31.87982646))
702
179255
179213
MULTILINESTRING((115.868336883 -31.87188829))
789
179329
179333
MULTILINESTRING((115.895629241 -31.8718535256))

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.

id source target cost reverse_cost
1
1274
1275
NULL
NULL
2
1276
1277
NULL
NULL
3
1278
1279
NULL
NULL

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’);

id source target cost reverse_cost
1
1274
1275
0.000655682025166796
NULL
2
1276
1277
0.00270400042483912
NULL
3
1278
1279
0.00684668815982494
NULL

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 :)

33 thoughts on “Build your own routing solution”

  1. Pingback: Alan's Blogometer
  2. Hi Chris, I was successful duplicating your demo with the routing of PostGIS. But once I tried to skip the step 9 (assign_vertex_id function) since I already have an existing source_id & target_id in my table, once I do the create_graph function, I get errors.

    CONTEXT: SQL statement “CREATE TABLE roads_tmp_edges (id serial, source int, target int, cost float8, reverse_cost float8, UNIQUE (source, target))”
    PL/pgSQL function “create_graph_tables” line 15 at execute statement
    ERROR: cannot EXECUTE a null querystring
    CONTEXT: PL/pgSQL function “create_graph_tables” line 27 at execute statement

  3. aileen, its been a while since i last looked at the code, but if you already have your edge id’s i would look at the SQL to see what format/id the script is looking for. From memory it looks for a specific name with a specific column type.

    Either way, follow through the pl/SQL and you will no doubt find your answer

  4. Hi chris, thanks for your reply. Were you able to use pgdijkstra using one-way roads? How were you able to do it? I understand that the shortest_path function accepts parameters indicating if the path is directed or not. But my dilemma is that the shortest_path function doesn’t output a multi-line string to be used for the data in the route layer. the cartoweb guys said that currently, the shortest_path_to_geometry doesn’t accept parameters like that.

    Any light on this matter?

  5. Unfortunately no Aileen, my routing work was out of pure interest rather than a specific work project.

    Sounds like you will need to edit the sql functions for generating the graph to cater for directional nodes …

  6. Hi Chris:

    I have a question about the function Assign_vertex_id….

    the second parameter exactly how does it works???

    I mean which distance does it measure? which is its utility?
    Does it serve for making connections between disconnected lines?

    thanks for the help.

  7. Yara, from memory the distance parameter allows you to specify an arbritrary “snapping” tolerance around each node.

    eg. If you specify a distance of 10m, the function will assign vertexes from Point A to all other Points within 10m.

    If you data is already networked well, setting this to a very low number won’t cause any problems.

  8. Thanks Chris that was very helpful, I have some tables that have errors in some connections and I was trying to fix that with ArcView to enter them into PostGIS and find the rout but it was a trouble…

    I’m going to try that.
    Thanks for the tip.

  9. Hi Chris,

    my questions are very simple but conceptual.

    1)what will be data structure for my tables. I have two tables roads and nodes in postgresql. i define my structure, if it is wrong can u plz correct it.
    Roads:
    road_id as serial, start_id as int4, target_id as int4, road_length as float8

    nodes:
    node_id as serial, x_value as float8, y_value as float8

    Also nodes and roads have correspondence. i.e if start_id is 546 in road table, it has 546 as node_id in node table with some coordinates.

    is this data structure good to run pgdijkstra module?

    2) where i can find some document that explians how to organize data in pgdijkstra??

    3)let say i have only shape files and arcgis and postgresql on my system. nothing else.
    my task is to run pgdijkstra and show result to my boss on screen.can i find any document that briefly explains all steps how to finish this task.
    I will be grateful if u help me to accomplish this task.

    regards
    @rtist

  10. Hi chris

    Your blog is very helpful.I am a beginner in using postgres and sql. I am having problem at the stage of changing data in the database, i.e. after the data is converted to filename.sql format, you mentioned “type SELEECT….” where do we execute this commands?

    IT will be great if you can help…
    Sasanka

  11. Hi chris,

    Thanks for the blog. I could implement the dijkstra algorithm following the above steps. I was wondering whether you have any idea of similar process for implementing the K-shortest path algorithm for the same dataset.

    Thnaks in Advance,

    Sasanka

  12. hi chris,
    i am a student trying to do route analysis using postgres sql 8.2,postgis 1.2.1 and Quantum gis… i learnt that pgdijkstra module from carto web is need to perform routing. When i tried to download pgdijkstra-win32-1.0.3.tar (for Windows xp) from the cartoweb site (including the link given in your post), i can download.. but i am not able to open the downloaded file.. i ve tried it many times.. can u send me the pgdijkstra module by some means mayb thru email or suggest other links where i could get it.. does downloading cartoweb package help?? please reply…

  13. Suganya, check the postlbs link 1 comment above as that may provide further documentation/help. The tar/zip package should just provide some SQL scripts and the compiled DLL’s.

    Cartoweb will only assist if you’d like to use something that is already integrated. By the sounds of things, you’re a long way away from this step

  14. hey…

    I am a final year computer science student and the university of guyana (south america). I am working on my final project and i am interested in creating a place finder(user enters a location)/routing system (based on two locations entered)–this is something of the sort of mapquest (same idea). The area i am thinking of working on is GEORGETOWN, CAPITAL CITY OF GUYANA.

    I am currently doing research on how to accomplish my tasks using only open source tools.

    If you have info. that can help me accomplish my task please reply.

    Robin.

  15. HI Chris,
    I am a final year MS-IT student. Trying shortest path solution in my road map. I use the query

    select assign_vertex_id(‘roads’,0.00000000000000000000000001);
    I used smallest unit also..

    then i triggered the following quires

    select create_graph_tables(‘roads’,’int4′);
    select update_cost_from_distance(‘roads’);

    but I cannot get the cost column filled can you find me a solution please

  16. Also to note:
    Orkney inc. (www.postlbs.org) improved the routing solution by adding some more shortest path algorithms.
    The 1.0.0 release was just released last week.

    Nicolas

  17. Hi Chris,

    Excellent, clear tutorial!

    All the steps seems to work fine. My confidence dissolve at step 11 when I get the same cost (in reasonable range) for all the route paths in my edges table.

    Also when I run the shortest path function it only works for path 1 to 2 and gives (of course) the cost repeated for all route paths.

    What may be the culprit?

    Schalk

  18. My mistake: My shapefile had ‘gid’ as id column and not ‘id’. Replaced id with gid in update_cost_from_distance function. Cost column in edges table is now correct.

  19. Actual solution :-]

    Give edges table an alias (note alias e) in update_cost_from_distance function:

    EXECUTE ‘UPDATE ‘ || quote_ident(geom_table) ||
    ‘_edges e SET cost = (SELECT sum( length( g.the_geom ) ) FROM ‘ ||
    quote_ident(geom_table) ||
    ‘ g WHERE g.edge_id = e.id GROUP BY e.id)';

  20. hi,

    I have been trying to get the above implementation to work but i am getting the following error at step 6:

    C:\Program Files\PostgreSQL\8.2\bin>psql -U robin roads -f “c:\program files\
    PostgreSQL\pgdijkstra\dijkstra.sql”
    CREATE TYPE
    psql:c:/program files/PostgreSQL/pgdijkstra/dijkstra.sql:32: ERROR: incompatible library “C:/Program Files/PostgreSQL/8.2/lib/libdijkstra.dll”: missing magic block
    HINT: Extension libraries are required to use the PG_MODULE_MAGIC macro.
    CREATE FUNCTION
    CREATE FUNCTION
    CREATE FUNCTION

    At the moment I have PostgreSQL 8.2 and the pgdijkstra package and nothing else. Am i missing anything?

    Can someone who has successfully implemented the algorithm please post all the steps and software used or email me at robinojha@gmail.com.

    thanks in advance,
    Robin

  21. Hii All
    I read the blog in Build your own routing solution
    But there is a problem when i do that ,i get an error on exectuion of dijkstra.sql.
    i get an error as mentioned by robin also above

    C:\Program Files\PostgreSQL\8.2\bin>psql -U robin roads -f “c:\program files\
    PostgreSQL\pgdijkstra\dijkstra.sql”
    CREATE TYPE
    psql:c:/program files/PostgreSQL/pgdijkstra/dijkstra.sql:32: ERROR: incompatible library “C:/Program Files/PostgreSQL/8.2/lib/libdijkstra.dll”: missing magic block
    HINT: Extension libraries are required to use the PG_MODULE_MAGIC macro.
    CREATE FUNCTION
    CREATE FUNCTION
    CREATE FUNCTION

    Please reply if you have found any resolution

    Regards

    Kusum

  22. hi all,
    The error about magic module ocurs in my case too.

    psql:c:/program files/PostgreSQL/pgdijkstra/dijkstra.sql:32: ERROR: incompatible library “C:/Program Files/PostgreSQL/8.2/lib/libdijkstra.dll”: missing magic block
    HINT: Extension libraries are required to use the PG_MODULE_MAGIC macro.

    Can someone tell me what are the extension libraries and if it is the .dll we have it in the postgres installation’s \lib dir already.

    thanks for any help in advance
    nishith

  23. I get an error when calling create_graph_tables;
    ERROR: duplicate key value violates unique constraint “roads_edges_source_key”
    CONTEXT: SQL statement “INSERT INTO roads_edges (id, source, target) VALUES (1393, ‘1550’, ’91’)”
    PL/pgSQL function “create_graph_tables” line 27 at EXECUTE statement

  24. I found the solution:

    You will have to modify dijkstra.c and add the following:

    #ifdef PG_MODULE_MAGIC
    PG_MODULE_MAGIC;
    #endif

    after the include section. Then reinstall the pgdijkstra by executing sudo make install. Finally, restart the postgresql server.

    (yes, i saw you are using the windows version and i am not sure if this appy for windows as well, but… good luck!)

  25. Hi Chris,
    I am developing a routing application using openlayers and postgres. I successfully executed my routing query using dijikstra shortest path. and my query goes like this:
    “SELECT rt.gid as geomId, astext(rt.the_geom) as geometry,rd_name as rd_name,length as len FROM road,(SELECT gid, the_geom FROM dijkstra_sp(‘road’,4352,4052) ) as rt WHERE road.gid=rt.gid;”

    But my dijkstra_sp function [SELECT gid, the_geom FROM dijkstra_sp(‘road’,4352,4052)] returns me a set of geometries of type line string which is not in an order. I am able to draw lines in map using these linestrings but fails to find the direction because the lines are not in sequential order. Is there any other function from which I can get a ordered set of linestring co-ordinates.

    Can you please reply me quickly for my question.

    Thanks in advance.

Comments are closed.