Bienvenue sur PostGIS.fr

Bienvenue sur PostGIS.fr , le site de la communauté des utilisateurs francophones de PostGIS.

PostGIS ajoute le support d'objets géographique à la base de données PostgreSQL. En effet, PostGIS "spatialise" le serverur PostgreSQL, ce qui permet de l'utiliser comme une base de données SIG.

Maintenu à jour, en fonction de nos disponibilités et des diverses sorties des outils que nous testons, nous vous proposons l'ensemble de nos travaux publiés en langue française.

source: trunk/workshop-routing-foss4g/chapters/shortest_path.rst @ 73

Revision 73, 15.1 KB checked in by djay, 10 years ago (diff)

Traduction du chapitre 8

RevLine 
[63]1==============================================================================================================
[73]2Plus courts chemins
[63]3==============================================================================================================
4
[73]5pgRouting été initialement appelé *pgDijkstra*, puisque il implémentait seulement la recherche de plus court chemin à l'aide de l'agorithme de *Dijkstra*. Plus tard, d'uatres fonctions se sont ajoutées et la bibliotÚque fut renommée.
[63]6
7.. image:: images/route.png
8        :width: 250pt
9        :align: center
10       
[73]11Ce chapitre explique les trois différents algorithmes et les attributs nécessaires.
[63]12
13
14.. note::
15
[73]16        Si vous lancez l'outils :doc:`osm2pgrouting <osm2pgrouting>` pour importer des données *OpenStreetMap*, la table des chemins (``ways``) contient déjà tout les attributs nécessaires pour utiliser les fonctions de recherche de plus court chemins. Au contraire, la table ``ways`` de la base de données ``pgrouting-workshop`` du :doc:`chapitre précédent <topology>` manque d'un certain nombre d'attributs, qui sont présentés dans ce chapitre dans les **Prérequis**.
[63]17
18
19-------------------------------------------------------------------------------------------------------------
20Dijkstra
21-------------------------------------------------------------------------------------------------------------
22
[73]23L'algorithme de Dijkstraa été la premiÚre implémentation disponible dans pgRouting. Il ne nécessite pas d'autre attributs que les champs ``source`` et ``target``, les attributs ``id`` et ``cost``. Il peut être utilisé sur des graphes orientés ou non. Vous pouvez spécifier que votre réseau à un coût de ``parcours inverse`` (``reverse cost``) ou non.
[63]24
[73]25.. rubric:: Prérequis
[63]26
[73]27Pour être en mesure d'utiliser un coût de parcuors invers, vous devez ajouter une colonne de coût. Nous pouvons affecter la longuer au coût de parcours inverse.
[63]28
29.. code-block:: sql
30
31        ALTER TABLE ways ADD COLUMN reverse_cost double precision;
32        UPDATE ways SET reverse_cost = length;
33
[73]34.. rubric:: Fonction avec paramÚtres
[63]35
36.. code-block:: sql
37
38        shortest_path( sql text,
39                           source_id integer,
40                           target_id integer,
41                           directed boolean,
42                           has_reverse_cost boolean )
43
44.. note::
45
[73]46        * Les identifiant pour source et target sont les identifiant des noeuds.
47        * Graphes non-orientés ("directed=false") implique que le paramÚtre "has_reverse_cost" est ignoré
[63]48
49
50^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
[73]51Bases
[63]52^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
53
[73]54Chaque algorithme a une fonction de *base*.
[63]55
56.. code-block:: sql
57
58        SELECT * FROM shortest_path('
59                        SELECT gid as id,
60                                 source::integer,
61                                 target::integer,
62                                 length::double precision as cost
63                                FROM ways',
64                        5700, 6733, false, false);
65
66.. code-block:: sql
67
68         vertex_id | edge_id |        cost         
69        -----------+---------+---------------------
70              5700 |    6585 |   0.175725539559539
71              5701 |   18947 |   0.178145491343884
72              2633 |   18948 |   0.177501253416424
73               ... |     ... |                 ...
74              6733 |      -1 |                   0
75         (38 rows)
76
77
78^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
79Wrapper
80^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
81
82.. rubric:: Wrapper WITHOUT bounding box
83
84Wrapper functions extend the core functions with transformations, bounding box limitations, etc.. Wrappers can change the format and ordering of the result. They often set default function parameters and make the usage of pgRouting more simple.
85
86.. code-block:: sql
87
88        SELECT gid, AsText(the_geom) AS the_geom
89                FROM dijkstra_sp('ways', 5700, 6733);
90               
91.. code-block:: sql
92               
93          gid   |                              the_geom     
94        --------+---------------------------------------------------------------
95           5534 | MULTILINESTRING((-104.9993415 39.7423284, ... ,-104.9999815 39.7444843))
96           5535 | MULTILINESTRING((-104.9999815 39.7444843, ... ,-105.0001355 39.7457581))
97           5536 | MULTILINESTRING((-105.0001355 39.7457581,-105.0002133 39.7459024))
98            ... | ...
99          19914 | MULTILINESTRING((-104.9981408 39.7320938,-104.9981194 39.7305074))
100        (37 rows)
101
102
103.. note::
104
105        It's possible to show the route in QGIS. It works for shortest path queries that return a geometry column.
106
107        * Create a database connection and add the "ways" table as a background layer.
108        * Add another layer of the "ways" table but select ``Build query`` before adding it.
109        * Type ``"gid"  IN ( SELECT gid FROM dijkstra_sp('ways',5700,6733))`` into the **SQL where clause** field.
110       
111        ``SQL query`` can be also selected from the layer context menu.
112
113       
114.. rubric:: Wrapper WITH bounding box
115
116You can limit your search area by adding a bounding box. This will improve performance especially for large networks.
117
118.. code-block:: sql
119
120        SELECT gid, AsText(the_geom) AS the_geom
121                FROM dijkstra_sp_delta('ways', 5700, 6733, 0.1);
122               
123.. code-block:: sql
124
125          gid   |                              the_geom     
126        --------+---------------------------------------------------------------
127           5534 | MULTILINESTRING((-104.9993415 39.7423284, ... ,-104.9999815 39.7444843))
128           5535 | MULTILINESTRING((-104.9999815 39.7444843, ... ,-105.0001355 39.7457581))
129           5536 | MULTILINESTRING((-105.0001355 39.7457581,-105.0002133 39.7459024))
130            ... | ...
131          19914 | MULTILINESTRING((-104.9981408 39.7320938,-104.9981194 39.7305074))
132        (37 rows)
133
134.. note:: 
135
136        The projection of OSM data is "degree", so we set a bounding box containing start and end vertex plus a ``0.1`` degree buffer for example.
137
138
139-------------------------------------------------------------------------------------------------------------
140A-Star
141-------------------------------------------------------------------------------------------------------------
142
143A-Star algorithm is another well-known routing algorithm. It adds geographical information to source and target of each network link. This enables the shortest path search to prefer links which are closer to the target of the search.
144
145.. rubric:: Prerequisites
146
147For A-Star you need to prepare your network table and add latitute/longitude columns (``x1``, ``y1`` and ``x2``, ``y2``) and calculate their values.
148
149.. code-block:: sql
150
151        ALTER TABLE ways ADD COLUMN x1 double precision;
152        ALTER TABLE ways ADD COLUMN y1 double precision;
153        ALTER TABLE ways ADD COLUMN x2 double precision;
154        ALTER TABLE ways ADD COLUMN y2 double precision;
155       
156        UPDATE ways SET x1 = x(ST_startpoint(the_geom));
157        UPDATE ways SET y1 = y(ST_startpoint(the_geom));
158       
159        UPDATE ways SET x2 = x(ST_endpoint(the_geom));
160        UPDATE ways SET y2 = y(ST_endpoint(the_geom));
161       
162        UPDATE ways SET x1 = x(ST_PointN(the_geom, 1));
163        UPDATE ways SET y1 = y(ST_PointN(the_geom, 1));
164       
165        UPDATE ways SET x2 = x(ST_PointN(the_geom, ST_NumPoints(the_geom)));
166        UPDATE ways SET y2 = y(ST_PointN(the_geom, ST_NumPoints(the_geom)));
167
168.. Note:: 
169
170        ``endpoint()`` function fails for some versions of PostgreSQL (ie. 8.2.5, 8.1.9). A workaround for that problem is using the ``PointN()`` function instead:
171
172
173.. rubric:: Function with parameters
174
175Shortest Path A-Star function is very similar to the Dijkstra function, though it prefers links that are close to the target of the search. The heuristics of this search are predefined, so you need to recompile pgRouting if you want to make changes to the heuristic function itself.
176
177.. code-block:: sql
178
179        shortest_path_astar( sql text,
180                           source_id integer,
181                           target_id integer,
182                           directed boolean,
183                           has_reverse_cost boolean )
184
185.. note::
186        * Source and target IDs are vertex IDs.
187        * Undirected graphs ("directed false") ignore "has_reverse_cost" setting
188
189^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
190Core
191^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
192
193.. code-block:: sql
194
195        SELECT * FROM shortest_path_astar('
196                        SELECT gid as id,
197                                 source::integer,
198                                 target::integer,
199                                 length::double precision as cost,
200                                 x1, y1, x2, y2
201                                FROM ways',
202                        5700, 6733, false, false);
203               
204.. code-block:: sql
205               
206         vertex_id | edge_id |        cost         
207        -----------+---------+---------------------
208              5700 |    6585 |   0.175725539559539
209              5701 |   18947 |   0.178145491343884
210              2633 |   18948 |   0.177501253416424
211               ... |     ... |                 ...
212              6733 |      -1 |                   0
213         (38 rows)
214
215
216^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
217Wrapper
218^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
219
220.. rubric:: Wrapper function WITH bounding box
221
222Wrapper functions extend the core functions with transformations, bounding box limitations, etc..
223
224.. code-block:: sql
225
226        SELECT gid, AsText(the_geom) AS the_geom
227                FROM astar_sp_delta('ways', 5700, 6733, 0.1);
228
229.. code-block:: sql
230
231          gid   |                              the_geom     
232        --------+---------------------------------------------------------------
233           5534 | MULTILINESTRING((-104.9993415 39.7423284, ... ,-104.9999815 39.7444843))
234           5535 | MULTILINESTRING((-104.9999815 39.7444843, ... ,-105.0001355 39.7457581))
235           5536 | MULTILINESTRING((-105.0001355 39.7457581,-105.0002133 39.7459024))
236            ... | ...
237          19914 | MULTILINESTRING((-104.9981408 39.7320938,-104.9981194 39.7305074))
238        (37 rows)
239
240       
241.. note::
242
243        * There is currently no wrapper function for A-Star without bounding box, since bounding boxes are very useful to increase performance. If you don't need a bounding box Dijkstra will be enough anyway.
244        * The projection of OSM data is "degree", so we set a bounding box containing start and end vertex plus a 0.1 degree buffer for example.
245
246
247-------------------------------------------------------------------------------------------------------------
248Shooting-Star
249-------------------------------------------------------------------------------------------------------------
250
251Shooting-Star algorithm is the latest of pgRouting shortest path algorithms. Its speciality is that it routes from link to link, not from vertex to vertex as Dijkstra and A-Star algorithms do. This makes it possible to define relations between links for example, and it solves some other vertex-based algorithm issues like "parallel links", which have same source and target but different costs.
252
253.. rubric:: Prerequisites
254
255For Shooting-Star you need to prepare your network table and add the ``rule`` and ``to_cost`` column. Like A-Star this algorithm also has a heuristic function, which prefers links closer to the target of the search.
256
257.. code-block:: sql
258
259        -- Add rule and to_cost column
260        ALTER TABLE ways ADD COLUMN to_cost double precision;   
261        ALTER TABLE ways ADD COLUMN rule text;
262
263.. rubric:: Shooting-Star algorithm introduces two new attributes
264
265.. list-table::
266   :widths: 10 90
267
268   * - **Attribute**
269     - **Description**
270   * - rule
271     - a string with a comma separated list of edge IDs, which describes a rule for turning restriction (if you came along these edges, you can pass through the current one only with the cost stated in to_cost column)
272   * - to_cost
273     - a cost of a restricted passage (can be very high in a case of turn restriction or comparable with an edge cost in a case of traffic light)
274
275.. rubric:: Function with parameters
276
277.. code-block:: sql
278
279        shortest_path_shooting_star( sql text,
280                           source_id integer,
281                           target_id integer,
282                           directed boolean,
283                           has_reverse_cost boolean )
284
285.. note::
286
287        * Source and target IDs are link IDs.
288        * Undirected graphs ("directed false") ignores "has_reverse_cost" setting
289
290To describe turn restrictions:
291
292.. code-block:: sql
293
294         gid | source | target | cost | x1 | y1 | x2 | y2 | to_cost | rule
295        -----+--------+--------+------+----+----+----+----+---------+------
296          12 |      3 |     10 |    2 |  4 |  3 |  4 |  5 |    1000 | 14
297 
298... means that the cost of going from edge 14 to edge 12 is 1000, and
299
300.. code-block:: sql
301
302         gid | source | target | cost | x1 | y1 | x2 | y2 | to_cost | rule
303        -----+--------+--------+------+----+----+----+----+---------+------
304          12 |      3 |     10 |    2 |  4 |  3 |  4 |  5 |    1000 | 14, 4
305
306... means that the cost of going from edge 14 to edge 12 through edge 4 is 1000.
307
308If you need multiple restrictions for a given edge then you have to add multiple records for that edge each with a separate restriction.
309
310.. code-block:: sql
311
312         gid | source | target | cost | x1 | y1 | x2 | y2 | to_cost | rule
313        -----+--------+--------+------+----+----+----+----+---------+------
314          11 |      3 |     10 |    2 |  4 |  3 |  4 |  5 |    1000 | 4
315          11 |      3 |     10 |    2 |  4 |  3 |  4 |  5 |    1000 | 12
316
317... means that the cost of going from either edge 4 or 12 to edge 11 is 1000. And then you always need to order your data by gid when you load it to a shortest path function..
318
319
320^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
321Core
322^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
323
324An example of a Shooting Star query may look like this:
325
326.. code-block:: sql
327
328        SELECT * FROM shortest_path_shooting_star('
329                        SELECT gid as id,
330                                 source::integer,
331                                 target::integer,
332                                 length::double precision as cost,
333                                 x1, y1, x2, y2,
334                                 rule, to_cost
335                                FROM ways',
336                        6585, 8247, false, false);
337
338.. code-block:: sql
339
340         vertex_id | edge_id |        cost
341        -----------+---------+---------------------
342             15007 |    6585 |   0.175725539559539
343             15009 |   18947 |   0.178145491343884
344              9254 |   18948 |   0.177501253416424
345               ... |     ... |   ...
346              1161 |    8247 |   0.051155648874288
347         (37 rows)
348
349.. warning::
350
351        Shooting Star algorithm calculates a path from edge to edge (not from vertex to vertex). Column vertex_id contains start vertex of an edge from column edge_id.
352
353
354^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
355Wrapper
356^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
357
358Wrapper functions extend the core functions with transformations, bounding box limitations, etc..
359
360.. code-block:: sql
361
362        SELECT gid, AsText(the_geom) AS the_geom
363                FROM shootingstar_sp('ways', 6585, 8247, 0.1, 'length', true, true);
364
365.. code-block:: sql
366
367          gid   |                              the_geom     
368        --------+---------------------------------------------------------------
369           6585 | MULTILINESTRING((-104.9975345 39.7193508,-104.9975487 39.7209311))
370          18947 | MULTILINESTRING((-104.9975487 39.7209311,-104.9975509 39.7225332))
371          18948 | MULTILINESTRING((-104.9975509 39.7225332,-104.9975447 39.7241295))
372            ... | ...
373           8247 | MULTILINESTRING((-104.9978555 39.7495627,-104.9982781 39.7498884))
374        (37 rows)
375
376.. note::
377
378        There is currently no wrapper function for Shooting-Star without bounding box, since bounding boxes are very useful to increase performance.
379
380.. warning::
381
382        The projection of OSM data is "degree", so we set a bounding box containing start and end vertex plus a 0.1 degree buffer for example.
Note: See TracBrowser for help on using the repository browser.