【重新發現PostgreSQL之美】- 27 無中生有

背景

場景:

•   路徑規劃: 大型商業綜合體, 自動駕駛, 虛拟現實.

•   共享出行(拼車), 配送排程(餐飲、包裹).

•   刑偵: 軌迹相遇分析

《重新發現PostgreSQL之美- 11 時空軌迹系統新冠&刑偵&預測》

挑戰:

•   傳統資料庫不支援路網資料, 需要move data到應用端進行計算.

•   現實中軌迹存在缺失點, 當需要分析軌迹相遇事件時, 準确度下降.

•   在共享出行拼單, 包裹和餐飲配送中存在一到多, 多到多的路徑規劃, 非常複雜傳統資料庫不支援.

PG 解決方案:

•   支援路網資料存儲: 點, 線. 支援道路正、反權重來表示路段通暢度.

•   内置多重路徑規劃算法, 支援one to one,one to many,many to one,many to many等算法.

pgrouting

https://docs.pgrouting.org/latest/en/index.html https://workshop.pgrouting.org/

資料庫路由優點：

•   相容更多用戶端, 都可以修改資料和屬性，例如QGIS通過JDBC、ODBC 或直接使用Pl/pgSQL。用戶端可以是PC 或移動裝置。

•   資料更新後, 全網可見. 無需預先計算。

•   路徑規劃中的變量: “成本”、“路段” 參數可以通過SQL 動态計算，其值可以來自多個字段或表。

◦                    例如路段施工、路段擁堵都可以實時回報.

核心功能, pgRouting 庫包含以下功能(算法)：

•   All Pairs Shortest Path, Johnson’s Algorithm

•   All Pairs Shortest Path, Floyd-Warshall Algorithm

•   Shortest Path A*

•   Bi-directional Dijkstra Shortest Path

•   Bi-directional A* Shortest Path

•   Shortest Path Dijkstra

•   Driving Distance

•   K-Shortest Path, Multiple Alternative Paths

•   K-Dijkstra, One to Many Shortest Path

•   Traveling Sales Person

•   Turn Restriction Shortest Path (TRSP)

例子

某個軌迹資訊:

point1, ts  

point2, ts  

...  

pointn, ts  

繪圖後發現缺失某些點, 出現飛行軌迹, 怎麼辦?以下是路網情況, cost可以表示為當時的道路通過耗時

pointx1, pointy1, cost, reverse_cost  

pointy1, pointz1, cost, reverse_cost  

...   

point??, point??, cost, reverse_cost  

無中生有:

采用one to one的算法的到缺失路徑

https://docs.pgrouting.org/latest/en/pgr_dijkstra.html

pgr_dijkstra(Edges SQL, start_vid,  end_vid [, directed])  

pgr_dijkstra(Edges SQL, start_vid,  end_vids [, directed])  

pgr_dijkstra(Edges SQL, start_vids, end_vid  [, directed]) 

pgr_dijkstra(Edges SQL, start_vids, end_vids [, directed])  

pgr_dijkstra(Edges SQL, Combinations SQL [, directed]) -- Proposed on v3.1  

RETURNS SET OF (seq, path_seq [, start_vid] [, end_vid], node, edge, cost, agg_cost)  

OR EMPTY SET  

Example

•   From vertex to vertex on a directed graph

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)  

參考

https://locatepress.com/pgrouting https://pgrouting.org/ https://www.openstreetmap.org/#map=4/36.96/104.17