Skip to content
Database

pgrouting：地理空间路由

pgRouting 是 Postgres 以及 PostGIS 扩展，增加了地理空间路由功能。

pgRouting 的核心功能是一组路径寻找算法，包括：

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

  • 所有节点对最短路径，约翰逊算法
  • 全对最短路径，弗洛伊德-沃肖算法
  • 最短路径 A*
  • 双向 Dijkstra 最短路径
  • 双向A*最短路径
  • 最短路径迪杰斯特拉
  • 驾驶距离
  • K 最短路径，多条备选路径
  • K-Dijkstra，一对多最短路径
  • 推销员
  • 转向限制最短路径（TRSP）

启用扩展 #

🌐 Enable the extension

  1. 在仪表板中转到数据库页面。
  2. 点击侧边栏的 扩展。
  3. 搜索 pgrouting 并启用这个扩展。

示例 #

🌐 Example

例如，我们将使用 pgRouting 的 pgr_TSPeuclidean 函数，从一些 PostGIS 坐标来解决旅行推销员问题。

🌐 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.

首先我们用一些 X、Y 坐标填充一个表格

🌐 First we populate a table with some X, Y coordinates

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

接下来我们用 pgr_TSPeuclidean 函数来找出最佳路径。

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

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

资源 #

🌐 Resources