示例数据¶
The documentation provides very simple example queries based on a small sample network that resembles a city. To be able to execute the majority of the examples queries, follow the instructions below.
主图¶
图由一组边和一组顶点组成。
要在数据库中插入以下城市：
Information known at this point is the geometry of the edges, cost values, capacity values, category values and some locations that are not in the graph.
拓扑结构的工作流程从插入边开始。然后再计算其他所有内容。
边¶
The database design for the documentation of pgRouting, keeps in the same row 2
segments, one in the direction of the geometry and the second in the opposite
direction. Therefore some information has the reverse_ prefix which
corresponds to the segment on the opposite direction of the geometry.
列 |
描述 |
|---|---|
|
唯一标识符。 |
|
几何体 |
|
几何体 |
|
从 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,
...
Optionally indexes on different columns can be created. The recommendation is to have
id列创建索引 。source和target列建立索引以加快 pgRouting 查询。geomindexed to speed up geometry processes that might be needed in the front end.
在这个小例子中，除了 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个固定的兴趣点，并且它们将被存储在一个表中。
列 |
描述 |
|---|---|
|
唯一标识符。 |
|
Identifier of the nearest segment. |
|
Is it on the left, right or both sides of the segment |
|
该点位于边的哪个位置。 |
|
点的几何形状。 |
|
The distance between |
|
A segment that connects the |
|
A point on segment |
CREATE TABLE pointsOfInterest(
pid BIGSERIAL PRIMARY KEY,
edge_id BIGINT,
side CHAR,
fraction FLOAT,
distance FLOAT,
edge geometry,
newPoint geometry,
geom geometry);
IF v > 3.4 THEN
Points of interest fill up¶
Inserting the points of interest.
INSERT INTO pointsOfInterest (geom) VALUES
(ST_Point(1.8, 0.4)),
(ST_Point(4.2, 2.4)),
(ST_Point(2.6, 3.2)),
(ST_Point(0.3, 1.8)),
(ST_Point(2.9, 1.8)),
(ST_Point(2.2, 1.7));
Filling the rest of the table.
UPDATE pointsofinterest SET
edge_id = poi.edge_id,
side = poi.side,
fraction = round(poi.fraction::numeric, 2),
distance = round(poi.distance::numeric, 2),
edge = poi.edge,
newPoint = ST_EndPoint(poi.edge)
FROM (
SELECT *
FROM pgr_findCloseEdges(
$$SELECT id, geom FROM edges$$,(SELECT array_agg(geom) FROM pointsOfInterest), 0.5) ) AS poi
WHERE pointsOfInterest.geom = poi.geom;
Any other additional modification: In this manual, point \(6\) can be reached from both sides.
UPDATE pointsOfInterest SET side = 'b' WHERE pid = 6;
The points of interest:
SELECT
pid, ST_AsText(geom) geom,
edge_id, fraction AS frac, side, distance AS dist,
ST_AsText(edge) edge, ST_AsText(newPoint) newPoint
FROM pointsOfInterest;
pid | geom | edge_id | frac | side | dist | edge | newpoint
-----+----------------+---------+------+------+------+---------------------------+--------------
1 | POINT(1.8 0.4) | 1 | 0.4 | l | 0.2 | LINESTRING(1.8 0.4,2 0.4) | POINT(2 0.4)
4 | POINT(0.3 1.8) | 6 | 0.3 | r | 0.2 | LINESTRING(0.3 1.8,0.3 2) | POINT(0.3 2)
3 | POINT(2.6 3.2) | 12 | 0.6 | l | 0.2 | LINESTRING(2.6 3.2,2.6 3) | POINT(2.6 3)
2 | POINT(4.2 2.4) | 15 | 0.4 | r | 0.2 | LINESTRING(4.2 2.4,4 2.4) | POINT(4 2.4)
5 | POINT(2.9 1.8) | 5 | 0.8 | l | 0.1 | LINESTRING(2.9 1.8,3 1.8) | POINT(3 1.8)
6 | POINT(2.2 1.7) | 4 | 0.7 | b | 0.2 | LINESTRING(2.2 1.7,2 1.7) | POINT(2 1.7)
(6 rows)
支持表¶
组合¶
当需要从 source 到 target 的路由时，许多函数都可以与 (source, target) 对组合使用。
For convenience of this documentation, some combinations will be stored on a table:
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/ 上发布的数据
车辆¶
There are 25 vehicles in the problem all with the same characteristics.
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
订单¶
The original data needs to be converted to an appropriate table:
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)