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 官方文檔 。