文档

路径模型

更新时间:

本文介绍了路径模型的用途、基本构成和快速入门等内容。

模型用途

简介

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

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

功能概述

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

  • Johnson算法。

  • Floyd-Warshall算法。

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

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

  • 旅行推销员算法。

  • Prim算法。

  • Kruskal算法。

  • K最短路径算法。

  • 流量(Flow)分析。

  • 图拓扑(Topology)相关操作。

  • 图部件(Component) 相关操作。

  • 图收缩。

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

同时,部分函数还支持设置成本(cost)或成本矩阵(cost matrix)进行计算。

主要业务场景

Ganos Networking的使用场景非常广泛:

  • 最优路线规划

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

  • 地理空间分析

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

  • 交通流量管理

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

基本构成

图的概念

图是一个有序对,遵循G = (V ,E),其中:

  • V表示图的顶点集合,V中的元素称为顶点(vertex)或节点(node)。

  • E ⊆ {( u, v ) | u , v ∈ V }

存在无向图、简单无向图、有向图、简单有向图等多种类型。

在Ganos中,有两种图的表示方式:

  • 成本图。

  • 正反向成本图。

两种图在执行计算时都可以指定为有向或无向。

成本图

成本图在数据库内具有如下结构:

列名

描述

id

边的唯一标识符。

source

该条边的起点。

target

该条边的终点。

cost

从起点到终点的边的权重(成本)。

正反向成本图

正反向成本图在数据库内具有如下结构:

列名

描述

id

某条边的唯一标识符。

source

该条边的起点。

target

该条边的终点。

cost

从起点到终点的边的权重(成本)。

reverse_cost

从终点到起点的边的权重(成本)。

函数体结构

Ganos Networking兼容Pgrouting标准,函数体的一般结构为:

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

其中:

  • Inner_queries:内部查询,是SQL字符串,用于构建函数所需要的数据。

  • Parameters:参数,函数所需的附加强制参数。

  • Optional_parameters:可选参数,省略时具有默认值。

一个函数可能有不同的重载。常见的重载方式为:

  • 一对一: 从一个起点导航到一个终点 。

  • 一对多:从一个起点导航到多个终点 。

  • 多对一:从多个起点导航到一个终点 。

  • 多对多:从多个起点导航到多个终点 。

  • 组合:从多个不同的起点导航到多个不同的终点,每个元组指定一对起点和终点。

内部查询依赖的数据结构

用户需要构建内部查询以将图结构传递给函数模型。按需求类型,可将内部查询分为如下几种:

  • 边查询(Edge SQL)。

  • 通用边查询:适用于Dijkstra/双向Dijkstra最短路径算法。

  • 不带ID的通用边查询:适用于全对(All Pairs)算法。

  • 带有X/Y值的通用边查询:适用于AStar/ 双向AStar最短路径算法。

  • 组合查询 (Combinations SQL)。

  • 限制查询(Restrictions SQL)。

  • 点查询(Points SQL)。

通用边查询

列名

类型

默认值

说明

id

integer

边的唯一标识符。

source

integer

该条边的起点。

target

integer

该条边的终点

cost

numeric

边的权重。

reverse_cost

numeric

-1

从终点到起点的边的权重。

当为负值时边\((target \rightarrow source)\)不存在于图中。

不带ID的边查询

列名

类型

默认值

说明

source

integer

该条边的起点。

target

integer

该条边的终点

cost

numeric

边的权重。

reverse_cost

numeric

-1

从终点到起点的边的权重。

当为负值时边\((target \rightarrow source)\)不存在于图中。

带有X/Y值的边查询

列名

类型

默认值

说明

source

integer

该条边的起点。

target

integer

该条边的终点

cost

numeric

边的权重。

当为负值时边\((source \rightarrow target)\)不存在于图中。

reverse_cost

numeric

-1

从终点到起点的边的权重。

当为负值时边\((target \rightarrow source)\)不存在于图中。

x1

numeric

边的起点X坐标。

y1

numeric

边的起点Y坐标。

x2

numeric

边的终点X坐标。

y2

numeric

边的终点Y坐标。

限制查询

列名

类型

默认值

说明

path

integer array

描述所有不可通过边的ID的序列。

cost

numeric

通行于不可通过边的成本。

点查询

列名

类型

默认值

说明

pid

integer

auto value

点的唯一标识符。

edge_id

integer

距离该点最近的边的唯一标识。

fraction

numeric

点在该边的相对位置。值必须位于[0,1]之间。

