PgRouting

Z FreeGIS portál
Přejít na: navigace, hledání
Pgrouting.png

pgRouting je rozšíření pro PostGIS určené pro síťové analýzy. V současnosti jsou implementovány následující síťové analýzy:

  • Vyhledání nejkratší cesty
  • Problém obchodního cestujícího
  • Dojezdová vzdálenost

Vytvoření geodatabáze, nahrání funkcí pgRouting

Informace ohledně vytvoření PostGIS geodatabáze najdete zde.

Příklad nahrání funkcí pgRouting do databáze 'template_routing'

psql template_routing -f /usr/share/pgrouting/routing_core.sql
psql template_routing -f /usr/share/pgrouting/routing_core_wrappers.sql
psql template_routing -f /usr/share/pgrouting/routing_topology.sql

Testcase 1 (workshop FOSS4G 2011)

Tento text čerpá z FOSS4G routing with pgRouting tools, OpenStreetMap road data and GeoExt (2011). Příklady jsou upraveny město Praha.

Vstupní data

Můžeme stáhnout originální data z workshopu a nebo si připravit vlastní dataset, zde je příklad pro město Praha.

Stažení originálních dat workshopu

git clone https://github.com/pgRouting/workshop.git pgrouting-workshop
cd pgrouting-workshop
tar xvzf data.tar.gz

Následující příkaz vytvoří databázi 'pgrouting-workshop' jako kopii databáze 'template_routing' a nahraje do této databáze cvičná data.

psql template_routing -f data/sampledata_notopo.sql
psql pgrouting-workshop
 SELECT * from geometry_columns;
  f_table_catalog   | f_table_schema | f_table_name | f_geometry_column | coord_dimension | srid |      type       
--------------------+----------------+--------------+-------------------+-----------------+------+-----------------
 pgrouting-workshop | public         | ways         | the_geom          |               2 | 4326 | MULTILINESTRING

Stažení OSM dat (Praha)

Nejprve zjistíme minimální ohraničující obdélník (bbox) Prahy.

psql pgis_student -c"SELECT ST_Extent(ST_Transform(geom, 4326)) FROM gis1.obce WHERE nazev = 'Praha'"
                                st_extent                                
-------------------------------------------------------------------------
 BOX(14.2253523853741 49.9423178052737,14.7065714274832 50.177370950699)
(1 row)

Data stáhneme přes API OpenStreetMap

 wget --progress=dot:mega -O praha.osm \
  http://www.informationfreeway.org/api/0.6/map?bbox=14.2253523853741,49.9423178052737,14.7065714274832,50.177370950699

Alternativně lze data stáhnout ze serveru 'Cloudmade'

wget --progress=dot:mega http://download.cloudmade.com/europe/eastern_europe/czech_republic/prague/prague.osm.bz2

Data naimportujeme do databáze pomocí aplikace osm2pgrouting

bzip2 -d prague.osm.bz2
osm2pgrouting -file prague.osm -conf /usr/share/osm2pgrouting/mapconfig.xml -dbname pgis_routing -clean -user postgis

Přístup k datům

Cvičná data jsou také součástí cvičné databáze PostGIS pgis_student, schéma 'routing'.

SET search_path TO routing,public;
\dt routing.
          List of relations
 Schema  |  Name   | Type  | Owner 
---------+---------+-------+-------
 routing | classes | table | landa
 routing | types   | table | landa
 routing | ways    | table | landa
(3 rows)

Databáze obsahuje pouze jednu "feature-table"

SELECT f_table_name,type,srid FROM geometry_columns  WHERE f_table_schema = 'routing';
 f_table_name |      type       | srid 
--------------+-----------------+------
 ways         | LINESTRING      | 4326
(1 row)

Náhled na data

SELECT gid,class_id,length,name,st_geometrytype(the_geom) FROM ways WHERE gid = 1;
 gid | class_id |      length       | name | st_geometrytype 
-----+----------+-------------------+------+-----------------
   1 |      101 | 0.182682884421833 |      | ST_LineString
SELECT * FROM classes WHERE id = 101;
id      | 101
type_id | 1
name    | motorway
cost    | 

Vytvoření topologie sítě

