Pgrouting求解大數(shù)據(jù)量最短路徑

實(shí)際工作中的一個(gè)場(chǎng)景，類似于要做一個(gè)像地圖那樣，指定起終點(diǎn)，給出所有可行路線，本來是自己實(shí)現(xiàn)的，使用圖的深度優(yōu)先算法，結(jié)果由于數(shù)據(jù)量太大了，直接把內(nèi)存算崩了。我也知道可以大而化小、分而治之、小則建立關(guān)系，可惜這樣一個(gè)好的數(shù)據(jù)結(jié)構(gòu)，我搞不出來。最終不得已，選用pgrouting作為替代品，但也跟原需求不太符合，這個(gè)是個(gè)求最優(yōu)的方式。

唉，不過是一個(gè)離了開源啥也干不了的廢物罷了。
也許，這才是許許多多CRUD碼農(nóng)，亟待突破的瓶頸！
所以，努力學(xué)習(xí)吧！

首先要有一個(gè)postgresql數(shù)據(jù)庫，并開啟postgis與pgrouting擴(kuò)展，這里不多贅述！查看具體的安裝過程。

導(dǎo)出 | OpenStreetMap

pgRouting通過osm2pgrouting加載osm地圖數(shù)據(jù)

github|管網(wǎng)連通性分析

pgr_dijkstra — pgRouting Manual (3.3)

pgRouting教程四：準(zhǔn)備數(shù)據(jù) - 知乎

pgrouting - 如何修復(fù) pgr_dijkstra 錯(cuò)誤，查詢必須返回列 ‘id’、‘source’、‘target’ 和 ‘cost’？ - 地理信息系統(tǒng)堆棧交換

postgresql對(duì)單引號(hào)進(jìn)行轉(zhuǎn)義

postgresql - 如何編寫一個(gè)不返回任何內(nèi)容的 postgres 存儲(chǔ)過程？ - 堆棧溢出

common table expression - PostgreSQL: Query has no destination for result data - Stack Overflow

創(chuàng)建觸發(fā)器-PostgreSQL輕松學(xué)-SJK66.COM

返回NULL的行級(jí)觸發(fā)器導(dǎo)致錯(cuò)誤：查詢沒有結(jié)果數(shù)據(jù)的目的地 - Thinbug

一、導(dǎo)入OSM數(shù)據(jù)

開源地圖導(dǎo)出 | OpenStreetMap，通過地圖導(dǎo)出自定義的位置信息。

進(jìn)入Linux，下載地圖信息，并導(dǎo)入信息。

# 忽略證書下載后重命名為map.osm wget https://www.openstreetmap.org/api/0.6/map?bbox=116.3849,39.9093,116.3969,39.9226 -O map.osm --no-check-certificate # 導(dǎo)入數(shù)據(jù) osm2pgrouting -f 地圖數(shù)據(jù) -h 數(shù)據(jù)庫host -U 數(shù)據(jù)庫用戶名 -d 數(shù)據(jù)庫名稱 -p 數(shù)據(jù)庫端口 -W 數(shù)據(jù)庫密碼 --conf=/usr/share/osm2pgrouting/mapconfig_for_cars.xml rm 地圖數(shù)據(jù)

導(dǎo)入后的輸出信息如下

[root@rollback ~]# osm2pgrouting -f map.osm -h 192.168.10.10 -U pgrouting -d pgrouting_test -p 5432 -W meethigher --conf=/usr/share/osm2pgrouting/mapconfig_for_cars.xml rm map.osm Execution starts at: Wed Apr 27 16:11:47 2022***************************************************COMMAND LINE CONFIGURATION * *************************************************** Filename = map.osm Configuration file = /usr/share/osm2pgrouting/mapconfig_for_cars.xml host = 192.168.10.10 port = 5432 dbname = pgrouting_test username = pgrouting schema= prefix = suffix = Don't drop tables Don't create indexes Don't add OSM nodes *************************************************** Testing database connection: pgrouting_test database connection successful: pgrouting_test Connecting to the database connection successCreating tables... TABLE: ways_vertices_pgr created ... OK. TABLE: ways created ... OK. TABLE: pointsofinterest created ... OK. TABLE: configuration created ... OK. Opening configuration file: /usr/share/osm2pgrouting/mapconfig_for_cars.xmlParsing configurationExporting configuration ...- Done Counting lines ...- Done Opening data file: map.osm total lines: 78998Parsing dataEnd Of fileFinish Parsing dataAdding auxiliary tables to database...Export Ways ...Processing 4493 ways: [**************************************************|] (100%) Total processed: 4493 Vertices inserted: 174 Split ways inserted 172Creating indexes ...Processing Points of Interest ... ######################### size of streets: 4493 Execution started at: Wed Apr 27 16:11:47 2022 Execution ended at: Wed Apr 27 16:11:47 2022 Elapsed time: 0.459 Seconds. User CPU time: -> 0.16 seconds #########################

推薦使用dbeaver打開，可以直接查看地圖數(shù)據(jù)，也是基于OpenStreetMap的。

因?yàn)镺penStreetMap下載的數(shù)據(jù)，本身已經(jīng)經(jīng)過拓?fù)涮幚砹?#xff0c;所以就可以直接進(jìn)行查詢。

-- 函數(shù)使用說明 pgr_dijkstra(Edges SQL, 起點(diǎn)編號(hào), 終點(diǎn)編號(hào) [, directed])-- 使用dijkstra查詢最短路徑 SELECT * FROM pgr_dijkstra('SELECT gid as id, source, target, cost FROM ways',30,56 );

