pgRouting中pgr_TSP调用pgr_dijkstraCostMatrix成本计算错误

环境与测试背景 #

• 运行环境：Ubuntu Server + Postgres 14 + pgRouting 3.5
• 测试数据：非OSM路网图，从468个节点中选取14个节点进行TSP路径计算

问题现象 #

调用pgr_TSP()时，通过嵌套的pgr_dijkstraCostMatrix()传入有向图参数（directed=>true），发现路径序列中节点13（ID：13800066621912）到节点14（ID：13800002893438）的成本被计算为1，但单独验证时该节点对的最短路径成本应为17。

验证步骤 #

SQL1：单独验证pgr_dijkstraCostMatrix结果 #

SELECT 
  * 
FROM 
  pgr_dijkstraCostMatrix(
    'SELECT id, source, target, cost, reverse_cost FROM dbroute_pl_generic_edges', 
    (
      SELECT 
        array_agg(id) 
      FROM 
        dbroute_pt_generic_nodes
    ), 
    directed => true
  ) foo 
WHERE 
  start_vid = 13800066621912 
  AND end_vid = 13800002893438

结果：agg_cost为17，符合预期。

SQL2：单独验证pgr_Dijkstra最短路径结果 #

SELECT 
  * 
FROM 
  pgr_Dijkstra(
    'SELECT id, source, target, cost, reverse_cost FROM dbroute_pl_generic_edges', 
    13800066621912, 13800002893438, 
    true
  )

结果：最终agg_cost为17，符合预期。

SQL3：嵌套调用pgr_TSP的语句 #

SELECT 
  * 
FROM 
  pgr_TSP(
    $$ 
    SELECT 
      * 
    FROM 
      pgr_dijkstraCostMatrix(
        'SELECT id, source, target, cost, reverse_cost FROM dbroute_pl_generic_edges', 
        (
          SELECT 
            array_agg(id) 
          FROM 
            dbroute_pt_generic_nodes
        ), 
        directed => true
      ) bar $$
  ) foo

结果：节点13到14的cost显示为1，与预期不符，且其他区域少量节点测试时偶现该问题。

排查与解决方法 #

1. 拆分成本矩阵生成与TSP计算流程 #

避免嵌套调用时可能的隐式转换或数据丢失，先将成本矩阵存入临时表，再传入pgr_TSP：

-- 生成成本矩阵并存入临时表
CREATE TEMP TABLE cost_matrix AS
SELECT * FROM pgr_dijkstraCostMatrix(
  'SELECT id, source, target, cost, reverse_cost FROM dbroute_pl_generic_edges', 
  (SELECT array_agg(id) FROM dbroute_pt_generic_nodes), 
  directed => true
);

-- 再次验证目标节点对的成本
SELECT * FROM cost_matrix WHERE start_vid = 13800066621912 AND end_vid = 13800002893438;

-- 调用pgr_TSP
SELECT * FROM pgr_TSP('SELECT * FROM cost_matrix');

2. 确认TSP结果的节点ID映射 #

pgr_TSP内部可能会对节点ID进行连续化重编号，需关联原始成本矩阵确认节点对应关系：

SELECT 
  tsp.seq,
  cm.start_vid AS original_start_node,
  cm.end_vid AS original_end_node,
  tsp.cost
FROM pgr_TSP('SELECT * FROM cost_matrix') tsp
JOIN cost_matrix cm ON tsp.node = cm.end_vid;

3. 检查边表的直接边成本 #

排查是否存在节点13到14的直接边，且其cost值为1（可能被TSP错误优先使用）：

SELECT id, source, target, cost, reverse_cost 
FROM dbroute_pl_generic_edges 
WHERE (source = 13800066621912 AND target = 13800002893438)
OR (source = 13800002893438 AND target = 13800066621912);

4. 升级pgRouting版本 #

pgRouting 3.5可能存在非对称矩阵处理的已知BUG，建议升级到最新稳定版（如3.6+），查看官方修复记录是否覆盖该问题。

内容的提问来源于stack exchange，提问作者pjhooker