CREATE TABLE ways AS SELECT w.*,c.name AS class_name FROM routing.ways AS w JOIN classes AS c ON class_id = id;
SELECT gid, class_id, class_name, length, name, st_geometrytype(the_geom) AS type from ways limit 1;
gid        | 302
class_id   | 102
class_name | footway
length     | 0.0714603355500818
name       | 
type       | ST_MultiLineString
ALTER TABLE ways ADD COLUMN source integer;
ALTER TABLE ways ADD COLUMN target integer;
SELECT assign_vertex_id('ways', 0.00001, 'the_geom', 'gid');
CREATE INDEX source_idx ON ways("source");
CREATE INDEX target_idx ON ways("target");
SELECT gid, class_id, length, name, st_geometrytype(the_geom) AS type,source,target FROM ways WHERE gid = 1;
gid      | 1
class_id | 101
length   | 0.182682884421833
name     | 
type     | ST_LineString
source   | 33
target   | 34

Vyhledání nejkratší cesty

Dijkstra

Vyhledání nejkratší cesty na základě Dijkstrova algoritmu. První implementovaný algoritmus pro PgRouting. Lze použít pro orientované či neorientované hrany. Vyžaduje pouze informace o uzlech.

shortest_path(sql text,                 -- SQL dotaz
              source_id integer,        -- id počátečního uzlu
	      target_id integer,        -- id koncového uzlu
	      directed boolean,         -- orientovaný/neorientovaný graf
	      has_reverse_cost boolean  -- náklady v opačném směru definovány/nededinovány)

Nalezení nejkratší cesty z bodu '10' do bodu '20' (neorientované hrany, délka hrany).

SELECT * FROM shortest_path('SELECT gid as id,source,target,length as cost from ways', 10, 20, false, false);
 vertex_id | edge_id |        cost         
-----------+---------+---------------------
        10 |   14701 |   0.133961657579708
      1034 |     974 |  0.0433580404548831
...
      6749 |    8014 |  0.0518861583127315
      6750 |    8015 |  0.0518860343451018
        20 |      -1 |                   0
(50 rows)

Alternativně lze použít funkci dijkstra_sp (wrapper pro shortest_path).

SELECT gid, ST_AsText(the_geom) AS geom FROM dijkstra_sp('ways', 10, 20);
   974 | MULTILINESTRING((-104.9740756 39.7255831,-104.9740817 39.7251932))
   973 | MULTILINESTRING((-104.9740814 39.7272791,-104.9740756 39.7255831))
 11107 | MULTILINESTRING((-104.9781265 39.7520022,-104.9781346 39.7526951))
 11108 | MULTILINESTRING((-104.9781346 39.7526951,-104.9781265 39.7531137))
  8012 | MULTILINESTRING((-104.981101 39.7571413,-104.981529 39.7574721))
(49 rows)

Nejkratší cestu vytvoříme dotazem.

CREATE TABLE sp10_20 AS SELECT gid, the_geom FROM dijkstra_sp('ways', 10, 20);

A-Star

Vyhledání nejkratší cesty na základě A-Star algoritmu.

Tabulka hran musí obsahovat informace o souřadnicích počátečních a koncových uzlů.

ALTER TABLE ways ADD COLUMN x1 double precision;
ALTER TABLE ways ADD COLUMN y1 double precision;
ALTER TABLE ways ADD COLUMN x2 double precision;
ALTER TABLE ways ADD COLUMN y2 double precision;

UPDATE ways SET x1 = st_x(st_startpoint(the_geom));
UPDATE ways SET y1 = st_y(st_startpoint(the_geom));
UPDATE ways SET x2 = st_x(st_endpoint(the_geom));
UPDATE ways SET y2 = st_y(st_endpoint(the_geom));
SELECT gid, st_astext(the_geom), x1, y1, x2, y2 FROM ways WHERE gid = 1;
gid       | 1
st_astext | LINESTRING(-105.0155597 39.7339973,...,-105.0158228 39.7323669)
x1        | -105.0155597
y1        | 39.7339973
x2        | -105.0158228
y2        | 39.7323669
shortest_path_astar(sql text,           -- SQL dotaz 
              source_id integer,        -- id počátečního uzlu
	      target_id integer,        -- id koncového uzlu
	      directed boolean,         -- orientovaný/neorientovaný graf
	      has_reverse_cost boolean  -- náklady v opačném směru definovány/nededinovány)
SELECT * FROM shortest_path_astar(
 'SELECT gid as id,source,target,length as cost,x1,y1,x2,y2 from ways',
 10, 20, false, false);
 vertex_id | edge_id |        cost         
