pgr_TSP

  • pgr_TSP -使用*metric*算法的近似方法。

_images/boost-inside.jpeg

Boost 图内部

可用性：

  • 版本3.2.1

    • Boost库 中的度量算法

    • Simulated Annealing算法不再受支持

      • Simulated Annealing算法相关参数被忽略：max_processing_time、tries_per_temper、max_changes_per_tempere、max_consecutive_non_changes、initial_temper、final_temper、cooling_factor、randomize

  • 版本2.3.0

    • 签名变更

      • 不再支持旧签名

  • 版本2.0.0

    • 官方 函数

描述

问题定义

旅行推销员问题 (TSP) 提出以下问题：

给定一个城市列表以及每对城市之间的距离，哪条是访问每个城市一次并返回出发城市的最短路线？

特征

  • 该问题是一个NP-hard优化问题。

  • 使用度量算法

  • 在最坏的情况下，实施产生的解决方案的时间是最佳旅行的两倍：

    • 图是无向的

    • 图是全连通的

    • 图中，边上的旅行成本服从三角不等式。

  • 在无向图上：

    • 旅行费用是对称的：

    • 从 u 到 v 的旅行费用与从 v 到 u 的旅行费用相同

  • 可以与 成本矩阵 - 类别 函数一起使用，最好使用 directed => false。

    • 使用 directed => false

      • 将生成一个图：

        • 是无向的

        • 是完全连接的（只要图有一个分量）

        • 所有边上的旅行成本都遵循三角不等式。

      • 当 start_vid = 0 OR end_vid = 0

        • 生成的解决方案保证是*最坏情况下最优路径时间的两倍*

      • 当 start_vid != 0 AND end_vid != 0 AND start_vid != end_vid

        • 在最坏情况下， 不能保证 解决方案将是最优路径的两倍长，因为 end_vid 被强制设置在固定位置。

    • 当 directed => true

      • 不能保证 在最坏情况下解决方案将是最优路径的两倍长

      • 将生成一个图：

        • 有向

        • 是完全连接的（只要图有一个分量）

        • 某些（或全部）边上的旅行成本可能不满足三角不等式。

      • 由于需要无向图，有向图变换如下：

        • 边 (u, v) 和 (v, u)`被认为是相同的边（表示为 `(u, v)

        • 如果 agg_cost 在边`(u, v)` 的一个或多个实例之间不同

        • 边 (u, v) 的所有实例的 agg_cost 最小值将被视为边 (u, v) 的 agg_cost

        • 边上的一些（或全部）旅行成本仍然可能不遵守三角不等式。

  • 当数据不完整，但是是连通图时：

    • 缺失值将使用 dijkstra 算法计算。

签名

总结

pgr_TSP(Matrix SQL, [start_id, end_id])
返回 (seq, node, cost, agg_cost) 的集合
OR EMTPY SET
示例:

使用 pgr_dijkstraCostMatrix 生成矩阵信息

  • Line 4 顶点 \(\{2, 4, 13, 14\}\) 不包括在内，因为它们未连接。

 1SELECT * FROM pgr_TSP(
 2  $$SELECT * FROM pgr_dijkstraCostMatrix(
 3    'SELECT id, source, target, cost, reverse_cost FROM edges',
 4    (SELECT array_agg(id) FROM vertices WHERE id NOT IN (2, 4, 13, 14)),
 5    directed => false) $$);
 6 seq | node | cost | agg_cost
 7-----+------+------+----------
 8   1 |    1 |    0 |        0
 9   2 |    3 |    1 |        1
10   3 |    7 |    1 |        2
11   4 |    6 |    1 |        3
12   5 |    5 |    1 |        4
13   6 |   10 |    2 |        6
14   7 |   11 |    1 |        7
15   8 |   12 |    1 |        8
16   9 |   16 |    2 |       10
17  10 |   15 |    1 |       11
18  11 |   17 |    2 |       13
19  12 |    9 |    3 |       16
20  13 |    8 |    1 |       17
21  14 |    1 |    3 |       20
22(14 rows)
23

参数

参数

类型

描述

Matrix SQL

TEXT

Matrix SQL 如下所述

TSP 可选参数

列

类型

默认

描述

start_id

ANY-INTEGER

0

第一个访问顶点

  • 当 0 时，任何顶点都可以成为第一个访问顶点。

end_id

ANY-INTEGER

0

返回 start_vid 之前最后访问的顶点。

  • 当为 0 时，任何顶点都可以成为返回 start_id 之前最后访问的顶点。

  • 当 NOT 0 且 start_id = 0 时，它是第一个和最后一个顶点

内部查询

矩阵SQL

列

类型

描述

start_vid

ANY-INTEGER

起始顶点的标识符。

end_vid

ANY-INTEGER

结束顶点的标识符。

agg_cost

ANY-NUMERICAL

从 start_vid 到 end_vid 的成本

结果列

返回集合 (seq, node, cost, agg_cost)

列

类型

描述

seq

INTEGER

行顺序。

node

BIGINT

