Greetings Shifters! Today I am going to introduce you to another piece of AWESOME geospatial technology that let’s you compute travel routes on a network – pgRouting. We have it available by default with PostGIS on OpenShift. It adds the capability to take a routable network, a start location, an end location, and then compute the “least cost route” between the two points. There are actually quite a few concepts in that statement to so let’s unpack the statement some more.
Routing is a function of the algorithms + the data you feed it. In terms of the data, you would be wise to heed the old maxim: garbage in = garbage out. I think a lot of people forget that good routing depends on having really good data. For today we are going to use OpenStreetMap data and I describe how to use it for routing more below.
The important part with the network of road data is that it has to have a valid topology. What this basically means is creating the nodes where roads meet and then storing that information in the routing table. There are utilities written to help you create a valid topology from OSM data and other formats(warning – this page is rather old).
For the start and stop points we are going to find nodes (points which form the intersection of road segments) which are closest to where we want to route between. Each segment has a start and an end node and pgRouting uses that information to help compute which path to follow. You will notice I have to use nodes, or maybe coordinates, but not addresses for my start and end points, this is the behavior I have seen in all routing software. To use addresses you actually have to add another layer to our application which is called a geocoder. A geocoder takes an address and turns it into coordinates. Geocoding is actually quite a big and complex topic so, I’m sorry, but we are not going to discuss it today.
Finally there are the functions that use “least cost” to compute the route between the two (or more) nodes. They all try to minimize cost but cost can be anything you want it to be. By default it will use length, but you could make it something like (length * slope), where steeper longer slopes cost more. We are only going to use Dijkstra’s Algorithm today but pgRouting gives numerous other routing options and can even tackle the Traveling Salesman Problem (which you will often see abbreviated TSP). You can also calculate drive time polygons using pgRouting.
pgRouting provides all the functionality you need to create some basic and advanced routing applications. Let’s move on and start working with OpenShift, OSM data, and pgRouting!
Turning pgRouting on in Postgresql and OpenShift
The programming language you choose is up to you, I am going to choose Python, but you must pick Postgresql-9.2. Open a terminal window, change into a directory where you want the resulting git repo to be cloned, and enter the following command:
rhc app create pgrouting python-2.7 postgresql-9
Then cd into the directory on your local machine and do the following set of commands:
rhc ssh psql CREATE EXTENSION POSTGIS; CREATE EXTENSION PGROUTING; \q
Now before you leave your SSH session on your gear do the following commands. We need to note the Postgresql username, password, and port for later (the db name is always the same as the application):
I love Open Street Map (OSM) and I think it’s data is probably the best bike and walk routing database in the world. For vehicle navigation, other than select geographies, I do not think it has enough speed limits, turn restrictions, and direction restrictions to make it completely safe for use. But if all you want to do is put a road network on the map and A) have the ability to update the actual data and B) have with more detail than any current map provider, then OSM is the map data for you.
Go to the Open Street Map site, pan and zoom to an area of roads, trails, and paths you want to use for routing and then click the export button on the top. Then you need to click the big blue Export button.
When you click the Export link, you get a XML file which contains an export of the OSM database for the bounding box you specified (which by default is the current map view). Please realize this file can get quite large quite fast. The area I selected was only about 10 KM x 7 KM with a medium density of features and it was still a 5.8 meg file.
There are several utilities that know how to deal with this XML file but the one we are going to use today is osm2pgrouting. This tool takes the XML files and converts it into pg_routing data.
I built and ran osm2pgrouting on my local machine and generated a SQL file to copy up to my OpenShift gear. It seems that osm2pgrouting needs to connect to the database so there is no way to generate the SQL. Instead I used RHC port-forwarding to allow my machine to talk directly to the Postgresql DB on OpenShift. Here are the commands I ran:
rhc port-forward pgrouting # wait for this to finish and then open another terminal window /usr/share/bin/osm2pgrouting -file map.osm -conf /usr/share/osm2pgrouting/mapconfig.xml -dbname pgrouting -user adminflllllll -passwd Uxxxxxxx -port 5433
The user, passwd, and port are all the values you noted before when we created the application. By default osm2pgrouting uses the ip of 127.0.0.1 which is what port forwarding uses as well. At the end of the command you should see something like this:
... NOTICE: PROCESSING: NOTICE: pgr_createTopology('ways',1e-05,'the_geom','gid','source','target','true') NOTICE: Performing checks, pelase wait ..... NOTICE: Creating Topology, Please wait... NOTICE: 1000 edges processed NOTICE: -------------> TOPOLOGY CREATED FOR 1248 edges NOTICE: Rows with NULL geometry or NULL id: 0 NOTICE: Vertices table for table public.ways is: public.ways_vertices_pgr NOTICE: ---------------------------------------------- Create Topology success ######################### size of streets: 608 size of splitted ways : 1248 finished
We now have a database that is completely routable – winning!
To use the database for routing let’s ssh back into our gear and open a Postgresql prompt.
rhc ssh pgrouting psql
Now let’s do some queries!
The first thing you need to understand is that pgRouting uses the ways table for all it’s calculation, so any queries should be executed against that table. The other thing is that you can only calculate routes from nodes that start or end a way. This means you can’t feed in a latitude and longitude, but instead have to find the closest nodes on a way from your starting and ending location. There is a discussion here in this GIS.stackexchange.com question and it covers some of these topics.
Let’s go ahead and calculate a route between the two blue dots on the map above.
1) Find the node for the eastern and then western blue dot based on it’s coordinates. I created a simple HTML page in Github to have a local web page that let’s me find coordinates – feel free to do with it what you will.
Eastern Dot = 36.94386, -121.85108 Western Dot = 36.95099, -121.86413
2) Now turn those coords into the “id” for the closest nodes.
pgrouting=# select id from ways_vertices_pgr order by st_distance(the_geom, st_setsrid(st_makepoint(-121.85108, 36.94386), 4326)) limit 1; id ----- 747 pgrouting=# select id from ways_vertices_pgr order by st_distance(the_geom, st_setsrid(st_makepoint(-121.86413, 36.95099), 4326)) limit 1; id ----- 311
Now time to calculate our route using Dijkstra’s Algorithm:
pgrouting=# SELECT seq, id1 AS node, id2 AS edge, cost FROM pgr_dijkstra(' pgrouting'# SELECT gid AS id, source::integer, target::integer, length::double precision AS cost FROM ways', pgrouting(# 747, 311, false, false); seq | node | edge | cost -----+------+------+-------------------- 0 | 747 | 1049 | 0.128535373626828 1 | 859 | 1050 | 0.273117500446028 2 | 658 | 1051 | 0.131566903734978 3 | 126 | 1052 | 0.239786823870393 4 | 860 | 1301 | 0.135057011186337 5 | 688 | 1302 | 0.0439222413304197 6 | 118 | 1303 | 0.0988599982373731 7 | 484 | 492 | 0.237091651135357 8 | 486 | 493 | 0.0741267447653214 9 | 38 | 494 | 0.401068970639265 10 | 487 | 495 | 0.489696236362355 11 | 488 | 496 | 0.0314500533578209 12 | 489 | 497 | 0.0237482588687067 13 | 311 | -1 | 0 (14 rows)
Since we specified the length field as the cost of traveling each segment, this means you can sum all the costs to get the total length (in degrees) of the path. You would have to change the projection of the length to a coordinate system that uses Meters or Feet if you want the distances in some other units. This also means you could use a different field for cost, for example, local roads could “cost more” than highways when the algorithm tries to compute distance. The effect of this would be that the even though the distance on the highway might be longer it would be preferred since it “costs less” to travel.
If you want to visualize this you will need to do a join back again to the ways table to select all the edges used. If you already have QGIS installed and talking to your Postgresql DB on OpenShift then you can visualize with a query. Here is a post where I talk a bit about using QGIS unfortunately I don’t cover how to connect it to your PostgreSQL running on OpenShift. You need to use port forwarding, which is covered here. There will be a future blog post on connecting QGIS to both PostGIS and Geoserver on OpenShift.
Here is the query you use to get back the actual geometries for the route.
SELECT * FROM ways JOIN (SELECT seq, id1 AS node, id2 AS edge_id, cost FROM pgr_dijkstra(' SELECT gid AS id, source::integer, target::integer, length::double precision AS cost FROM ways', 747, 311, false, false) ) AS route ON ways.gid = route.edge_id;
And when you put this into the DB Mangager IN QGIS you get a nice line that looks like this:
For the last exercise we are going route between the two green dots on the original map. Note, this will actually route along some paths once we get close to the beach. I am going to put all the code in the block below and then show the final image.
--near the highway pgrouting=# select id from ways_vertices_pgr order by st_distance(the_geom, st_setsrid(st_makepoint(-121.86868, 36.96306), 4326)) limit 1; id ----- 327 --near the beach pgrouting=# select id from ways_vertices_pgr order by st_distance(the_geom, st_setsrid(st_makepoint(-121.88001, 36.95071), 4326)) limit 1; id ----- 923 pgrouting=# SELECT seq, id1 AS node, id2 AS edge, cost FROM pgr_dijkstra(' pgrouting'# SELECT gid AS id, source::integer, target::integer, length::double precision AS cost FROM ways', pgrouting(# 327, 923, false, false); seq | node | edge | cost -----+------+------+-------------------- 0 | 327 | 270 | 0.348741456108403 1 | 328 | 997 | 0.193876573935048 2 | 839 | 999 | 0.336227990537045 3 | 274 | 1000 | 0.191340240373881 4 | 272 | 1001 | 0.0980040773336148 5 | 836 | 993 | 0.215084551516997 6 | 314 | 257 | 0.257117913479673 7 | 313 | 991 | 0.070454539232671 8 | 309 | 252 | 0.281206436783026 9 | 306 | 279 | 0.0955788381320284 10 | 335 | 280 | 0.101469035422479 11 | 336 | 382 | 0.22081578198984 12 | 298 | 242 | 0.212587826544106 13 | 297 | 859 | 0.0788526583865116 14 | 432 | 1379 | 0.0122898531912145 15 | 1007 | 1378 | 0.0189756980021841 16 | 1003 | 1372 | 0.0112055234905677 17 | 1004 | 1381 | 0.0631133444304038 18 | 936 | 1189 | 0.0994512980601248 19 | 796 | 913 | 0.0547520352297354 20 | 797 | 914 | 0.115394853257037 21 | 798 | 916 | 0.0665225070180245 22 | 799 | 1592 | 0.073182033287391 23 | 893 | 1177 | 0.10134436002455 24 | 924 | 1165 | 0.0914773536656268 25 | 921 | 1161 | 0.0142038328282594 26 | 922 | 1162 | 0.246920411218791 27 | 923 | -1 | 0 (28 rows) --to put in QGIS SELECT * FROM ways JOIN (SELECT seq, id1 AS node, id2 AS edge_id, cost FROM pgr_dijkstra(' SELECT gid AS id, source::integer, target::integer, length::double precision AS cost FROM ways', 327, 923, false, false) ) AS route ON ways.gid = route.edge_id;
The dark blue lines are actually footpaths. So this would be the best route to take your bike and board to the beach – surfs up!!!
In this example I just scratched the surface of the functionality that pgRouting brings to the table. As with all the geospatial stuff I have covered, once it is installed and running, using this software on OpenShift is no different than running it on your own servers. All the other examples you find on the web for pgRouting should work just fine on your OpenShift gear.
Some more topics to explore are:
- How to hook the functionality up to a web map. I have given you most of the pieces you need here but there is still some translation work to be done.
- How to return turn by turn directions with pgRouting. I have not covered this at all but I saw some examples out on the web.
Here are some other blogs that talk about pgRouting
- Intro to pgRouting – http://anitagraser.com/2011/02/07/a-beginners-guide-to-pgrouting/
Some content from the BostonGIS group http://www.bostongis.com/blog/index.php?/archives/216-pgRouting-Tutorials-Part-1.html
Working with a beta of Vehicle Route Planning http://blog.georepublic.info/2013/pgrouting-preview-the-new-vrp-solver/
In my geospatial blog series I have covered a lot of server technology. I think my next post in this series will either focus on using QGIS as a desktop application to interact with all these servers OR I will be showing you how to use Hibernate Spatial to interact with PostGIS.
Please leave any feedback or suggestions below. I would love to hear other topics that people would like me to cover.