本文介紹了路徑模型的用途、基本構成和快速入門等內容。
模型用途
簡介
路徑模型是一種以點、邊描述的圖結構,用于解決基于道路網的路徑規劃問題、電子地圖GPS導航路徑搜索規劃問題、路由問題等。路徑模型完全兼容PGRouting接口,支持已有應用的平滑遷移。路徑數據是由Edge和Node構成的幾何網絡圖,主要用于構建道路和交通網絡。
Ganos Networking是對象關系型數據庫PostgreSQL兼容版本(PolarDB PostgreSQL版(兼容Oracle))的一個時空引擎擴展,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 | 當前點的位置。值必須為[ |
結果列數據結構
根據函數的不同,返回的列也有多種。
返回單條路徑的結果
列名 | 類型 | 說明 |
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 官方文檔 。