In this assginment we are going to use Pgrouting
to compare multiple routing algorithems and also learn how the roads graphs are being stored in the database
This assignment is mainly based on the following workshop
Please have a look at the following page to have a grasp about pgrouting
To be able to use pgRouting, data has to be imported into a database.
pgRouting is installed as extension on Postgis. This requires:
- Supported PostgreSQL version
- Supported PostGIS version
These requirements are met on your Postgresql instalation. When the required software is installed, open PGAdmin and follow these steps:
Use Postgresql UI to create a new database ccalled city_routing
Run the following queris in the new database.
-- add PostGIS functions
CREATE EXTENSION postgis;
-- add pgRouting functions
CREATE EXTENSION pgrouting;
-- View pgRouting version
SELECT pgr_version();
Note The output of
pgr_version()
can be different from what is shown here
The pgRouting workshop will make use of OpenStreetMap data, which is already available on a service called Geofabrik [https://www.geofabrik.de]. We will use the Waterloo
city data and is a snapshot of August 2022. You should pick a city of your own. Make sure select a small city since it impacts the processing time on your machine.
Navigate to the http://overpass-turbo.eu
and zoom to the city of your choise. Type the following query in the left side text box
node({{bbox}});way(bn);
( ._; >; );
out;
Then click export and chose raw data directly from Overpass API
it will open a new tab and a new file will be downloaded for you.
Create a folder (lets say C:\osm_data
) and copy the downloaded file there. You can rename it to city_name.osm
(in this example waterloo.osm
)
In this step we used Overpass API
to download raw osm data. Additional information about Overpass API is available here
The next step is to run osm2pgrouting
converter, which is a command line tool that inserts the data in the database, ready
to be used with pgRouting
. Additional information about osm2pgrouting can be found here
For this step:
- the osm2pgrouting default mapconfig.xml (available under PostgreSQL installation path) configuration file is used
- and the
C:\osm_data\waterloo.osm
data - with the
city_routing
database
From the start menu open terminal (type cmd
in the search bar and run it as Administrator) and navigate to postgresql folder. To navigate you can use the following command
cd /d "C:\Program Files\PostgreSQL\14\bin"
Note Change
C:\Program Files\PostgreSQL\14\bin
to the proper path depending to your postgresql instalation. Learn more about basiccd
command here.
osm2pgrouting -f "C:\osm_data\waterloo.osm" -c "mapconfig.xml" -d city_routing -U postgres -W YOURDBPASSWORD
Note: If you have installed postgresql on different port add
-p 5433
to the end of the command above.5433
is the new port which postgresql is using. ReplaceYOURDBPASSWORD
with your postgresql password
To see the tables which are imported into the database right click on the database name in the pgadmin
and then select generate ERD
. it will create an ERD from the imported data.
Optional You can also follow the same process and this time click on the PSQL Tool
and then in the new window type \d
to see the list of the tables and views in the database.
Alternatively you can check the Tables
sub-tree and see the tables you created during the process. If everything went well the result should look like this:
In order to have a better grasp of our data we usin QGIS
to visualize data from postgresql database. You can download Qgis from the following website (https://www.qgis.org/en/site/forusers/download.html). Download QGIS and install it on your machines. Once it is installed open it and in the left navigation bar select Postgresql
and right click on it and select new Connection
fill the required information same as the following image. This form asks you for the information about your database server to connecto to. Make sure to insert your password correctly and check store
checkboxes in front of the fields. The username of your postgresql instalation is postgres
and the port should be 5432
unless you changed it during instalation process of the postgresql.
Click test connection
to make sure you inserted everything correctly and then click ok
. Your database connection is added there under Pgrouting
name. double click on it and then double click on ways_vertices_pgr
and it will be added to QGIS. you can see the set of the vertexes in the table.
Note: If you want to add a base map to your map you need to install
QuickMapServices
plugin to the qgis. Refer to this youtube clip to learn how to install a plugin to qgis. Follow this link to learn more about installing this plugin.
Lets find a few nodes near some points of intrests (POI). In my dataset I want to find WLU Briker Building
, UW university Club
, Fair View Park Map
and Chicopee ski resort
. Write down the id of each node near the selected POI. Make sure to select at least 4 locations.
WLU Briker Building
(id63672
)UW university Club
(id16090
)Fair View Park Map
(id13147
)Chicopee ski resort
(id15287
)
Now Add ways
table from your database connection to the qgis. select one of the lines and check its attributes. Try to check the values in the source
and targer
columns and match them with the id
attribute from the nodes (ways_vertices_pgr
table ) at two ends of each way object.
You can also visialuze data using pgAdmin by running the following query. However, due to the limitations with the UI it does no allow you to load the entire dataset into the map
SELECT * FROM public.ways_vertices_pgr
ORDER BY id ASC
pgRouting was first called pgDijkstra
, because it implemented only shortest path search with Dijkstra
algorithm. Later other functions were added and the library was renamed to pgRouting.
Dijkstra algorithm was the first algorithm implemented in pgRouting. It doesn’t require other attributes than id
, source
and target
ID and cost
and reverse_cost
. You can specify when to consider the graph as directed
or undirected
. Read the documentation page to figure out about the pgr_dijkstra
function in the database.
Signature Summary
pgr_dijkstra(Edges SQL, start_vid, end_vid [, directed])
pgr_dijkstra(Edges SQL, start_vid, end_vids [, directed])
pgr_dijkstra(Edges SQL, start_vids, end_vid [, directed])
pgr_dijkstra(Edges SQL, start_vids, end_vids [, directed])
pgr_dijkstra(Edges SQL, Combinations SQL [, directed])
RETURNS SET OF (seq, path_seq [, start_vid] [, end_vid], node, edge, cost, agg_cost)
OR EMPTY SET
Description of the parameters can be found in pgr_dijkstra.
Note 1: Many pgRouting functions have
sql::text
as one of their arguments. While this may look confusing at first, it makes the functions very flexible as the user can pass aSELECT statement
as function argument as long as the returned result contains the required number of attributes and the correct attribute names. Note 2: Most of pgRouting implemented algorithms do not require thegeometry
. Note 3: The pgRouting functions do not return a geometry, but only an ordered list of nodes or edges.
Identifiers for the Queries
The assignment of the vertices identifiers on the source and target columns may be different, the following exercises will use the results of our previous step.
WLU Briker Building
(id63672
)UW university Club
(id16090
)Fair View Park Map
(id13147
)Chicopee ski resort
(id15287
)
SELECT osm_id, id FROM ways_vertices_pgr
WHERE id IN (63672, 16090, 13147, 15287)
ORDER BY osm_id;
osm_id | id |
---|---|
1136516956 | 13147 |
1575027136 | 15287 |
1606967619 | 16090 |
7751996285 | 63672 |
Problem:
Walking from WLU Briker Building
to the UW university Club
.
From the |place_1| to the |place_1|
Solution:
Check the following query. The pedestrian wants to go from vertex 63672
to vertex 16090
(lines 9 and 10 in the sql query bellow).The pedestrian’s cost is in terms of length
. In this case length (line 6), which was calculated by osm2pgrouting
, is in unit degrees
. From a pedestrian perspective the graph is undirected
(line 11), that is, the pedestrian can move in both directions on all segments.
SELECT * FROM pgr_dijkstra(
'
SELECT gid AS id,
source,
target,
length AS cost
FROM ways
',
63672,
16090,
directed := false);
Modify your query based on your numbers and run it. you should see a table like this
seq | path_seq | node | edge | cost | agg_cost |
---|---|---|---|---|---|
1 | 1 | 63672 | 77168 | 9.051729116529995e-05 | 0 |
2 | 2 | 63671 | 77171 | 0.00019852742883585286 | 9.051729116529995e-05 |
3 | 3 | 63675 | 77163 | 0.00023085636226948333 | 0.0002890447200011528 |
4 | 4 | 63668 | 77162 | 0.00017765989981117253 | 0.0005199010822706362 |
Note: The returned cost attribute represents the cost specified in the inner SQL query (edges_sql::text argument). In this example cost is length in unit
degrees
. Cost may betime
,distance
or any combination of both or any other attributes or acustom formula
.
node and edge results may vary depending on the assignment of the identifiers to the vertices given by
osm2pgrouting
.
Problem:
Walking from the UW university Club
and Fair View Park Map
to the Chicopee ski resort
.
From |place_1| and |place_2| to |place_3|
Solution:
The pedestrians are departing at vertices 16090 and 13147 (line 9). All pedestrians want to go to vertex 15287 (line 10). The cost to be in meters using attribute length_m
(line 6).
SELECT * FROM pgr_dijkstra(
'
SELECT gid AS id,
source,
target,
length_m AS cost
FROM ways
',
ARRAY[16090,13147],
15287,
directed := false);
Problem:
Walking from the UW university Club
to Fair View Park Map
and Chicopee ski resort
.
Solution:
All pedestrians are departing from vertex 16090 (line 9). Pedestrians want to go to locations 13147 and 15287 (line 10). The cost to be in seconds, with a walking speed s = 1.3
m/s and t = d/s
(line 6).
SELECT * FROM pgr_dijkstra(
'
SELECT gid AS id,
source,
target,
length_m / 1.3 AS cost
FROM ways
',
16090,
ARRAY[13147,15287],
directed := false);
A query for vehicle routing generally differs from routing for pedestrians:
-
The road segments are considered directed
-
Costs can be: ...Distance ...Time ...Euros ...Pesos ...Dollars ...CO2 emissions, etc.
-
The
reverse_cost
attribute must be taken into account on two way streets. -
The
costs
should have the same units as the costattribute
-
cost
andreverse_cost
values can be different, Due to the fact that there are roads that are one way -
Depending on the geometry, the valid way:
...(source, target) segment IF cost >= 0 AND reverse_cost < 0
...(target, source) segment IF cost < 0 AND reverse_cost >= 0
-
A wrong way is indicated with a negative value and is not inserted in the graph for processing.
-
Two way roads ...IF
cost >= 0 AND reverse_cost >= 0
and their values can be different. For example, it is faster going down hill on a sloped road. In general,cost
andreverse_cost
do not need to be length; they can be84c2aa29125fdae1aae0cb25bc0ef2c097e7537e
almost anything, for example time, slope, surface, road type, etc., or they can be a combination of multiple parameters.
The following queries indicate the number of road segments, where a one-way
rule applies:
Number of (source, target) segments with cost < 0
(line 3).
SELECT count(*)
FROM ways
WHERE cost < 0;
Number of (target, source) segments with reverse_cost < 0
(line 3).
SELECT count(*)
FROM ways
WHERE reverse_cost < 0;
Problem:
From the WLU Briker Building
to the Chicopee ski resort
by car.
Solution:
The vehicle is going from vertex 63672
(line 10) to 15287
(line 11). Use cost (line 6) and reverse_cost (line 7) columns, which are in unit degrees.
SELECT * FROM pgr_dijkstra(
'
SELECT gid AS id,
source,
target,
cost,
reverse_cost
FROM ways
',
63672,
15287,
directed := true);
Problem:
From Chicopee ski resort
to the WLU Briker Building
by car.
Solution:
The vehicle is going from vertex 15287
(line 10) to 63672
(line 11). Use cost (line 6) and reverse_cost (line 7) columns, which are in unit degrees.
SELECT * FROM pgr_dijkstra(
'
SELECT gid AS id,
source,
target,
cost,
reverse_cost
FROM ways
',
15287,
63672,
directed := true);
Note: On a directed graph, going and coming back routes, most of the time are different.
Problem:
From Chicopee ski resort
to the WLU Briker Building
by taxi.
Solution:
- The vehicle is going from vertex
15287
(line 10) to63672
(line 11). - The
cost
is $100 per hour. - Use
cost_s
(line 6) andreverse_cost_s
(line 7) columns, which are in unitseconds
. - The
duration
in hours iscost_s / 3600
. - The
cost
in $ iscost_s / 3600 * 100.
SELECT * FROM pgr_dijkstra(
'
SELECT gid AS id,
source,
target,
cost_s / 3600 * 100 AS cost,
reverse_cost_s / 3600 * 100 AS reverse_cost
FROM ways
',
15287,
63672);
Note: Comparing with Vehicle routing - returning:
- The total number of records are identical.
- The node sequence is identical.
- The edge sequence is identical.
- The cost and agg_cost results are directly proportional.
Problem : Routing from WLU Briker Building
to the UW university Club
. Additionally we want to get the geometry in human readable form.
Solution: Check the following query. the_geom
in human readable form named as route_readable
Tip : WITH provides a way to write auxiliary statements in larger queries. It can be thought of as defining temporary tables that exist just for one query.
Solution
The query from Exercise 1: Testing the views for routing used as a subquery named results this time in a WITH clause. (lines 2 to 6)
The SELECT clause contains:
- All the columns of results. (line 8)
- The
the_geom
processed withST_AsText
to get the human readable form. (line 9) - Renames the result to route_readable
- LEFT JOIN with
ways
. (line 11)
WITH results AS (
SELECT seq, edge AS gid, cost AS seconds FROM pgr_dijkstra(
'
SELECT gid AS id,
source,
target,
cost / 3600 * 100 AS cost,
reverse_cost
FROM ways
',
63672,
16090,
directed := true)
)
SELECT
results.*,
ST_AsText(the_geom) AS route_readable
FROM results
LEFT JOIN ways
USING (gid)
ORDER BY seq;
In Order to view the route in qgis follow these steps
- In the
Database
menu inqgis
selectdb manager ...
- Select your database connection
- Click new query window from top left toolbar
- Modify query bellow (change node ids) and then copy and paste you modified query from to the text box
- Fill the form as it is shown in the image
- click load
WITH results AS (
SELECT seq, edge AS gid, cost AS seconds FROM pgr_dijkstra(
'
SELECT gid AS id,
source,
target,
cost / 3600 * 100 AS cost,
reverse_cost
FROM ways
',
63672,
16090,
directed := true)
)
SELECT
results.*,
the_geom AS route_geometry
FROM results
LEFT JOIN ways
USING (gid)
ORDER BY seq;
-
Follow these steps in part 4 and visualize all of the quries you from each part
2.1.1
,2.1.2
,2.1.3
,3.1.1
,3.1.2
and3.1.3
and export an image for each of the queires. Per each part you just need to run one query. In total of 6 exports should be provided (12 marks) -
Read more about OSM data model and find out the meaning of
Node, Way and Relationships
Compare them withPoint, Polygon and line
objects. Write one paragraph about it and also show the type of the relation between those entities (one-to-one, many-to-one and so on). (8 marks) -
In the step
1.3.2
we have a term calledview
. What are theviews
in the database and what is their use? Write one paragraph about it. (5 marks) -
In section
Visualizing Data
we manually found the node id. Write a simple sql query to find the closest node id to a point from alat
andlng
value. (5 marks)
Submit your answers in the pdf
format in Assignment 1
dropbox in Myls