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
- Go to the Database page in the Dashboard.
- Click on Extensions in the sidebar.
- Search for "pgrouting" and enable the extension.
Example
As an example, we'll solve the traveling salesman problem using the pgRouting's pgr_TSPeuclidean function from some PostGIS coordinates.
A summary of the traveling salesman 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
_38create table wi29 (_38 id bigint,_38 x float,_38 y float,_38 geom geometry_38);_38_38insert into wi29 (id, x, y)_38values_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.
_10select_10 *_10from_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
- Official
pgRoutingdocumentation