示例数据¶
该文档提供了基于类似于城市的小型示例网络的非常简单的示例查询。 为了能够执行大部分示例查询，请按照以下说明进行操作。
主图¶
图由一组边和一组顶点组成。
要在数据库中插入以下城市：
此时已知的信息是边的几何形状、成本值、容量值、类别值和一些不在图中的位置。
拓扑结构的工作流程从插入边开始。然后再计算其他所有内容。
边¶
pgRouting文档的数据库设计将同一行中的两段保留在一个方向上，其中一个是与几何形状相同方向的，另一个是与几何形状相反方向的。因此，一些信息具有 reverse_ 前缀，对应于几何形状相反方向的段。
列 |
描述 |
|---|---|
|
唯一标识符。 |
|
几何体 |
|
几何体 |
|
从 source 到 |
|
从 target 到 |
|
从 source 到 |
|
从 target 到 |
|
从 target 到 |
|
从 target 到 |
|
\(x\) 几何图形起始顶点的坐标。
|
|
\(y\) 几何图形结束顶点的坐标。
|
|
分段的几何形状。 |
CREATE TABLE edges (
id BIGSERIAL PRIMARY KEY,
source BIGINT,
target BIGINT,
cost FLOAT,
reverse_cost FLOAT,
capacity BIGINT,
reverse_capacity BIGINT,
x1 FLOAT,
y1 FLOAT,
x2 FLOAT,
y2 FLOAT,
geom geometry
);
CREATE TABLE
从 PostgreSQL 12 开始：：
...
x1 FLOAT GENERATED ALWAYS AS (ST_X(ST_StartPoint(geom))) STORED,
y1 FLOAT GENERATED ALWAYS AS (ST_Y(ST_StartPoint(geom))) STORED,
x1 FLOAT GENERATED ALWAYS AS (ST_X(ST_EndPoint(geom))) STORED,
y1 FLOAT GENERATED ALWAYS AS (ST_Y(ST_EndPoint(geom))) STORED,
...
可以选择在不同的列上创建索引。建议的做法是
id列创建索引 。source和target列建立索引以加快 pgRouting 查询。geom列建立索引以加快前端可能需要的 gemetry 处理。
在这个小例子中，除了 id 以外，其他索引都被跳过
边数据¶
将边的信息插入数据库：
INSERT INTO edges (
cost, reverse_cost,
capacity, reverse_capacity, geom) VALUES
( 1, 1, 80, 130, ST_MakeLine(ST_POINT(2, 0), ST_POINT(2, 1))),
(-1, 1, -1, 100, ST_MakeLine(ST_POINT(2, 1), ST_POINT(3, 1))),
(-1, 1, -1, 130, ST_MakeLine(ST_POINT(3, 1), ST_POINT(4, 1))),
( 1, 1, 100, 50, ST_MakeLine(ST_POINT(2, 1), ST_POINT(2, 2))),
( 1, -1, 130, -1, ST_MakeLine(ST_POINT(3, 1), ST_POINT(3, 2))),
( 1, 1, 50, 100, ST_MakeLine(ST_POINT(0, 2), ST_POINT(1, 2))),
( 1, 1, 50, 130, ST_MakeLine(ST_POINT(1, 2), ST_POINT(2, 2))),
( 1, 1, 100, 130, ST_MakeLine(ST_POINT(2, 2), ST_POINT(3, 2))),
( 1, 1, 130, 80, ST_MakeLine(ST_POINT(3, 2), ST_POINT(4, 2))),
( 1, 1, 130, 50, ST_MakeLine(ST_POINT(2, 2), ST_POINT(2, 3))),
( 1, -1, 130, -1, ST_MakeLine(ST_POINT(3, 2), ST_POINT(3, 3))),
( 1, -1, 100, -1, ST_MakeLine(ST_POINT(2, 3), ST_POINT(3, 3))),
( 1, -1, 100, -1, ST_MakeLine(ST_POINT(3, 3), ST_POINT(4, 3))),
( 1, 1, 80, 130, ST_MakeLine(ST_POINT(2, 3), ST_POINT(2, 4))),
( 1, 1, 80, 50, ST_MakeLine(ST_POINT(4, 2), ST_POINT(4, 3))),
( 1, 1, 80, 80, ST_MakeLine(ST_POINT(4, 1), ST_POINT(4, 2))),
( 1, 1, 130, 100, ST_MakeLine(ST_POINT(0.5, 3.5), ST_POINT(1.999999999999, 3.5))),
( 1, 1, 50, 130, ST_MakeLine(ST_POINT(3.5, 2.3), ST_POINT(3.5, 4)));
INSERT 0 18
成本、容量和类别上的负值表示不存在边。
顶点¶
根据边的标识符和几何形状计算顶点信息并保存在表中。 保存 pgr_extractVertices -- 拟议 提供的所有信息 ：
SELECT * INTO vertices
FROM pgr_extractVertices('SELECT id, geom FROM edges ORDER BY id');
SELECT 17
在本例中，由于未使用 CREATE 语句，因此需要在表上定义索引。
CREATE SEQUENCE vertices_id_seq;
CREATE SEQUENCE
ALTER TABLE vertices ALTER COLUMN id SET DEFAULT nextval('vertices_id_seq');
ALTER TABLE
ALTER SEQUENCE vertices_id_seq OWNED BY vertices.id;
ALTER SEQUENCE
SELECT setval('vertices_id_seq', (SELECT coalesce(max(id)) FROM vertices));
setval
--------
17
(1 row)
表的结构如下：
Table "public.vertices"
Column | Type | Collation | Nullable | Default
-----------+------------------+-----------+----------+--------------------------------------
id | bigint | | | nextval('vertices_id_seq'::regclass)
in_edges | bigint[] | | |
out_edges | bigint[] | | |
x | double precision | | |
y | double precision | | |
geom | geometry | | |
顶点数据¶
保存的顶点信息为：
SELECT * FROM vertices;
id | in_edges | out_edges | x | y | geom
----+----------+-----------+----------------+-----+--------------------------------------------
1 | | {6} | 0 | 2 | 010100000000000000000000000000000000000040
2 | | {17} | 0.5 | 3.5 | 0101000000000000000000E03F0000000000000C40
3 | {6} | {7} | 1 | 2 | 0101000000000000000000F03F0000000000000040
4 | {17} | | 1.999999999999 | 3.5 | 010100000068EEFFFFFFFFFF3F0000000000000C40
5 | | {1} | 2 | 0 | 010100000000000000000000400000000000000000
6 | {1} | {2,4} | 2 | 1 | 01010000000000000000000040000000000000F03F
7 | {4,7} | {8,10} | 2 | 2 | 010100000000000000000000400000000000000040
8 | {10} | {12,14} | 2 | 3 | 010100000000000000000000400000000000000840
9 | {14} | | 2 | 4 | 010100000000000000000000400000000000001040
10 | {2} | {3,5} | 3 | 1 | 01010000000000000000000840000000000000F03F
11 | {5,8} | {9,11} | 3 | 2 | 010100000000000000000008400000000000000040
12 | {11,12} | {13} | 3 | 3 | 010100000000000000000008400000000000000840
13 | | {18} | 3.5 | 2.3 | 01010000000000000000000C406666666666660240
14 | {18} | | 3.5 | 4 | 01010000000000000000000C400000000000001040
15 | {3} | {16} | 4 | 1 | 01010000000000000000001040000000000000F03F
16 | {9,16} | {15} | 4 | 2 | 010100000000000000000010400000000000000040
17 | {13,15} | | 4 | 3 | 010100000000000000000010400000000000000840
(17 rows)
这里可以为顶点表添加更多的列。附加列的名称和类型取决于应用程序。
拓扑结构¶
此查询基于顶点数据，通过填充边表中的 source 列和 target 列来创建拓扑。
/* -- set the source information */
UPDATE edges AS e
SET source = v.id, x1 = x, y1 = y
FROM vertices AS v
WHERE ST_StartPoint(e.geom) = v.geom;
UPDATE 18
/* -- set the target information */
UPDATE edges AS e
SET target = v.id, x2 = x, y2 = y
FROM vertices AS v
WHERE ST_EndPoint(e.geom) = v.geom;
UPDATE 18
拓扑数据¶
SELECT id, source, target
FROM edges ORDER BY id;
id | source | target
----+--------+--------
1 | 5 | 6
2 | 6 | 10
3 | 10 | 15
4 | 6 | 7
5 | 10 | 11
6 | 1 | 3
7 | 3 | 7
8 | 7 | 11
9 | 11 | 16
10 | 7 | 8
11 | 11 | 12
12 | 8 | 12
13 | 12 | 17
14 | 8 | 9
15 | 16 | 17
16 | 15 | 16
17 | 2 | 4
18 | 13 | 14
(18 rows)
图之外的点¶
兴趣点¶
有时应用程序会“即时执行”，从不是图中顶点的位置开始。在pgRouting中，这些位置被称为兴趣点。
兴趣点所需的信息包括 pid, edge_id, side, fraction。
在这份文档中，将有6个固定的兴趣点，并且它们将被存储在一个表中。
列 |
描述 |
|---|---|
|
唯一标识符。 |
|
允许到达该点的最近边的标识符。 |
|
它位于边 |
|
该点位于边的哪个位置。 |
|
点的几何形状。 |
|
在线段顶部移动的点的几何形状。 |
CREATE TABLE pointsOfInterest(
pid BIGSERIAL PRIMARY KEY,
edge_id BIGINT,
side CHAR,
fraction FLOAT,
geom geometry);
CREATE TABLE
兴趣点填充¶
INSERT INTO pointsOfInterest (edge_id, side, fraction, geom) VALUES
(1, 'l' , 0.4, ST_POINT(1.8, 0.4)),
(15, 'r' , 0.4, ST_POINT(4.2, 2.4)),
(12, 'l' , 0.6, ST_POINT(2.6, 3.2)),
(6, 'r' , 0.3, ST_POINT(0.3, 1.8)),
(5, 'l' , 0.8, ST_POINT(2.9, 1.8)),
(4, 'b' , 0.7, ST_POINT(2.2, 1.7));
INSERT 0 6
支持表¶
组合¶
当需要从 source 到 target 的路由时，许多函数都可以与 (source, target) 对组合使用。
为便于阅读，某些组合将存储在一个表中：
CREATE TABLE combinations (
source BIGINT,
target BIGINT
);
CREATE TABLE
插入数据：
INSERT INTO combinations (
source, target) VALUES
(5, 6),
(5, 10),
(6, 5),
(6, 15),
(6, 14);
INSERT 0 5
组合数据¶
SELECT * FROM combinations;
source | target
--------+--------
5 | 6
5 | 10
6 | 5
6 | 15
6 | 14
(5 rows)
限制¶
一些函数接受关于段的软约束。
限制表的创建
CREATE TABLE restrictions (
id SERIAL PRIMARY KEY,
path BIGINT[],
cost FLOAT
);
CREATE TABLE
添加限制
INSERT INTO restrictions (path, cost) VALUES
(ARRAY[4, 7], 100),
(ARRAY[8, 11], 100),
(ARRAY[7, 10], 100),
(ARRAY[3, 5, 9], 4),
(ARRAY[9, 16], 100);
INSERT 0 5
限制数据¶
SELECT * FROM restrictions;
id | path | cost
----+---------+------
1 | {4,7} | 100
2 | {8,11} | 100
3 | {7,10} | 100
4 | {3,5,9} | 4
5 | {9,16} | 100
(5 rows)
图片¶
红色箭头对应边表中
cost> 0 的情况。蓝色箭头对应边表中的
reverse_cost> 0 的情况。点位于图之外。
点击图可放大。
带 cost 和 reverse_cost 的有向图¶
在使用城市网络时，建议从车辆的角度考虑。
具有cost和reverse_cost的有向图¶
具有 cost 和 reverse_cost 的无向图¶
在使用城市网络时，建议从行人的角度考虑。
带有cost和 reverse cost的无向图¶
有 cost 的有向图¶
有向，有成本¶
带有 cost 的无向图¶
无向，有成本¶
取货和送货数据¶
此数据示例 lc101 来自 https://www.sintef.no/projectweb/top/pdptw/li-lim-benchmark/ 上发布的数据
车辆¶
问题中有 25 辆车都具有相同的特征。
CREATE TABLE v_lc101(
id BIGINT NOT NULL primary key,
capacity BIGINT DEFAULT 200,
start_x FLOAT DEFAULT 30,
start_y FLOAT DEFAULT 50,
start_open INTEGER DEFAULT 0,
start_close INTEGER DEFAULT 1236);
CREATE TABLE
/* create 25 vehciles */
INSERT INTO v_lc101 (id)
(SELECT * FROM generate_series(1, 25));
INSERT 0 25
原始订单¶
对于同一订单的取货和配送，数据位于不同的行中。
CREATE table lc101_c(
id BIGINT not null primary key,
x DOUBLE PRECISION,
y DOUBLE PRECISION,
demand INTEGER,
open INTEGER,
close INTEGER,
service INTEGER,
pindex BIGINT,
dindex BIGINT
);
CREATE TABLE
/* the original data */
INSERT INTO lc101_c(
id, x, y, demand, open, close, service, pindex, dindex) VALUES
( 1, 45, 68, -10, 912, 967, 90, 11, 0),
( 2, 45, 70, -20, 825, 870, 90, 6, 0),
( 3, 42, 66, 10, 65, 146, 90, 0, 75),
( 4, 42, 68, -10, 727, 782, 90, 9, 0),
( 5, 42, 65, 10, 15, 67, 90, 0, 7),
( 6, 40, 69, 20, 621, 702, 90, 0, 2),
( 7, 40, 66, -10, 170, 225, 90, 5, 0),
( 8, 38, 68, 20, 255, 324, 90, 0, 10),
( 9, 38, 70, 10, 534, 605, 90, 0, 4),
( 10, 35, 66, -20, 357, 410, 90, 8, 0),
( 11, 35, 69, 10, 448, 505, 90, 0, 1),
( 12, 25, 85, -20, 652, 721, 90, 18, 0),
( 13, 22, 75, 30, 30, 92, 90, 0, 17),
( 14, 22, 85, -40, 567, 620, 90, 16, 0),
( 15, 20, 80, -10, 384, 429, 90, 19, 0),
( 16, 20, 85, 40, 475, 528, 90, 0, 14),
( 17, 18, 75, -30, 99, 148, 90, 13, 0),
( 18, 15, 75, 20, 179, 254, 90, 0, 12),
( 19, 15, 80, 10, 278, 345, 90, 0, 15),
( 20, 30, 50, 10, 10, 73, 90, 0, 24),
( 21, 30, 52, -10, 914, 965, 90, 30, 0),
( 22, 28, 52, -20, 812, 883, 90, 28, 0),
( 23, 28, 55, 10, 732, 777, 0, 0, 103),
( 24, 25, 50, -10, 65, 144, 90, 20, 0),
( 25, 25, 52, 40, 169, 224, 90, 0, 27),
( 26, 25, 55, -10, 622, 701, 90, 29, 0),
( 27, 23, 52, -40, 261, 316, 90, 25, 0),
( 28, 23, 55, 20, 546, 593, 90, 0, 22),
( 29, 20, 50, 10, 358, 405, 90, 0, 26),
( 30, 20, 55, 10, 449, 504, 90, 0, 21),
( 31, 10, 35, -30, 200, 237, 90, 32, 0),
( 32, 10, 40, 30, 31, 100, 90, 0, 31),
( 33, 8, 40, 40, 87, 158, 90, 0, 37),
( 34, 8, 45, -30, 751, 816, 90, 38, 0),
( 35, 5, 35, 10, 283, 344, 90, 0, 39),
( 36, 5, 45, 10, 665, 716, 0, 0, 105),
( 37, 2, 40, -40, 383, 434, 90, 33, 0),
( 38, 0, 40, 30, 479, 522, 90, 0, 34),
( 39, 0, 45, -10, 567, 624, 90, 35, 0),
( 40, 35, 30, -20, 264, 321, 90, 42, 0),
( 41, 35, 32, -10, 166, 235, 90, 43, 0),
( 42, 33, 32, 20, 68, 149, 90, 0, 40),
( 43, 33, 35, 10, 16, 80, 90, 0, 41),
( 44, 32, 30, 10, 359, 412, 90, 0, 46),
( 45, 30, 30, 10, 541, 600, 90, 0, 48),
( 46, 30, 32, -10, 448, 509, 90, 44, 0),
( 47, 30, 35, -10, 1054, 1127, 90, 49, 0),
( 48, 28, 30, -10, 632, 693, 90, 45, 0),
( 49, 28, 35, 10, 1001, 1066, 90, 0, 47),
( 50, 26, 32, 10, 815, 880, 90, 0, 52),
( 51, 25, 30, 10, 725, 786, 0, 0, 101),
( 52, 25, 35, -10, 912, 969, 90, 50, 0),
( 53, 44, 5, 20, 286, 347, 90, 0, 58),
( 54, 42, 10, 40, 186, 257, 90, 0, 60),
( 55, 42, 15, -40, 95, 158, 90, 57, 0),
( 56, 40, 5, 30, 385, 436, 90, 0, 59),
( 57, 40, 15, 40, 35, 87, 90, 0, 55),
( 58, 38, 5, -20, 471, 534, 90, 53, 0),
( 59, 38, 15, -30, 651, 740, 90, 56, 0),
( 60, 35, 5, -40, 562, 629, 90, 54, 0),
( 61, 50, 30, -10, 531, 610, 90, 67, 0),
( 62, 50, 35, 20, 262, 317, 90, 0, 68),
( 63, 50, 40, 50, 171, 218, 90, 0, 74),
( 64, 48, 30, 10, 632, 693, 0, 0, 102),
( 65, 48, 40, 10, 76, 129, 90, 0, 72),
( 66, 47, 35, 10, 826, 875, 90, 0, 69),
( 67, 47, 40, 10, 12, 77, 90, 0, 61),
( 68, 45, 30, -20, 734, 777, 90, 62, 0),
( 69, 45, 35, -10, 916, 969, 90, 66, 0),
( 70, 95, 30, -30, 387, 456, 90, 81, 0),
( 71, 95, 35, 20, 293, 360, 90, 0, 77),
( 72, 53, 30, -10, 450, 505, 90, 65, 0),
( 73, 92, 30, -10, 478, 551, 90, 76, 0),
( 74, 53, 35, -50, 353, 412, 90, 63, 0),
( 75, 45, 65, -10, 997, 1068, 90, 3, 0),
( 76, 90, 35, 10, 203, 260, 90, 0, 73),
( 77, 88, 30, -20, 574, 643, 90, 71, 0),
( 78, 88, 35, 20, 109, 170, 0, 0, 104),
( 79, 87, 30, 10, 668, 731, 90, 0, 80),
( 80, 85, 25, -10, 769, 820, 90, 79, 0),
( 81, 85, 35, 30, 47, 124, 90, 0, 70),
( 82, 75, 55, 20, 369, 420, 90, 0, 85),
( 83, 72, 55, -20, 265, 338, 90, 87, 0),
( 84, 70, 58, 20, 458, 523, 90, 0, 89),
( 85, 68, 60, -20, 555, 612, 90, 82, 0),
( 86, 66, 55, 10, 173, 238, 90, 0, 91),
( 87, 65, 55, 20, 85, 144, 90, 0, 83),
( 88, 65, 60, -10, 645, 708, 90, 90, 0),
( 89, 63, 58, -20, 737, 802, 90, 84, 0),
( 90, 60, 55, 10, 20, 84, 90, 0, 88),
( 91, 60, 60, -10, 836, 889, 90, 86, 0),
( 92, 67, 85, 20, 368, 441, 90, 0, 93),
( 93, 65, 85, -20, 475, 518, 90, 92, 0),
( 94, 65, 82, -10, 285, 336, 90, 96, 0),
( 95, 62, 80, -20, 196, 239, 90, 98, 0),
( 96, 60, 80, 10, 95, 156, 90, 0, 94),
( 97, 60, 85, 30, 561, 622, 0, 0, 106),
( 98, 58, 75, 20, 30, 84, 90, 0, 95),
( 99, 55, 80, -20, 743, 820, 90, 100, 0),
( 100, 55, 85, 20, 647, 726, 90, 0, 99),
( 101, 25, 30, -10, 725, 786, 90, 51, 0),
( 102, 48, 30, -10, 632, 693, 90, 64, 0),
( 103, 28, 55, -10, 732, 777, 90, 23, 0),
( 104, 88, 35, -20, 109, 170, 90, 78, 0),
( 105, 5, 45, -10, 665, 716, 90, 36, 0),
( 106, 60, 85, -30, 561, 622, 90, 97, 0);
INSERT 0 106
订单¶
需要将原始数据转换为合适的表格：
WITH deliveries AS (SELECT * FROM lc101_c WHERE dindex = 0)
SELECT
row_number() over() AS id, p.demand,
p.id as p_node_id, p.x AS p_x, p.y AS p_y, p.open AS p_open, p.close as p_close, p.service as p_service,
d.id as d_node_id, d.x AS d_x, d.y AS d_y, d.open AS d_open, d.close as d_close, d.service as d_service
INTO c_lc101
FROM deliveries as d JOIN lc101_c as p ON (d.pindex = p.id);
SELECT 53
SELECT * FROM c_lc101 LIMIT 1;
id | demand | p_node_id | p_x | p_y | p_open | p_close | p_service | d_node_id | d_x | d_y | d_open | d_close | d_service
----+--------+-----------+-----+-----+--------+---------+-----------+-----------+-----+-----+--------+---------+-----------
1 | 10 | 3 | 42 | 66 | 65 | 146 | 90 | 75 | 45 | 65 | 997 | 1068 | 90
(1 row)