- 1. Requirements
- 2. Installation
- 3. Create a routing database and load data
- 4. Shortest Path Dijkstra: shortest_path and dijkstra_sp_directed()
- 5. Shortest Path A*: shortest_path_astar() and astar_sp_directed()
- 6. Shortest Path Shooting Star : shortest_path_shooting_star()
- 7. Traveling Sales Person (TSP): tsp_astar_directed()
| Revision History | ||
|---|---|---|
| 2008-07-12 add example for shortest_path and dijkstra_sp_directed and shooting_sp | ||
Important
This is a tutorial about pgrouting on windows. This tutorial has been written by a French guy (not very very good in english...
) Please refer to the documentation for PgRouting at http://pgrouting.postlbs.org for more information.
- A demo for A* is available at http://www.davidgis.fr/test/roads.php. It was done using PHP 5.2 + Ming 0.4.0 beta 5.
- Another example for Shooting Star with turn restrictions is also available at http://www.davidgis.fr/blog/index.php?2008/07/24/349-shooting-star-usage-example-with-turn-restriction
A Flash demo for A* using Ming
You should have the following items
PostgreSQL 8.3.3. You can download it from http://www.postgresql.org;
PostGIS 1.3.3. Once PostgreSQL is installed on your computer, use the Stack Buildder from PostgreSQL.
Download pgrouting 1.02 from http://www.davidgis.fr/download/pgRouting-1.02_pg-8.3.3.zip. Then
Unzip the file
Copy lib and share dir to C:\Program Files\PostgreSQL\8.3
Add C:\Program Files\PostgreSQL\8.3\bin;C:\Program Files\PostgreSQL\8.3\lib at the beginning of your environment variable PATH
Open a DOS shell then
SET PGUSER=postgres cd C:\Program Files\PostgreSQL\8.3\share\contrib createdb -T template_postgis testgis psql -d testgis -f routing_core.sql psql -d testgis -f routing_core_wrappers.sql psql -d testgis -f routing_tsp.sql psql -d testgis -f routing_tsp_wrappers.sql psql -d testgis -f routing_dd.sql psql -d testgis -f routing_dd_wrappers.sql
In the zip file, you will find the file roads.sql. Load it by doing
psql -d testgis -f roads.sql
The table has the following structure
testgis=# \d roads
Table « public.roads »
Colonne | Type | Modificateurs
--------------+------------------+----------------------------------------------------
id | integer | not null default nextval('roads_id_seq'::regclass)
source | integer |
target | integer |
cost | double precision |
reverse_cost | double precision |
oneway | text |
x1 | double precision |
y1 | double precision |
x2 | double precision |
y2 | double precision |
gid | integer | not null
the_geom | geometry |
length | double precision |
rule | text |
to_cost | double precision |
Index :
« roads_pkey » PRIMARY KEY, btree (gid)
« roads_source_key » UNIQUE, btree (source, target)
« roads_source_target_idx » btree (source, target)
Contraintes de vérification :
« 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) = (-1))
Here is the roads' content. I've decided to add the requested fields for the differents kind of functions.
testgis=# SELECT id,source,target,x1,y1,x2,y2,cost,reverse_cost,oneway,length,rule,to_cost from roads order by id;
id | source | target | x1 | y1 | x2 | y2 | cost | reverse_cost | oneway | length | rule | to_cost
----+--------+--------+-------------------+--------------------+-------------------+--------------------+------------------+------------------+--------+------------------+------+--------
1 | 1 | 2 | 1 | 0 | 5 | 0 | 4 | 4 | N | 4 | |
2 | 2 | 3 | 5 | 0 | 5 | 6 | 6 | 6 | N | 6 | |
3 | 4 | 5 | 0 | 7.5 | 3 | 7.5 | 3 | 3 | N | 3 | |
4 | 5 | 3 | 3 | 7.5 | 5 | 6 | 2.91421356237309 | -1 | Y | 2.91421356237309 | |
5 | 3 | 6 | 5 | 6 | 7 | 7.5 | 2.91421356237309 | -1 | Y | 2.91421356237309 | |
6 | 6 | 7 | 7 | 7.5 | 5 | 9 | 2.91421356237309 | -1 | Y | 2.91421356237309 | |
7 | 7 | 5 | 5 | 9 | 3 | 7.5 | 2.91421356237309 | -1 | Y | 2.91421356237309 | |
8 | 6 | 8 | 7 | 7.5 | 11 | 7.5 | 4 | 4 | N | 4 | |
9 | 8 | 9 | 11 | 7.5 | 11 | 11 | 3.5 | 3.5 | N | 3.5 | |
10 | 8 | 10 | 11 | 7.5 | 14 | 7.5 | 3 | 3 | N | 3 | |
11 | 10 | 11 | 14 | 7.5 | 21 | 7.5 | 7 | 7 | N | 7 | |
12 | 10 | 12 | 14 | 7.5 | 14 | 11 | 3.5 | 3.5 | N | 3.5 | |
13 | 12 | 13 | 14 | 11 | 18 | 11 | 4 | 4 | N | 4 | |
14 | 13 | 14 | 18 | 11 | 18 | 13 | 2 | 2 | N | 2 | |
15 | 13 | 15 | 18 | 11 | 20 | 11 | 2 | 2 | N | 2 | |
16 | 15 | 16 | 20 | 11 | 20 | 9 | 2 | 2 | N | 2 | |
17 | 12 | 17 | 14 | 11 | 14 | 13 | 2 | 2 | N | 2 | |
18 | 7 | 18 | 5 | 9 | 8 | 14.5 | 8.5 | 8.5 | N | 8.5 | |
19 | 18 | 19 | 8 | 14.5 | 8 | 18 | 3.5 | 3.5 | N | 3.5 | |
20 | 18 | 20 | 8 | 14.5 | 12 | 14.5 | 4 | 4 | N | 4 | |
21 | 20 | 17 | 12 | 14.5 | 14 | 13 | 2.91421356237309 | -1 | Y | 2.91421356237309 | |
22 | 17 | 21 | 14 | 13 | 16 | 14.5 | 2.98079618907396 | -1 | Y | 2.98079618907396 | |
23 | 21 | 22 | 16 | 14.5 | 15.5 | 15.5 | 1.20710678118655 | -1 | Y | 1.20710678118655 | |
24 | 22 | 23 | 15.5 | 15.5 | 14 | 16 | 1.70710678118655 | -1 | Y | 1.70710678118655 | |
25 | 23 | 20 | 14 | 16 | 12 | 14.5 | 2.91421356237309 | -1 | Y | 2.91421356237309 | |
26 | 23 | 24 | 14 | 16 | 14 | 20 | 4 | 4 | N | 4 | |
27 | 21 | 25 | 16 | 14.5 | 23.5 | 19 | 12 | 12 | N | 12 | |
28 | 22 | 25 | 15.5 | 15.5 | 23.5 | 19 | 9.44974746830583 | 9.44974746830583 | N | 9.44974746830583 | |
29 | 25 | 26 | 23.5 | 19 | 30 | 19 | 6.5 | 6.5 | N | 6.5 | |
30 | 1 | 27 | 1 | 0 | -1.24301510067114 | -2.5522432885906 | 3.61523066112342 | 3.61523066112342 | N | 3.61523066112342 | |
31 | 28 | 29 | -1.48505369127517 | -3.85925167785235 | 4 | -7 | 6.728520725894 | 6.728520725894 | N | 6.728520725894 | |
32 | 30 | 4 | -4 | 4 | 0 | 7.5 | 5.86670129625104 | 5.86670129625104 | N | 5.86670129625104 | |
33 | 31 | 28 | -2.11435402684564 | -3.4719899328859 | -1.48505369127517 | -3.85925167785235 | 0.84274652312971 | -1 | Y | 0.84274652312971 | |
34 | 28 | 27 | -1.48505369127517 | -3.85925167785235 | -1.24301510067114 | -2.5522432885906 | 1.643652980008 | -1 | Y | 1.643652980008 | |
35 | 27 | 31 | -1.24301510067114 | -2.5522432885906 | -2.11435402684564 | -3.4719899328859 | 1.51352166586552 | -1 | Y | 1.51352166586552 | |
36 | 32 | 33 | -5.07865086257376 | 2.26953745529481 | -3.5712446684834 | 2.22091144903383 | 1.73350805494058 | -1 | Y | 1.73350805494058 | |
37 | 33 | 30 | -3.5712446684834 | 2.22091144903383 | -4 | 4 | 1.99498090204589 | -1 | Y | 1.99498090204589 | |
38 | 30 | 32 | -4 | 4 | -5.07865086257376 | 2.26953745529481 | 2.42470775726398 | -1 | Y | 2.42470775726398 | |
39 | 34 | 35 | 16.9050866893397 | 5.03750410181188 | 17.8313340915255 | 4.01375697308019 | 1.73750308554073 | -1 | Y | 1.73750308554073 | |
40 | 35 | 34 | 17.8313340915255 | 4.01375697308019 | 16.9050866893397 | 5.03750410181188 | 2.20661903277814 | -1 | Y | 2.20661903277814 | |
41 | 36 | 31 | -9.0366577181208 | -4.14969798657718 | -2.11435402684564 | -3.4719899328859 | 7.08611544792685 | 7.08611544792685 | N | 7.08611544792685 | |
42 | 1 | 33 | 1 | 0 | -3.5712446684834 | 2.22091144903383 | 5.16592533550955 | 5.16592533550955 | N | 5.16592533550955 | |
43 | 37 | 32 | -11.497283689023 | -0.064510845232198 | -5.07865086257376 | 2.26953745529481 | 7.08935847100446 | 7.08935847100446 | N | 7.08935847100446 | |
44 | 38 | 39 | -7.3154471505788 | -0.210388864015136 | -8.67697532588622 | -1.62054304558353 | 2.81901636360908 | 2.81901636360908 | N | 2.81901636360908 | |
45 | 40 | 39 | -6.92643910049097 | -2.10680310819333 | -8.67697532588622 | -1.62054304558353 | 2.71375967514431 | 2.71375967514431 | N | 2.71375967514431 | |
46 | 41 | 39 | -10.3788855450205 | -2.05817710193235 | -8.67697532588622 | -1.62054304558353 | 1.76395914112196 | 1.76395914112196 | N | 1.76395914112196 | |
47 | 37 | 41 | -11.497283689023 | -0.064510845232198 | -10.3788855450205 | -2.05817710193235 | 2.28593953367386 | 2.28593953367386 | N | 2.28593953367386 | |
48 | 41 | 36 | -10.3788855450205 | -2.05817710193235 | -9.0366577181208 | -4.14969798657718 | 2.48516300274436 | 2.48516300274436 | N | 2.48516300274436 | |
49 | 42 | 43 | 19.1963302631677 | -6.07746472441785 | 19.1963302631677 | -1.00747894403236 | 5.06998578038549 | 5.06998578038549 | N | 5.06998578038549 | |
50 | 44 | 45 | 10.8113537802225 | 2.64876080143794 | 10.8113537802225 | -0.568730174575924 | 3.21749097601387 | 3.21749097601387 | N | 3.21749097601387 | |
51 | 46 | 47 | 7.39886335111687 | 2.84376025452969 | 7.44761321438981 | 0.211267637791074 | 2.63392519805962 | 2.63392519805962 | N | 2.63392519805962 | |
52 | 47 | 45 | 7.44761321438981 | 0.211267637791074 | 10.8113537802225 | -0.568730174575924 | 3.45299104857306 | 3.45299104857306 | N | 3.45299104857306 | |
53 | 48 | 49 | 5.10761977728881 | -3.9324707404086 | 14.8575924318763 | -1.34872798694292 | 13.0297765905234 | 13.0297765905234 | N | 13.0297765905234 | |
54 | 45 | 49 | 10.8113537802225 | -0.568730174575924 | 14.8575924318763 | -1.34872798694292 | 4.12073340722674 | 4.12073340722674 | N | 4.12073340722674 | |
55 | 50 | 51 | 26.8988086602918 | 7.71874658182343 | 28.36130455848 | 3.81875751998844 | 4.63167714107961 | 4.63167714107961 | N | 4.63167714107961 | |
56 | 52 | 53 | 31.0912969017644 | 9.66874111274093 | 31.432545944675 | 4.40375587926369 | 5.29390700081218 | 5.29390700081218 | N | 5.29390700081218 | |
57 | 43 | 54 | 19.1963302631677 | -1.00747894403236 | 28.36130455848 | 3.7700076567155 | 10.3354309080009 | 10.3354309080009 | N | 10.3354309080009 | |
58 | 54 | 53 | 28.36130455848 | 3.7700076567155 | 31.432545944675 | 4.40375587926369 | 3.13594650175355 | 3.13594650175355 | N | 3.13594650175355 | |
59 | 49 | 43 | 14.8575924318763 | -1.34872798694292 | 19.1963302631677 | -1.00747894403236 | 4.35213704724091 | 4.35213704724091 | N | 4.35213704724091 | |
60 | 43 | 35 | 19.1963302631677 | -1.00747894403236 | 17.8313340915255 | 4.01375697308019 | 5.23594066797949 | 5.23594066797949 | N | 5.23594066797949 | |
61 | 10 | 34 | 14 | 7.5 | 16.9050866893397 | 5.03750410181188 | 3.8083349013935 | 3.8083349013935 | N | 3.8083349013935 | |
(61 lignes)Suppose that we want to know what is the best path from source = 26 and target = 39 and vice versa
Here before using our functions, we must take care of the value of field reverse_cost. Indeed reverse_cost must take positive value else PostgreSQL server crash! :(. We can take a expensive value. reverse_cost=1000 should be enough in order to supporting one-way streets.
UPDATE roads SET reverse_cost=1000 WHERE oneway='Y';
We have
source=26 and target = 39
testgis=# SELECT * FROM shortest_path('SELECT id, source, target,x1,y1,x2,y2,cost,reverse_cost from roads',26,39,true,true); vertex_id | edge_id | cost -----------+---------+------------------ 26 | 29 | 6.5 25 | 28 | 9.44974746830583 22 | 24 | 1.70710678118655 23 | 25 | 2.91421356237309 20 | 20 | 4 18 | 18 | 8.5 7 | 7 | 2.91421356237309 5 | 3 | 3 4 | 32 | 5.86670129625104 30 | 38 | 2.42470775726398 32 | 43 | 7.08935847100446 37 | 47 | 2.28593953367386 41 | 46 | 1.76395914112196 39 | -1 | 0 (14 lignes)source=39 and target=26
testgis=# SELECT * FROM shortest_path('SELECT id, source, target,x1,y1,x2,y2,cost,reverse_cost from roads',39,26,true,true); vertex_id | edge_id | cost -----------+---------+------------------ 39 | 46 | 1.76395914112196 41 | 47 | 2.28593953367386 37 | 43 | 7.08935847100446 32 | 36 | 1.73350805494058 33 | 37 | 1.99498090204589 30 | 32 | 5.86670129625104 4 | 3 | 3 5 | 4 | 2.91421356237309 3 | 5 | 2.91421356237309 6 | 8 | 4 8 | 10 | 3 10 | 12 | 3.5 12 | 17 | 2 17 | 22 | 2.98079618907396 21 | 23 | 1.20710678118655 22 | 28 | 9.44974746830583 25 | 29 | 6.5 26 | -1 | 0 (18 lignes)
Let's now see our paths in QGIS
We will create two tables associated to the paths!
BEGIN TRANSACTION;
DROP TABLE IF EXISTS shortest_path_table_1,shortest_path_table_2;
CREATE TABLE shortest_path_table_1(gid int4) with oids;
SELECT AddGeometryColumn( 'shortest_path_table_1', 'the_geom', -1, 'MULTILINESTRING', 2 );
INSERT INTO shortest_path_table_1(the_geom)
SELECT the_geom FROM dijkstra_sp_directed('roads',26,39,true,true);
CREATE TABLE shortest_path_table_2(gid int4) with oids;
SELECT AddGeometryColumn( 'shortest_path_table_2', 'the_geom', -1, 'MULTILINESTRING', 2 );
INSERT INTO shortest_path_table_2(the_geom)
SELECT the_geom FROM dijkstra_sp_directed('roads',39,26,true,true);
END TRANSACTION;Here is the result in QGIS
Let's have a few tests. Here we will use shortest_path_astar().
If (source,target)=(37,43) then
testgis=# SELECT * FROM shortest_path_astar('SELECT id, source, target,x1,y1,x2,y2,cost,reverse_cost from roads',37,43,true,true);
vertex_id | edge_id | cost
-----------+---------+------------------
37 | 43 | 7.08935847100446
32 | 36 | 1.73350805494058
33 | 37 | 1.99498090204589
30 | 32 | 5.86670129625104
4 | 3 | 3
5 | 4 | 2.91421356237309
3 | 5 | 2.91421356237309
6 | 8 | 4
8 | 10 | 3
10 | 61 | 3.8083349013935
34 | 39 | 1.73750308554073
35 | 60 | 5.23594066797949
43 | -1 | 0
(13 rows)By reversing (source,target)=(43,37) we have
testgis=# SELECT * FROM shortest_path_astar('SELECT id, source, target,x1,y1,x2,y2,cost,reverse_cost from roads',43,37,true,true);
vertex_id | edge_id | cost
-----------+---------+------------------
43 | 60 | 5.23594066797949
35 | 40 | 2.20661903277814
34 | 61 | 3.8083349013935
10 | 10 | 3
8 | 8 | 4
6 | 6 | 2.91421356237309
7 | 7 | 2.91421356237309
5 | 3 | 3
4 | 32 | 5.86670129625104
30 | 38 | 2.42470775726398
32 | 43 | 7.08935847100446
37 | -1 | 0
(12 rows)We can use astar_sp_directed() to see the geometric paths
testgis=# SELECT id,gid,astext(the_geom) FROM astar_sp_directed('roads',43,37,true,true);
id | gid | astext
----+-----+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
1 | 43 | MULTILINESTRING((19.1963302631677 -1.00747894403236,17.8800839547984 2.94125998107557,17.8313340915255 4.01375697308019))
2 | 61 | MULTILINESTRING((17.8313340915255 4.01375697308019,18.0047396454493 4.20401231196082,18.1257963529056 4.51270691597435,18.0410566576862 4.785084507751,17.9199999502299 4.94245822744417,17.6415695230805 5.10588478251016,17.4841958033873 5.21483581922082,17.266293729966 5.208782983848,17.1210256810184 5.16036030086549,16.9050866893397 5.03750410181188))
3 | 44 | MULTILINESTRING((14 7.5,16.9050866893397 5.03750410181188))
4 | 6 | MULTILINESTRING((11 7.5,14 7.5))
5 | 4 | MULTILINESTRING((7 7.5,11 7.5))
6 | 47 | MULTILINESTRING((7 7.5,7 8,6 9,5 9))
7 | 48 | MULTILINESTRING((5 9,4 9,3 8,3 7.5))
8 | 3 | MULTILINESTRING((0 7.5,3 7.5))
9 | 23 | MULTILINESTRING((-4 4,-2.8 6.7,0 7.5))
10 | 59 | MULTILINESTRING((-4 4,-4.46274864568763 3.93807848556878,-4.75377039792406 3.78754999303269,-4.90429889046015 3.59688056915365,-4.9946159859818 3.4563873094533,-5.10500354717493 3.15533032438113,-5.14514447851788 2.8643085721447,-5.15517971135362 2.53314588856532,-5.07865086257376 2.26953745529481))
11 | 26 | MULTILINESTRING((-11.497283689023 -0.064510845232198,-10.4761375575425 0.227245192333677,-8.9687313634521 0.470375223638574,-7.36407315683978 0.762131261204449,-6.1484230003153 1.05388729877032,-5.07865086257376 2.26953745529481))Let's create the two associated tables in order to seeing them in QGIS
-- (source,target)=(37,43)
CREATE TABLE shortest_path_astar_table_1(gid int4) with oids;
SELECT AddGeometryColumn( 'shortest_path_astar_table_1', 'the_geom', -1, 'MULTILINESTRING', 2 );
INSERT INTO shortest_path_astar_table_1(the_geom)
SELECT the_geom FROM astar_sp_directed('roads',37,43,true,true);
-- (source,target)=(43,37)
CREATE TABLE shortest_path_astar_table_2(gid int4) with oids;
SELECT AddGeometryColumn( 'shortest_path_astar_table_2', 'the_geom', -1, 'MULTILINESTRING', 2 );
INSERT INTO shortest_path_astar_table_2(the_geom)
SELECT the_geom FROM astar_sp_directed('roads',43,37,true,true);Here is the result
and for (source=43,target=37)
Here we must begin to see the edge from roads (see the field id from roads)
The id field give us the edges from roads table
Suppose that we want the path from 29 to 46 and from 46 to 49.
on't forget to use the field rule and tocost for this function.
from 29 to 46
testgis=# SELECT * FROM shortest_path_shooting_star('SELECT id, source, target, cost,reverse_cost, x1, y1, x2, y2, rule, to_cost FROM roads',29,46,true,true); vertex_id | edge_id | cost -----------+---------+------------------ 40 | 29 | 6.5 43 | 29 | 6.5 40 | 28 | 9.44974746830583 41 | 24 | 1.70710678118655 37 | 25 | 2.91421356237309 36 | 20 | 4 32 | 18 | 8.5 31 | 7 | 2.91421356237309 10 | 3 | 3 9 | 32 | 5.86670129625104 48 | 38 | 2.42470775726398 54 | 43 | 7.08935847100446 53 | 47 | 2.28593953367386 58 | 46 | 1.76395914112196 (14 rows)from 46 to 29
testgis=# SELECT * FROM shortest_path_shooting_star('SELECT id, source, target, cost,reverse_cost, x1, y1, x2, y2, rule, to_cost FROM roads',46,29,true,true) vertex_id | edge_id | cost -----------+---------+------------------ 58 | 46 | 1.76395914112196 56 | 46 | 1.76395914112196 58 | 47 | 2.28593953367386 53 | 43 | 7.08935847100446 54 | 36 | 1.73350805494058 52 | 37 | 1.99498090204589 48 | 32 | 5.86670129625104 9 | 3 | 3 10 | 4 | 2.91421356237309 8 | 5 | 2.91421356237309 11 | 8 | 4 12 | 10 | 3 16 | 12 | 3.5 20 | 17 | 2 30 | 22 | 2.98079618907396 39 | 23 | 1.20710678118655 41 | 28 | 9.44974746830583 40 | 29 | 6.5 (18 rows)
Here we will use two table
from 29 to 46
BEGIN; CREATE TABLE shooting_star_table_1(gid int4) with oids; SELECT AddGeometryColumn( 'shooting_star_table_1', 'the_geom', -1, 'MULTILINESTRING', 2 ); INSERT INTO shooting_star_table_1(the_geom) SELECT the_geom FROM roads WHERE id IN ( SELECT edge_id FROM shortest_path_shooting_star ( 'SELECT id, source, target, cost,reverse_cost, x1, y1, x2, y2, rule, to_cost FROM roads', 29,46,true,true ) ); END;from 46 to 29
BEGIN; CREATE TABLE shooting_star_table_2(gid int4) with oids; SELECT AddGeometryColumn( 'shooting_star_table_2', 'the_geom', -1, 'MULTILINESTRING', 2 ); INSERT INTO shooting_star_table_2(the_geom) SELECT the_geom FROM roads WHERE id IN ( SELECT edge_id FROM shortest_path_shooting_star ( 'SELECT id, source, target, cost,reverse_cost, x1, y1, x2, y2, rule, to_cost FROM roads', 46,29,true,true ) ); END;
Here we will use shootingstar_sp(). We are trying to find the path from edge=31 to edge=56 and vice versa. The requested query is
SELECT the_geom FROM shootingstar_sp('roads',31,56,1,'cost',true,true);In order to see our path in QGIS, we can create the requested tables
BEGIN TRANSACTION; DROP TABLE IF EXISTS shooting_table_1,shooting_table_2; CREATE TABLE shooting_table_1(gid int4) with oids; SELECT AddGeometryColumn( 'shooting_table_1', 'the_geom', -1, 'MULTILINESTRING', 2 ); INSERT INTO shooting_table_1(the_geom) SELECT the_geom FROM shootingstar_sp('roads',31,56,1,'cost',true,true); CREATE TABLE shooting_table_2(gid int4) with oids; SELECT AddGeometryColumn( 'shooting_table_2', 'the_geom', -1, 'MULTILINESTRING', 2 ); INSERT INTO shooting_table_2(the_geom) SELECT the_geom FROM shootingstar_sp('roads',56,31,1,'cost',true,true); END TRANSACTION;
Here is the result
It's times to try TSP. Let's suppose that we want to know what is the best path from source=7 to (46,43,25?18)???. Here we can use tsp_astar_directed.
Caution
tsp_astar_directed() is based on astar_sp_delta_directed(). [For my personal use of this function, I use astar_sp_directed() instead]. (Just see the function in routing_tsp_wrappers.sql...)
testgis=# SELECT * FROM tsp(
'SELECT distinct source AS source_id,x1 as x,y1 as y,cost,reverse_cost FROM roads WHERE source IN (28,37,43,18,23)',
'28,37,43,18,23',37);;will give us
vertex_id | edge_id | cost
-----------+------------+-----------------------
37 | 25784720 | 0
37 | -1 | 9.12458190115067e-313
18 | 16 | 4.24399190603761e-314
18 | 25784800 | 1.69874584211253e-313
23 | 25784800 | 1.69874584211253e-313
23 | 25784776 | 3.39634247488474e-313
28 | 1818326113 | 3.30605350921819e-028
28 | 8 | 1.27393917699377e-316
43 | 8 | 2.96839805221217e-301
43 | 8 | 1.97484348732601e+166
(10 lignes)We can create a table in order to seeing data in QGIS.
BEGIN TRANSACTION;
DROP TABLE IF EXISTS tsp_table;
CREATE TABLE tsp_table(gid integer,the_geom geometry)WITH oids;
INSERT INTO tsp_table
SELECT foo.gid,foo.the_geom FROM (SELECT * FROM tsp_astar_directed('roads','28,37,43,18,23',37,3,true,true)) AS foo JOIN roads r ON foo.gid=r.gid;
END TRANSACTION;