起點(diǎn)編號(hào)source和終點(diǎn)編號(hào)source是pgrouting維護(hù)的。通過dbeaver可以直觀的看出起終點(diǎn)號(hào)。

二、Dijkstra最短路徑

使用自己創(chuàng)建的數(shù)據(jù)庫，來體驗(yàn)下整個(gè)流程。

-- 刪表 drop table if exists xiangwan;-- 建表,source、target、cost是pgrouting必需的字段 -- 拉跨帕瓦，頂碗人在哪里？ create table xiangwan ( id int, roadName varchar, region geometry, source int, target int, cost float )-- 創(chuàng)建索引，不然巨慢 create index if not exists pgr_source_idx on xiangwan("source"); create index if not exists pgr_target_idx on xiangwan("target");-- 導(dǎo)入數(shù)據(jù) insert into xiangwan ("id", "roadname", "region") values ('1', '我愛向晚1', 'LINESTRING(116.403245 39.927884,116.403317 39.926542)'); insert into xiangwan ("id", "roadname", "region") values ('2', '我愛向晚2', 'LINESTRING(116.403317 39.926542,116.400352 39.924245)'); insert into xiangwan ("id", "roadname", "region") values ('3', '我愛向晚3', 'LINESTRING(116.403317 39.926542,116.406676 39.925186)'); insert into xiangwan ("id", "roadname", "region") values ('4', '我愛向晚4', 'LINESTRING(116.400352 39.924245,116.403658 39.920856)'); insert into xiangwan ("id", "roadname", "region") values ('5', '我愛向晚5', 'LINESTRING(116.406676 39.925186,116.403658 39.920856)'); insert into xiangwan ("id", "roadname", "region") values ('6', '我愛向晚6', 'LINESTRING(116.403658 39.920856,116.403586 39.919113)');-- 計(jì)算更新權(quán)值，權(quán)值的計(jì)算方法有很多種，這里就取線的距離 update xiangwan set cost = st_length(region) where cost is null;-- 更新拓?fù)鋱D，執(zhí)行完畢后，再去看表里的source、target已經(jīng)根據(jù)誤差自動(dòng)進(jìn)行編號(hào)了。 select pgr_createTopology('xiangwan',0.000001,'region','id','source','target');-- 具體字段說明 -- 參數(shù)1:表名 -- 參數(shù)2:誤差緩沖值，兩個(gè)點(diǎn)的距離在這個(gè)距離內(nèi)，就算重合為一點(diǎn)。這個(gè)距離使用st_length計(jì)算 -- 參數(shù)3:該表的空間坐標(biāo)字段 -- 參數(shù)4:該表的主鍵 -- 參數(shù)5:空間起點(diǎn)編號(hào) -- 參數(shù)6:空間終點(diǎn)編號(hào) -- 參數(shù)7:看官方描述，默認(rèn)true -- 參數(shù)8:每次執(zhí)行都重建拓?fù)鋱D，默認(rèn)false select pgr_createTopology('xiangwan',0.000001,'region','id','source','target',rows_where := 'true', clean := 'true');-- 求最短路徑 -- 參數(shù)1:sql -- 參數(shù)2:起點(diǎn)source -- 參數(shù)3:重點(diǎn)target select * from pgr_dijkstra('select id, source, target, cost from xiangwan where roadname like $$%我愛向晚%$$',1,6 );

postgresql 單引號(hào)的轉(zhuǎn)義符是$$

上面的寫法就是select id, source, target, cost from xiangwan where roadname like ‘%我愛向晚%’

根據(jù)查詢結(jié)果可知，經(jīng)過的點(diǎn)號(hào)依次是1->2->3->5->6。

三、實(shí)際做法

因?yàn)槊坑袛?shù)據(jù)來了之后，就要對(duì)拓?fù)鋱D進(jìn)行一次維護(hù)(對(duì)cost、source、target的維護(hù))。

由于數(shù)據(jù)不常變化，這邊就想直接使用postgresql的觸發(fā)器實(shí)現(xiàn)。更主要的還是我懶得寫代碼維護(hù)了！

postgresql的觸發(fā)器比較反人類，必須要基于一個(gè)觸發(fā)器函數(shù)才行。這點(diǎn)跟mysql相比，從人性化的角度考慮，簡直被吊打。

-- 刪除函數(shù) drop function updateTopology();-- 創(chuàng)建維護(hù)拓?fù)鋱D函數(shù)，不想輸出內(nèi)容時(shí)，將select換成perform create or replace function updateTopology()returns trigger as $body$ begin update xiangwan set cost = st_length(region) where cost is null; perform pgr_createtopology('xiangwan',0.000001,'region','id','source','target'); return null; end; $body$ language plpgsql;-- 創(chuàng)建觸發(fā)器 create trigger maintainTopology after insert or update of region on xiangwanfor each statementexecute procedure updateTopology();-- 刪除觸發(fā)器 drop trigger if exists maintainTopology on xiangwan;

上面的那個(gè)update xiangwan where cost is null，這么寫其實(shí)有問題。

但是我的目的是只要有路徑能查出來就行，所以這邊特別精準(zhǔn)是哪條路徑對(duì)我作用不大。

而且，如果不加where cost is null，就會(huì)出現(xiàn)無限套娃的情況！

每次update之后，都要重新執(zhí)行觸發(fā)器。

總結(jié)

以上是生活随笔為你收集整理的PgRouting求解大数据量最短路径的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。