-----------+---------+---------------------
        10 |   14701 |   0.133961657579708
      1034 |     974 |  0.0433580404548831
...
      6749 |    8014 |  0.0518861583127315
      6750 |    8015 |  0.0518860343451018
        20 |      -1 |                   0

Alternativně lze použít funkci astar_sp_delta (wrapper pro shortest_path_astar).

SELECT gid, ST_AsText(the_geom) AS the_geom
  FROM astar_sp_delta('ways', 10, 20, 0.1);

Shooting-Star

Vyhledání nejkratší cesty na základě Shooting-Star algoritmu. Tento algoritmus na rozdíl od Dijkstrova či A-Star algoritmu vypočítává nejkratší cestu ze spojnice hran nikoliv z uzlů. Tento přístup umožňuje zachytit vztahy mezi hranami, rovnoběžnost hran a pod.

Algoritmus vyžaduje existenci sloupce 'reverse_cost' a 'to_cost'.

ALTER TABLE ways ADD COLUMN reverse_cost double precision;
UPDATE ways SET reverse_cost = length;

ALTER TABLE ways ADD COLUMN to_cost double precision;
ALTER TABLE ways ADD COLUMN rule text;
shortest_path_shooting_star(sql text,                 -- SQL dotaz 
                            source_id integer,        -- id počátečního uzlu
                  	    target_id integer,        -- id koncového uzlu
	                    directed boolean,         -- orientovaný/neorientovaný graf
	                    has_reverse_cost boolean  -- náklady v opačném směru definovány/nededinovány)
SELECT * FROM shortest_path_shooting_star(
 'SELECT gid as id,source,target,length as cost,x1,y1,x2,y2,rule,to_cost from ways',
 8015, 14701, false, false);
SELECT gid, ST_AsText(the_geom) AS the_geom
  FROM shootingstar_sp('ways', 8015, 14701, 0.1, 'length', true, true);

Testcase 2 (workshop FOSS4G 2008)

Tento text čerpá z FOSS4G routing with pgRouting tools and OpenStreetMap road data (2008).

Vstupní data

Testovací data jsou dostupná z

git clone https://github.com/pgRouting/workshop-2008.git workshop-2008

Nahrajeme testovací data.

cd workshop-2008
psql pgis2_routing -f Data/ways_without_topology.sql
\d ways
           Table "public.ways"
  Column  |       Type       | Modifiers 
----------+------------------+-----------
 gid      | integer          | not null
 length   | double precision | 
 name     | character(200)   | 
 the_geom | geometry         | 
Indexes:
    "ways_pkey" PRIMARY KEY, btree (gid)
Check constraints:
    "enforce_dims_the_geom" CHECK (ndims(the_geom) = 2)
    "enforce_geotype_the_geom" CHECK (geometrytype(the_geom) = 'MULTILINESTRING'::text OR the_geom IS NULL)
    "enforce_srid_the_geom" CHECK (srid(the_geom) = 4326)

Dále vytvoříme topologii sítě.

ALTER TABLE ways ADD COLUMN source integer;
ALTER TABLE ways ADD COLUMN target integer;
SELECT assign_vertex_id('ways', 0.00001, 'the_geom', 'gid');

Funkce assign_vertex_id() vytvoří tabulku s uzly ('vertices_tmp').

\d vertices_tmp
                           Table "public.vertices_tmp"
  Column  |   Type   |                         Modifiers                         
----------+----------+-----------------------------------------------------------
 id       | integer  | not null default nextval('vertices_tmp_id_seq'::regclass)
 the_geom | geometry | 
Indexes:
    "vertices_tmp_idx" gist (the_geom)
Check constraints:
    "enforce_dims_the_geom" CHECK (st_ndims(the_geom) = 2)
    "enforce_geotype_the_geom" CHECK (geometrytype(the_geom) = 'POINT'::text OR the_geom IS NULL)
    "enforce_srid_the_geom" CHECK (st_srid(the_geom) = 4326)

Doplníme indexy.

CREATE INDEX source_idx ON ways(source);
CREATE INDEX target_idx ON ways(target);
CREATE INDEX geom_idx ON ways USING GIST(the_geom GIST_GEOMETRY_OPS);
\d ways
           Table "public.ways"
  Column  |       Type       | Modifiers 
----------+------------------+-----------
 gid      | integer          | not null
 length   | double precision | 
 name     | character(200)   | 
 the_geom | geometry         | 
 source   | integer          | 
 target   | integer          | 
