云原生数据库 PolarDB：路径模型

简介

路径模型是一种以点、边描述的图结构，用于解决基于道路网的路径规划问题、电子地图GPS导航路径搜索规划问题、路由问题等。路径模型完全兼容PGRouting接口，支持已有应用的平滑迁移。路径数据是由Edge和Node构成的几何网络图，主要用于构建道路和交通网络。

GanosBase Networking是对象关系型数据库PostgreSQL兼容版本（PolarDB PostgreSQL版）的一个时空引擎扩展，Networking扩展提供了一系列的函数和存储过程，用于根据代价模型查找最快、最短甚至是最优的路径，它能够提供地理空间路由功能，支持多种路径分析和网络分析算法，为数据库增加了路径分析和网络分析的功能。

功能概述

GanosBase Networking主要提供了一系列的路径规划与网络分析函数：

• Johnson算法。

• Floyd-Warshall算法。

• AStar/双向AStar最短路径算法。

• Dijkstra/双向Dijkstra最短路径算法。

• 旅行推销员算法。

• Prim算法。

• Kruskal算法。

• K最短路径算法。

• 流量（Flow）分析。

• 图拓扑（Topology）相关操作。

• 图部件（Component） 相关操作。

• 图收缩。

• 转弯限制最短路径（Turn Restriction Shortest Path）算法。

同时，部分函数还支持设置成本（cost）或成本矩阵（cost matrix）进行计算。

主要业务场景

GanosBase Networking的使用场景非常广泛：

• 最优路线规划

  在物流、快递、出租车服务等行业中，可以使用GanosBase Networking来计算两点之间的最短路径或最快路径，以便进行路线规划和优化。同时，对于非地理路径，如互联网节点的连接，也可以借助GanosBase Networking得到更优的网络拓扑。

• 地理空间分析

  GanosBase Networking可以用于执行基于路网的分析。例如，最近邻搜索、服务区分析等。这些分析可以帮助用户了解地理空间数据的分布和关系，进一步进行决策和规划。

• 交通流量管理

  通过结合交通流数据，GanosBase Networking可以帮助分析交通流量，预测拥堵情况，并提供优化建议。这对于城市交通管理、智能交通系统等应用非常有价值。

基本构成

pgr_<name>(Inner_queries, Parameters, [ Optional_parameters ])

结果列数据结构

根据函数的不同，返回的列也有多种。

返回单条路径的结果

适用于pgr_withPoints函数：

适用于pgr_dijkstraNear函数：

返回多条路径的结果

适用于对多条路径具有选择性的函数：

适用于对多条路径不具有选择性的函数：

成本函数的结果

适用于使用成本或成本矩阵的函数：

简介

快速入门文档帮助用户快速理解GanosBase Networking引擎的基本用法，包括扩展创建、建表、插入数据、更新属性、创建拓扑、路径查询等内容。

语法说明

• 创建扩展。

   CREATE Extension Ganos_Networking cascade;

  说明

  建议将扩展安装在public模式下，避免权限问题。

  CREATE extension Ganos_Networking WITH schema public cascade;

• 创建表。

   CREATE TABLE edge_table (
       id BIGSERIAL,
       dir character varying,
       source BIGINT,
       target BIGINT,
       cost FLOAT,
       reverse_cost FLOAT,
       capacity BIGINT,
       reverse_capacity BIGINT,
       category_id INTEGER,
       reverse_category_id INTEGER,
       x1 FLOAT,
       y1 FLOAT,
       x2 FLOAT,
       y2 FLOAT,
       the_geom geometry
   );

