`pgr_TSP`¶

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

可用性：

版本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\}\) 不包括在内，因为它们未连接。

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

参数¶

参数	类型	描述
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` 时，它是第一个和最后一个顶点

列

类型

默认

描述

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

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

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

生成非对称矩阵：

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

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

连接不完整数据 ¶

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

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

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

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

另请参阅¶

索引和表格

pgr_TSP¶

描述¶

问题定义¶

特征¶

签名¶

参数¶

TSP 可选参数¶

内部查询¶

矩阵SQL¶

结果列¶

其他示例¶

从顶点 \(1\) 开始¶

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

连接不完整数据¶

另请参阅¶

`pgr_TSP`¶

从顶点 \(1\) 开始 ¶

连接不完整数据 ¶