节点/坐标/点的标识符。

cost

FLOAT

从路径序列中的当前 node``遍历到下一个``node 的成本。

  • 0 表示游览序列中的最后一行。

agg_cost

FLOAT

从 seq = 1 的 node 到当前节点的总成本。

  • 0 表示游览序列中的第一行。

其他示例

从顶点 \(1\) 开始

  • Line 6 start_vid => 1

 1SELECT * FROM pgr_TSP(
 2  $$SELECT * FROM pgr_dijkstraCostMatrix(
 3    'SELECT id, source, target, cost, reverse_cost FROM edges',
 4    (SELECT array_agg(id) FROM vertices WHERE id NOT IN (2, 4, 13, 14)),
 5    directed => false) $$,
 6  start_id => 1);
 7 seq | node | cost | agg_cost
 8-----+------+------+----------
 9   1 |    1 |    0 |        0
10   2 |    3 |    1 |        1
11   3 |    7 |    1 |        2
12   4 |    6 |    1 |        3
13   5 |    5 |    1 |        4
14   6 |   10 |    2 |        6
15   7 |   11 |    1 |        7
16   8 |   12 |    1 |        8
17   9 |   16 |    2 |       10
18  10 |   15 |    1 |       11
19  11 |   17 |    2 |       13
20  12 |    9 |    3 |       16
21  13 |    8 |    1 |       17
22  14 |    1 |    3 |       20
23(14 rows)
24

使用兴趣点生成不对称矩阵。

生成非对称矩阵：

  • Line 4 通过未在查询中包括 pointsOfInterset 中的``side`` 信息而被忽略

  • Line 6 使用 directed => true 生成一个非对称矩阵

    • \(min(agg\_cost(u, v), agg\_cost(v, u))\) 将被视为 agg_cost

    • 该解决方案的长度可能是*最佳行程的两倍以上*，因为：

      • 三角不等式可能不满足。

      • start_id != 0 AND end_id != 0

 1SELECT * FROM pgr_TSP(
 2  $$SELECT * FROM pgr_withPointsCostMatrix(
 3    'SELECT id, source, target, cost, reverse_cost FROM edges ORDER BY id',
 4    'SELECT pid, edge_id, fraction from pointsOfInterest',
 5    array[-1, 10, 7, 11, -6],
 6    directed => true) $$,
 7  start_id => 7,
 8  end_id => 11);
 9 seq | node | cost | agg_cost
10-----+------+------+----------
11   1 |    7 |    0 |        0
12   2 |   -6 |  0.3 |      0.3
13   3 |   -1 |  1.3 |      1.6
14   4 |   10 |  1.6 |      3.2
15   5 |   11 |    1 |      4.2
16   6 |    7 |    1 |      5.2
17(6 rows)
18

连接不完整数据

使用选定的边 \(\{2, 4, 5, 8, 9, 15\}\)，矩阵不完整。

 1SELECT * FROM pgr_dijkstraCostMatrix(
 2  $q1$SELECT id, source, target, cost, reverse_cost FROM edges WHERE id IN (2, 4, 5, 8, 9, 15)$q1$,
 3  (SELECT ARRAY[6, 7, 10, 11, 16, 17]),
 4  directed => true);
 5 start_vid | end_vid | agg_cost
 6-----------+---------+----------
 7         6 |       7 |        1
 8         6 |      11 |        2
 9         6 |      16 |        3
10         6 |      17 |        4
11         7 |       6 |        1
12         7 |      11 |        1
13         7 |      16 |        2
14         7 |      17 |        3
15        10 |       6 |        1
16        10 |       7 |        2
17        10 |      11 |        1
18        10 |      16 |        2
19        10 |      17 |        3
20        11 |       6 |        2
21        11 |       7 |        1
22        11 |      16 |        1
23        11 |      17 |        2
24        16 |       6 |        3
25        16 |       7 |        2
26        16 |      11 |        1
27        16 |      17 |        1
28        17 |       6 |        4
29        17 |       7 |        3
30        17 |      11 |        2
31        17 |      16 |        1
32(25 rows)
33

对于 \(17 \rightarrow 10\) 的成本值在矩阵中不存在，但使用的值是从 \(10 \rightarrow 17\) 中获取的。

 1SELECT * FROM pgr_TSP(
 2  $$SELECT * FROM pgr_dijkstraCostMatrix(
 3  $q1$SELECT id, source, target, cost, reverse_cost FROM edges WHERE id IN (2, 4, 5, 8, 9, 15)$q1$,
 4  (SELECT ARRAY[6, 7, 10, 11, 16, 17]),
 5  directed => true)$$);
 6 seq | node | cost | agg_cost
 7-----+------+------+----------
 8   1 |    6 |    0 |        0
 9   2 |    7 |    1 |        1
10   3 |   11 |    1 |        2
11   4 |   16 |    1 |        3
12   5 |   17 |    1 |        4
13   6 |   10 |    3 |        7
14   7 |    6 |    1 |        8
15(7 rows)
16

另请参阅

索引和表格