Indexes:
    "ways_pkey" PRIMARY KEY, btree (gid)
    "geom_idx" gist (the_geom)
    "source_idx" btree (source)
    "target_idx" btree (target)
Check constraints:
    "enforce_dims_the_geom" CHECK (ndims(the_geom) = 2)
    "enforce_geotype_the_geom" CHECK (geometrytype(the_geom) = 'MULTILINESTRING'::text OR the_geom IS NULL)
    "enforce_srid_the_geom" CHECK (srid(the_geom) = 4326)

Vyhledání nejkratší cesty

Dijkstra

Vyhledání nejkratší cesty na základě Dijkstrova algoritmu. První implementovaný algoritmus pro PgRouting. Lze použít pro orientované či neorientované hrany. Vyžaduje pouze informace o uzlech.

shortest_path(sql text,                 -- SQL dotaz
              source_id integer,        -- id počátečního uzlu
	      target_id integer,        -- id koncového uzlu
	      directed boolean,         -- orientovaný/neorientovaný graf
	      has_reverse_cost boolean  -- náklady v opačném směru definovány/nededinovány)

Nalezení nejkratší cesty z bodu '10' do bodu '20' (neorientované hrany, délka hrany).

SELECT * FROM shortest_path('SELECT gid as id,source,target,length as cost from ways', 10, 20, false, false);
 vertex_id | edge_id |        cost         
-----------+---------+---------------------
        10 |     293 |  0.0059596293824534
         9 |    4632 |  0.0846731039249787
      4067 |    4633 |  0.0765635090514303
      2136 |    4634 |  0.0763951531894937
      1936 |    4635 |  0.0750311256021923
      1867 |    4636 |  0.0724897276707373
      4218 |    4637 | 0.00909269800649229
...
      1806 |     762 |  0.0551912469872652
      1805 |     761 |  0.0305298478239596
        20 |      -1 |                   0

Funkce dijkstra_sp vrací informaci o geometrii nejkratší cesty.

SELECT gid, ST_AsText(the_geom) AS the_geom FROM dijkstra_sp('ways', 10, 20);
  293 | MULTILINESTRING((18.4074149 -33.9443308,18.4074019 -33.9443833))
 4632 | MULTILINESTRING((18.4074149 -33.9443308,18.4077388 -33.9436183))
 4633 | MULTILINESTRING((18.4077388 -33.9436183,18.4080293 -33.9429733))
 4634 | MULTILINESTRING((18.4080293 -33.9429733,18.4083191 -33.9423297))
 4635 | MULTILINESTRING((18.4083191 -33.9423297,18.4085881 -33.9416929))
 4636 | MULTILINESTRING((18.4085881 -33.9416929,18.4088787 -33.9410872))
 4637 | MULTILINESTRING((18.4088787 -33.9410872,18.4089132 -33.9410106))
...
  762 | MULTILINESTRING((18.4241422 -33.9179275,18.4237423 -33.9182966))
  761 | MULTILINESTRING((18.4243523 -33.9177154,18.4241422 -33.9179275))

Nejkratší cestu vytvoříme dotazem.

CREATE TABLE sp10_20 AS SELECT gid, the_geom FROM dijkstra_sp('ways', 10, 20);
SELECT Populate_Geometry_Columns('sp10_20'::regclass);

A-Star

Vyhledání nejkratší cesty na základě A-Star algoritmu.

Tabulka hran musí obsahovat informace o souřadnicích počátečních a koncových uzlů.

ALTER TABLE ways ADD COLUMN x1 double precision;
ALTER TABLE ways ADD COLUMN y1 double precision;
ALTER TABLE ways ADD COLUMN x2 double precision;
ALTER TABLE ways ADD COLUMN y2 double precision;

UPDATE ways SET x1 = x(startpoint(the_geom));
UPDATE ways SET y1 = y(startpoint(the_geom));
UPDATE ways SET x2 = x(endpoint(the_geom));
UPDATE ways SET y2 = y(endpoint(the_geom));
shortest_path_astar(sql text,           -- SQL dotaz 
              source_id integer,        -- id počátečního uzlu
	      target_id integer,        -- id koncového uzlu
	      directed boolean,         -- orientovaný/neorientovaný graf
	      has_reverse_cost boolean  -- náklady v opačném směru definovány/nededinovány)
SELECT * FROM shortest_path_astar(
 'SELECT gid as id,source,target,length as cost,x1,y1,x2,y2 from ways',
 10, 20, false, false);
 vertex_id | edge_id |        cost         
