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

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