Database

pgrouting: Geospatial Routing

pgRouting is PostgreSQL and PostGIS extension adding geospatial routing functionality.

The core functionality of pgRouting is a set of path finding algorithms including:

  • All Pairs Shortest Path, Johnson’s Algorithm
  • All Pairs Shortest Path, Floyd-Warshall Algorithm
  • Shortest Path A*
  • Bi-directional Dijkstra Shortest Path
  • Bi-directional A* Shortest Path
  • Shortest Path Dijkstra
  • Driving Distance
  • K-Shortest Path, Multiple Alternative Paths
  • K-Dijkstra, One to Many Shortest Path
  • Traveling Sales Person
  • Turn Restriction Shortest Path (TRSP)

Enable the extension

  1. Go to the Database page in the Dashboard.
  2. Click on Extensions in the sidebar.
  3. Search for pgrouting and enable the extension.

Example

As an example, we'll solve the traveling salesperson problem using the pgRouting's pgr_TSPeuclidean function from some PostGIS coordinates.

A summary of the traveling salesperson problem is, given a set of city coordinates, solve for a path that goes through each city and minimizes the total distance traveled.

First we populate a table with some X, Y coordinates


_38
create table wi29 (
_38
id bigint,
_38
x float,
_38
y float,
_38
geom geometry
_38
);
_38
_38
insert into wi29 (id, x, y)
_38
values
_38
(1,20833.3333,17100.0000),
_38
(2,20900.0000,17066.6667),
_38
(3,21300.0000,13016.6667),
_38
(4,21600.0000,14150.0000),
_38
(5,21600.0000,14966.6667),
_38
(6,21600.0000,16500.0000),
_38
(7,22183.3333,13133.3333),
_38
(8,22583.3333,14300.0000),
_38
(9,22683.3333,12716.6667),
_38
(10,23616.6667,15866.6667),
_38
(11,23700.0000,15933.3333),
_38
(12,23883.3333,14533.3333),
_38
(13,24166.6667,13250.0000),
_38
(14,25149.1667,12365.8333),
_38
(15,26133.3333,14500.0000),
_38
(16,26150.0000,10550.0000),
_38
(17,26283.3333,12766.6667),
_38
(18,26433.3333,13433.3333),
_38
(19,26550.0000,13850.0000),
_38
(20,26733.3333,11683.3333),
_38
(21,27026.1111,13051.9444),
_38
(22,27096.1111,13415.8333),
_38
(23,27153.6111,13203.3333),
_38
(24,27166.6667,9833.3333),
_38
(25,27233.3333,10450.0000),
_38
(26,27233.3333,11783.3333),
_38
(27,27266.6667,10383.3333),
_38
(28,27433.3333,12400.0000),
_38
(29,27462.5000,12992.2222);

Next we use the pgr_TSPeuclidean function to find the best path.


_10
select
_10
*
_10
from
_10
pgr_TSPeuclidean($$select * from wi29$$)


_32
seq | node | cost | agg_cost
_32
-----+------+------------------+------------------
_32
1 | 1 | 0 | 0
_32
2 | 2 | 74.535614157127 | 74.535614157127
_32
3 | 6 | 900.617093380362 | 975.152707537489
_32
4 | 10 | 2113.77757765045 | 3088.93028518793
_32
5 | 11 | 106.718669615254 | 3195.64895480319
_32
6 | 12 | 1411.95293791574 | 4607.60189271893
_32
7 | 13 | 1314.23824873744 | 5921.84014145637
_32
8 | 14 | 1321.76283931305 | 7243.60298076942
_32
9 | 17 | 1202.91366735569 | 8446.5166481251
_32
10 | 18 | 683.333268292684 | 9129.84991641779
_32
11 | 15 | 1108.05137466134 | 10237.9012910791
_32
12 | 19 | 772.082339448903 | 11009.983630528
_32
13 | 22 | 697.666150054665 | 11707.6497805827
_32
14 | 23 | 220.141999627513 | 11927.7917802102
_32
15 | 21 | 197.926372783442 | 12125.7181529937
_32
16 | 29 | 440.456596290771 | 12566.1747492844
_32
17 | 28 | 592.939989005405 | 13159.1147382898
_32
18 | 26 | 648.288376333318 | 13807.4031146231
_32
19 | 20 | 509.901951359278 | 14317.3050659824
_32
20 | 25 | 1330.83095428717 | 15648.1360202696
_32
21 | 27 | 74.535658878487 | 15722.6716791481
_32
22 | 24 | 559.016994374947 | 16281.688673523
_32
23 | 16 | 1243.87392358622 | 17525.5625971092
_32
24 | 9 | 4088.0585364911 | 21613.6211336004
_32
25 | 7 | 650.85409697993 | 22264.4752305803
_32
26 | 3 | 891.004385199336 | 23155.4796157796
_32
27 | 4 | 1172.36699411442 | 24327.846609894
_32
28 | 8 | 994.708187806297 | 25322.5547977003
_32
29 | 5 | 1188.01888359478 | 26510.5736812951
_32
30 | 1 | 2266.91173136004 | 28777.4854126552

Resources