PG Routing Assignment.md

GG618 Routing Algorithm Assignment

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

Credits:

This assignment is mainly based on the following workshop

An Overview about the different tools we are using

Please have a look at the following page to have a grasp about pgrouting

1. Prepare Data

To be able to use pgRouting, data has to be imported into a database.

1.1. Prepare the 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:

1.1.1. Create a pgRouting compatible database

Create the database

Use Postgresql UI to create a new database ccalled city_routing

Enable Postgis and Pgrouting

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

1.2. Get the Workshop Data

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.

1.2.1. Getting the data

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

1.3. Upload data to the database

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 basic cd command here.

1.3.1. Run the osm2pgrouting converter

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. Replace YOURDBPASSWORD with your postgresql password

1.3.2. Tables on the database

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:

1.4 Visualizing Data

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 (id 63672)
• UW university Club (id 16090)
• Fair View Park Map (id 13147)
• Chicopee ski resort (id 15287)

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 

2. Routing

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.

2.1. pgr_dijkstra

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 a SELECT 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 the geometry. 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 (id 63672)
• UW university Club (id 16090)
• Fair View Park Map (id 13147)
• Chicopee ski resort (id 15287)

Get the vertex identifiers

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

2.1.1. Exercise 1: One Pedestrians going to one destination

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 be time, distance or any combination of both or any other attributes or a custom formula.

node and edge results may vary depending on the assignment of the identifiers to the vertices given by osm2pgrouting.

2.1.2. Exercise 2: Many Pedestrians going to the same destination

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

2.1.3. Exercise 3: Many Pedestrians departing from the same location

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

3.1. Routing for vehicles

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 cost attribute

• cost and reverse_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 and reverse_cost do not need to be length; they can be 84c2aa29125fdae1aae0cb25bc0ef2c097e7537e 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;

3.1.1. Exercise 1: Vehicle routing - going

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

3.1.2. Exercise 2: Vehicle routing - returning

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.

3.1.3. Exercise 3: Vehicle routing when time is money

Problem:

From Chicopee ski resort to the WLU Briker Building by taxi.

Solution:

• The vehicle is going from vertex 15287 (line 10) to 63672 (line 11).
• The cost is $100 per hour.
• Use cost_s (line 6) and reverse_cost_s (line 7) columns, which are in unit seconds.
• The duration in hours is cost_s / 3600.
• The cost in $ is cost_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.

4.3. Geometry handling

4.3.1. Route geometry

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 with ST_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 in qgis select db 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;

Questions:

1. 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 and 3.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)

2. Read more about OSM data model and find out the meaning of Node, Way and Relationships Compare them with Point, 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)

3. In the step 1.3.2 we have a term called view. What are the views in the database and what is their use? Write one paragraph about it. (5 marks)

4. 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 a lat and lng value. (5 marks)

Submit your answers in the pdf format in Assignment 1 dropbox in Myls