-----------+---------+---------------------
        10 |     293 |  0.0059596293824534
         9 |    4632 |  0.0846731039249787
      4067 |    4633 |  0.0765635090514303
      2136 |    4634 |  0.0763951531894937
      1936 |    4635 |  0.0750311256021923
      1867 |    4636 |  0.0724897276707373
      4218 |    4637 | 0.00909269800649229
...
      1806 |     762 |  0.0551912469872652
      1805 |     761 |  0.0305298478239596
        20 |      -1 |                   0
SELECT gid, AsText(the_geom) AS the_geom
  FROM astar_sp_delta('ways', 10, 20, 0.1);
 gid  |          the_geom                                                                           
------+------------------------------------------------------------------
  293 | MULTILINESTRING((18.4074149 -33.9443308,18.4074019 -33.9443833))
 4632 | MULTILINESTRING((18.4074149 -33.9443308,18.4077388 -33.9436183))
 4633 | MULTILINESTRING((18.4077388 -33.9436183,18.4080293 -33.9429733))
 ...
 6618 | MULTILINESTRING((18.4236514 -33.9182429,18.4237423 -33.9182966))
  762 | MULTILINESTRING((18.4241422 -33.9179275,18.4237423 -33.9182966))
  761 | MULTILINESTRING((18.4243523 -33.9177154,18.4241422 -33.9179275))
(62 rows)

Shooting-Star

Vyhledání nejkratší cesty na základě Shooting-Star algoritmu. Tento algoritmus na rozdíl od Dijkstrova či A-Star algoritmu vypočítává nejkratší cestu ze spojnice hran nikoliv z uzlů. Tento přístup umožňuje zachytit vztahy mezi hranami, rovnoběžnost hran a pod.

Algoritmus vyžaduje existenci sloupce 'reverse_cost' a 'to_cost'.

ALTER TABLE ways ADD COLUMN reverse_cost double precision;
UPDATE ways SET reverse_cost = length;

ALTER TABLE ways ADD COLUMN to_cost double precision;
ALTER TABLE ways ADD COLUMN rule text;
shortest_path_shooting_star(sql text,                 -- SQL dotaz 
                            source_id integer,        -- id počátečního uzlu
                  	    target_id integer,        -- id koncového uzlu
	                    directed boolean,         -- orientovaný/neorientovaný graf
	                    has_reverse_cost boolean  -- náklady v opačném směru definovány/nededinovány)
SELECT * FROM shortest_path_shooting_star(
 'SELECT gid as id,source,target,length as cost,x1,y1,x2,y2,rule,to_cost from ways',
 293, 761, false, false)
 vertex_id | edge_id |        cost         
-----------+---------+---------------------
      5156 |     293 |  0.0059596293824534
      5157 |     293 |  0.0059596293824534
      5156 |    4632 |  0.0846731039249787
     16346 |    4633 |  0.0765635090514303
     12324 |    4634 |  0.0763951531894937
     11972 |    4635 |  0.0750311256021923
     11847 |    4636 |  0.0724897276707373
     16692 |    4637 | 0.00909269800649229
...
     11746 |     762 |  0.0551912469872652
     11744 |     761 |  0.0305298478239596
SELECT gid, AsText(the_geom) AS the_geom
  FROM shootingstar_sp('ways', 10, 20, 0.1, 'length', true, true);

Testcase 3 (OSM)

Stažení dat OSM a import do geodatabáze

# stažení dat OSM
wget http://download.geofabrik.de/europe/czech-republic-latest.osm.bz2
bzip2 -d czech-republic-latest.osm.bz2
 
# import dat
./osm2pgrouting -file ~/czech-republic-latest.osm -conf mapconfig.xml -dbname pgis_osm_rouring -user landa -passwd ...

Poznámka: Data jsou součástí cvičná databáze PostGIS jako schéma osm_routing.

Vytvoření tématických vrstev

create schema landamar;
set search_path to landamar,osm_routing,osm,public;

create view ways_c as select w.*,c.name as class_name from ways as w join classes as c on class_id = id;
silnice
 create table silnice as select * from ways_c where class_name in
 ('motorway', 'motorway_link',
  'trunk', 'trunk_link',
  'primary', 'primary_link',
  'secondary', 'secondary_link',
  'tertiary', 'tertiary_link');

Související články

Externí odkazy