• 插入记录。

   INSERT INTO edge_table (
       category_id, reverse_category_id,
       cost, reverse_cost,
       capacity, reverse_capacity,
       x1, y1,
       x2, y2) VALUES
   (3, 1,    1,  1,  80, 130,   2,   0,    2, 1),
   (3, 2,   -1,  1,  -1, 100,   2,   1,    3, 1),
   (2, 1,   -1,  1,  -1, 130,   3,   1,    4, 1),
   (2, 4,    1,  1, 100,  50,   2,   1,    2, 2),
   (1, 4,    1, -1, 130,  -1,   3,   1,    3, 2),
   (4, 2,    1,  1,  50, 100,   0,   2,    1, 2),
   (4, 1,    1,  1,  50, 130,   1,   2,    2, 2),
   (2, 1,    1,  1, 100, 130,   2,   2,    3, 2),
   (1, 3,    1,  1, 130,  80,   3,   2,    4, 2),
   (1, 4,    1,  1, 130,  50,   2,   2,    2, 3),
   (1, 2,    1, -1, 130,  -1,   3,   2,    3, 3),
   (2, 3,    1, -1, 100,  -1,   2,   3,    3, 3),
   (2, 4,    1, -1, 100,  -1,   3,   3,    4, 3),
   (3, 1,    1,  1,  80, 130,   2,   3,    2, 4),
   (3, 4,    1,  1,  80,  50,   4,   2,    4, 3),
   (3, 3,    1,  1,  80,  80,   4,   1,    4, 2),
   (1, 2,    1,  1, 130, 100,   0.5, 3.5,  1.999999999999,3.5),
   (4, 1,    1,  1,  50, 130,   3.5, 2.3,  3.5,4);

• 更新表属性。

   UPDATE edge_table SET the_geom = st_makeline(st_point(x1,y1),st_point(x2,y2)),
   dir = CASE WHEN (cost>0 AND reverse_cost>0) THEN 'B'   -- both ways
              WHEN (cost>0 AND reverse_cost<0) THEN 'FT'  -- direction of the LINESSTRING
              WHEN (cost<0 AND reverse_cost>0) THEN 'TF'  -- reverse direction of the LINESTRING
              ELSE '' END;

• 创建拓扑。

   SELECT pgr_createTopology('edge_table',0.001);

• 查询最短路径。

   -- dijkstra 最短路径
   SELECT * FROM pgr_dijkstra(
       'SELECT id, source, target, cost, reverse_cost FROM edge_table',
       2, 3
   );
  
    seq | path_seq | node | edge | cost | agg_cost
   -----+----------+------+------+------+----------
      1 |        1 |    2 |    4 |    1 |        0
      2 |        2 |    5 |    8 |    1 |        1
      3 |        3 |    6 |    9 |    1 |        2
      4 |        4 |    9 |   16 |    1 |        3
      5 |        5 |    4 |    3 |    1 |        4
      6 |        6 |    3 |   -1 |    0 |        5
   (6 rows)
  
   -- astar 路径算法
   SELECT * FROM pgr_astar(
       'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2 FROM edge_table',
       2, 12,
       directed := false, heuristic := 2);
  
    seq | path_seq | node | edge | cost | agg_cost
   -----+----------+------+------+------+----------
      1 |        1 |    2 |    2 |    1 |        0
      2 |        2 |    3 |    3 |    1 |        1
      3 |        3 |    4 |   16 |    1 |        2
      4 |        4 |    9 |   15 |    1 |        3
      5 |        5 |   12 |   -1 |    0 |        4
   (5 rows)
  
   -- trsp 路径算法
   SELECT * FROM pgr_trsp(
           'SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost FROM edge_table',
           2, 7, false, false,
           'SELECT to_cost, target_id::int4,
           from_edge || coalesce('','' || via_path, '''') AS via_path
           FROM restrictions'
       );
  
    seq | id1 | id2 | cost
   -----+-----+-----+------
      0 |   2 |   4 |    1
      1 |   5 |  10 |    1
      2 |  10 |  12 |    1
      3 |  11 |  11 |    1
      4 |   6 |   8 |    1
      5 |   5 |   7 |    1
      6 |   8 |   6 |    1
      7 |   7 |  -1 |    0
   (8 rows)

• 删除扩展（可选）。

   Drop Extension Ganos_Networking cascade;

SQL参考

详细SQL手册请参见pgrouting 官方文档 。