side

char

b

当前点的位置。值必须为[b(两侧),r(右侧),l(左侧)]中的一个。若为NULL,则视为b

结果列数据结构

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

返回单条路径的结果

列名

类型

说明

seq

integer

从1开始的顺序值。

path_seq

integer

在整个路径中的相对位置。从1开始的顺序值。

[start_vid]

big integer

起始顶点的唯一标识符。仅在查询中有多个起始顶点时返回。

[end_vid]

big integer

结束顶点的唯一标识符。仅在查询中有多个结束顶点时返回。

node

big integer

从"start_vid"到"end_vid"路径中节点的标识符。

edge

big integer

从当前节点到路径序列中的下一个节点的边的标识符。-1表示路径的最后一个节点。

cost

float

从当前节点到路径序列中的下一个节点的成本。

agg_cost

float

从"start_vid"到"node"的总成本。

适用于pgr_withPoints函数:

列名

类型

说明

seq

integer

从1开始的顺序值。

path_seq

integer

在整个路径中的相对位置。从1开始的顺序值。

[start_vid]

big integer

起始顶点(Vertex)/点(Point)的唯一标识符。仅在查询中有多个起始顶点时返回。

  • 当为正数时是起始顶点的标识符。

  • 当为负数时是起始点的标识符。

[end_vid]

big integer

结束顶点(Vertex)/点(Point)的唯一标识符。仅在查询中有多个起始顶点时返回。

  • 当为正数时是结束顶点的标识符。

  • 当为负数时是结束点的标识符。

node

big integer

从"start_vid"到"end_vid"路径中节点的标识符。

  • 当为正数时是顶点的标识符。

  • 当为负数时是点的标识符。

edge

big integer

从当前节点到路径序列中的下一个节点的边的标识符。-1表示路径的最后一个节点。

cost

float

从当前节点到路径序列中的下一个节点的成本。

agg_cost

float

从"start_vid"到"node"的总成本。0表示路径的第一条记录。

适用于pgr_dijkstraNear函数:

列名

类型

说明

seq

integer

从1开始的顺序值。

path_seq

integer

在整个路径中的相对位置。从1开始。

start_vid

big integer

当前路径起始顶点的唯一标识符。

end_vid

big integer

当前路径结束顶点的唯一标识符。

node

big integer

从"start_vid"到"end_vid"路径中节点的标识符。

edge

big integer

从当前节点到路径序列中的下一个节点的边的标识符。 -1表示路径的最后一个节点。

cost

float

从当前节点到路径序列中的下一个节点的成本。

agg_cost

float

从"start_vid"到"node"的总成本。

返回多条路径的结果

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

列名

类型

说明

seq

integer

从1开始的顺序值。

path_id

integer

路径的唯一标识符。

从"start_vid"到"end_vid"路径的第一个路径的ID为1。

path_seq

integer

在整个路径中的相对位置。从1开始的顺序值。

[start_vid]

big integer

起始顶点的唯一标识符。仅在查询中有多个起始顶点时返回。

[end_vid]

big integer

结束顶点的唯一标识符。仅在查询中有多个结束顶点时返回。

node

big integer

从"start_vid"到"end_vid"路径中节点的标识符。

edge

big integer

从当前节点到路径序列中的下一个节点的边的标识符。 -1表示路径的最后一个节点。

cost

float

从当前节点到路径序列中的下一个节点的成本。

agg_cost

float

从"start_vid"到"node"的总成本。

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

列名

类型

说明

seq

integer

从1开始的顺序值。

path_id

integer

路径的唯一标识符。

从"start_vid"到"end_vid"路径的第一个路径的ID为1。

path_seq

integer

在整个路径中的相对位置。从1开始。

start_vid

big integer

起始顶点的唯一标识符。

end_vid

big integer

结束顶点的唯一标识符。

node

big integer

从"start_vid"到"end_vid"路径中节点的标识符。

edge

big integer

从当前节点到路径序列中的下一个节点的边的标识符。 -1表示路径的最后一个节点。

cost

float

从当前节点到路径序列中的下一个节点的成本。

agg_cost

float

从"start_vid"到"node"的总成本。

成本函数的结果

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

列名

类型

说明

start_vid

big integer

起始顶点的唯一标识符。

end_vid

big integer

结束顶点的唯一标识符。

agg_cost

float

从"start_vid"到"end_vid"的路径的总成本。

快速入门

简介

快速入门文档帮助用户快速理解Ganos 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 官方文档