数据库

pgrouting: 地理空间路由

pgRouting 是 Postgres 和 PostGIS 的扩展，用于增加地理空间路由功能。

pgRouting 的核心功能是一系列路径查找算法，包括：

  • 全对最短路径，Johnson 算法
  • 全对最短路径，Floyd-Warshall 算法
  • A* 最短路径
  • 双向 Dijkstra 最短路径
  • 双向 A* 最短路径
  • Dijkstra 最短路径
  • 行驶距离计算
  • K-最短路径，多备选路径
  • K-Dijkstra，一对多最短路径
  • 旅行商问题
  • 转向限制最短路径 (TRSP)

启用扩展

  1. 进入 Dashboard 的 数据库 页面
  2. 在侧边栏点击 扩展
  3. 搜索 pgrouting 并启用该扩展

示例

我们将通过一个示例，使用 pgRouting 的 pgr_TSPeuclidean 函数基于 PostGIS 坐标来解决旅行商问题。

旅行商问题的简要描述是：给定一组城市坐标，求解一条经过每个城市且总旅行距离最短的路径。

首先我们创建一个表并填充一些 X、Y 坐标数据：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
create table wi29 (  id bigint,  x float,  y float,  geom 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 函数来寻找最优路径：

1
2
3
4
select    *from     pgr_TSPeuclidean($$select * from wi29$$)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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

相关资源