基于pgrouting的路徑規(guī)劃處理方法
對(duì)于GIS業(yè)務(wù)來說，路徑規(guī)劃是非?；A(chǔ)的一個(gè)業(yè)務(wù)，一般公司如果處理，都會(huì)直接選擇調(diào)用已經(jīng)成熟的第三方的接口，比如高德、百度等。當(dāng)然其實(shí)路徑規(guī)劃的算法非常多，像比較著名的Dijkstra、A*算法等。當(dāng)然本篇文章不是介紹算法的，本文作者會(huì)根據(jù)pgrouting已經(jīng)集成的Dijkstra算法來，結(jié)合postgresql數(shù)據(jù)庫來處理最短路徑。
一、數(shù)據(jù)處理
路徑規(guī)劃的核心是數(shù)據(jù)，數(shù)據(jù)是一般的路網(wǎng)數(shù)據(jù)，但是我們拿到路網(wǎng)數(shù)據(jù)之后，需要對(duì)數(shù)據(jù)進(jìn)行處理，由于算法的思想是基于有向圖的原理，因此首先需要對(duì)數(shù)據(jù)做topo處理，通過topo我們其實(shí)就建立了路網(wǎng)中各條道路的頂點(diǎn)關(guān)系，下面是主要命令：
--開啟執(zhí)行路網(wǎng)topo的插件
create extension postgis;
create extension postgis_topology;
--數(shù)據(jù)創(chuàng)建拓?fù)?ALTER TABLE test_road ADD COLUMN source integer;
ALTER TABLE test_road ADD COLUMN target integer;
SELECT pgr_createTopology('test_road',0.00001, 'geom', 'gid');其中test_road是將路網(wǎng)數(shù)據(jù)導(dǎo)入到postgresql中的表名。
處理完topo之后，基本就夠用了，我們就可以借助pgrouting自帶的函數(shù)，其實(shí)有很多，我們選擇pgr_dijkstra
CREATE OR REPLACE FUNCTION public.pgr_dijkstra(
IN edges_sql text,
IN start_vid bigint,
IN end_vid bigint,
IN directed boolean,
OUT seq integer,
OUT path_seq integer,
OUT node bigint,
OUT edge bigint,
OUT cost double precision,
OUT agg_cost double precision)
RETURNS SETOF record AS
$BODY$
DECLARE
BEGIN
RETURN query SELECT *
FROM _pgr_dijkstra(_pgr_get_statement($1), start_vid, end_vid, directed, false);
END
$BODY$
LANGUAGE plpgsql VOLATILE
COST 100
ROWS 1000;
ALTER FUNCTION public.pgr_dijkstra(text, bigint, bigint, boolean)
OWNER TO postgres;從函數(shù)輸入?yún)?shù)可以看到，我們需要一個(gè)查詢sql,一個(gè)起始點(diǎn)、一個(gè)結(jié)束點(diǎn)、以及是否考慮方向，好了了解到調(diào)用函數(shù)輸入?yún)?shù)，我們就來寫這個(gè)函數(shù)。
二、原理分析
一般路徑規(guī)劃，基本都是輸入一個(gè)起點(diǎn)位置、一個(gè)終點(diǎn)位置然后直接規(guī)劃，那么對(duì)于我們來說，要想套用上面的函數(shù)，必須找出起點(diǎn)位置target ，以及終點(diǎn)位置的source，然后規(guī)劃根據(jù)找出的這兩個(gè)topo點(diǎn)，調(diào)用上面的函數(shù)，來返回自己所需要的結(jié)果。
如何根據(jù)起始點(diǎn)找到對(duì)應(yīng)的target呢，其實(shí)就是找離起點(diǎn)最近線的target，同理終點(diǎn)的source，其實(shí)就是找離終點(diǎn)最近線的source,當(dāng)然將這兩個(gè)點(diǎn)規(guī)劃規(guī)劃好之后，基本就可以了，但是最后還需要將起點(diǎn)到起點(diǎn)最近先的target連接起來，終點(diǎn)到終點(diǎn)最近線的source連接起來，這樣整個(gè)路徑規(guī)劃就算完成了。
下面我們來看具體的實(shí)現(xiàn)存儲(chǔ)過程：
CREATE OR REPLACE FUNCTION public.pgr_shortest_road(
IN startx double precision,
IN starty double precision,
IN endx double precision,
IN endy double precision,
OUT road_name character varying,
OUT v_shpath character varying,
OUT cost double precision)
RETURNS SETOF record AS
$BODY$
declare
v_startLine geometry;--離起點(diǎn)最近的線
v_endLine geometry;--離終點(diǎn)最近的線
v_startTarget integer;--距離起點(diǎn)最近線的終點(diǎn)
v_endSource integer;--距離終點(diǎn)最近線的起點(diǎn)
v_statpoint geometry;--在v_startLine上距離起點(diǎn)最近的點(diǎn)
v_endpoint geometry;--在v_endLine上距離終點(diǎn)最近的點(diǎn)
v_res geometry;--最短路徑分析結(jié)果
v_perStart float;--v_statpoint在v_res上的百分比
v_perEnd float;--v_endpoint在v_res上的百分比
v_rec record;
first_name varchar;
end_name varchar;
first_cost double precision;
end_cost double precision;
begin
--查詢離起點(diǎn)最近的線
execute 'select geom,target,name from china_road where
ST_DWithin(geom,ST_Geometryfromtext(''point('|| startx ||' ' || starty||')''),0.01)
order by ST_Distance(geom,ST_GeometryFromText(''point('|| startx ||' '|| starty ||')'')) limit 1'
into v_startLine ,v_startTarget,first_name;
--查詢離終點(diǎn)最近的線
execute 'select geom,source,name from china_road
where ST_DWithin(geom,ST_Geometryfromtext(''point('|| endx || ' ' || endy ||')''),0.01)
order by ST_Distance(geom,ST_GeometryFromText(''point('|| endx ||' ' || endy ||')'')) limit 1'
into v_endLine,v_endSource,end_name;
--如果沒找到最近的線，就返回null
if (v_startLine is null) or (v_endLine is null) then
return;
end if ;
select ST_ClosestPoint(v_startLine, ST_Geometryfromtext('point('|| startx ||' ' || starty ||')')) into v_statpoint;
select ST_ClosestPoint(v_endLine, ST_GeometryFromText('point('|| endx ||' ' || endy ||')')) into v_endpoint;
--計(jì)算距離起點(diǎn)最近線上的點(diǎn)在該線中的位置
select ST_Line_Locate_Point(st_linemerge(v_startLine), v_statpoint) into v_perStart;
select ST_Line_Locate_Point(st_linemerge(v_endLine), v_endpoint) into v_perEnd;
select ST_Distance_Sphere(v_statpoint,ST_PointN(ST_GeometryN(v_startLine,1), ST_NumPoints(ST_GeometryN(v_startLine,1)))) into first_cost;
select ST_Distance_Sphere(ST_PointN(ST_GeometryN(v_endLine,1),1),v_endpoint) into end_cost;
if (ST_Intersects(st_geomfromtext('point('|| startx ||' '|| starty ||') '), v_startLine) and ST_Intersects(st_geomfromtext('point('|| endx ||' '|| endy ||') '), v_startLine)) then
select ST_Distance_Sphere(v_statpoint, v_endpoint) into first_cost;
select ST_Line_Locate_Point(st_linemerge(v_startLine), v_endpoint) into v_perEnd;
for v_rec in
select ST_Line_SubString(st_linemerge(v_startLine), v_perStart,v_perEnd) as point,COALESCE(end_name,'無名路') as name,end_cost as cost loop
v_shPath:= ST_AsGeoJSON(v_rec.point);
cost:= v_rec.cost;
road_name:= v_rec.name;
return next;
end loop;
return;
end if;
--最短路徑
for v_rec in
(select ST_Line_SubString(st_linemerge(v_startLine),v_perStart,1) as point,COALESCE(first_name,'無名路') as name,first_cost as cost
union all
SELECT st_linemerge(b.geom) as point,COALESCE(b.name,'無名路') as name,b.length as cost
FROM pgr_dijkstra(
'SELECT gid as id, source, target, length as cost FROM china_road
where st_intersects(geom,st_buffer(st_linefromtext(''linestring('||startx||' ' || starty ||','|| endx ||' ' || endy ||')''),0.05))',
v_startTarget, v_endSource , false
) a, china_road b
WHERE a.edge = b.gid
union all
select ST_Line_SubString(st_linemerge(v_endLine),0,v_perEnd) as point,COALESCE(end_name,'無名路') as name,end_cost as cost)
loop
v_shPath:= ST_AsGeoJSON(v_rec.point);
cost:= v_rec.cost;
road_name:= v_rec.name;
return next;
end loop;
end;
$BODY$
LANGUAGE plpgsql VOLATILE STRICT;上面這種實(shí)現(xiàn)，是將所有查詢道路返回一個(gè)集合，然后客戶端來將各個(gè)線路進(jìn)行合并，這種方式對(duì)最終效率影響比較大，所以一般會(huì)在函數(shù)中將道路何合并為一條道路，我們可以使用postgis的st_union函數(shù)來處理，小編經(jīng)過長(zhǎng)時(shí)間的試驗(yàn)，在保證效率和準(zhǔn)確性的情況下，對(duì)上面的存儲(chǔ)過程做了很多優(yōu)化，最終得出了如下：
CREATE OR REPLACE FUNCTION public.pgr_shortest_road(
startx double precision,
starty double precision,
endx double precision,
endy double precision)
RETURNS geometry AS
$BODY$
declare
v_startLine geometry;--離起點(diǎn)最近的線
v_endLine geometry;--離終點(diǎn)最近的線
v_perStart float;--v_statpoint在v_res上的百分比
v_perEnd float;--v_endpoint在v_res上的百分比
v_shpath geometry;
distance double precision;
bufferInstance double precision;
bufferArray double precision[];
begin
execute 'select geom,
case china_road.direction
when ''3'' then
source
else
target
end
from china_road where
ST_DWithin(geom,ST_Geometryfromtext(''point('|| startx ||' ' || starty||')'',4326),0.05)
AND width::double precision >= '||roadWidth||'
order by ST_Distance(geom,ST_GeometryFromText(''point('|| startx ||' '|| starty ||')'',4326)) limit 1'
into v_startLine;
execute 'select geom,
case china_road.direction
when ''3'' then
target
else
source
end
from china_road
where ST_DWithin(geom,ST_Geometryfromtext(''point('|| endx || ' ' || endy ||')'',4326),0.05)
AND width::double precision >= '||roadWidth||'
order by ST_Distance(geom,ST_GeometryFromText(''point('|| endx ||' ' || endy ||')'',4326)) limit 1'
into v_endLine;
if (v_startLine is null) or (v_endLine is null) then
return null;
end if;
if (ST_equals(v_startLine,v_endLine)) then
select ST_LineLocatePoint(st_linemerge(v_startLine), ST_Geometryfromtext('point('|| startx ||' ' || starty ||')',4326)) into v_perStart;
select ST_LineLocatePoint(st_linemerge(v_endLine), ST_Geometryfromtext('point('|| endx ||' ' || endy ||')',4326)) into v_perEnd;
select ST_LineSubstring(st_linemerge(v_startLine),v_perStart,v_perEnd) into v_shPath;
return v_shPath;
end if;
select ST_DistanceSphere(st_geomfromtext('point('|| startx ||' ' || starty ||')',4326),st_geomfromtext('point('|| endx ||' ' || endy ||')',4326)) into distance;
if ((distance / 1000) > 50) then
bufferArray := ARRAY[0.1,0.2,0.3,0.5,0.8];
else
bufferArray := ARRAY[0.02,0.05,0.08,0.1];
end if;
forEACH bufferInstance IN ARRAY bufferArray
LOOP
select _pgr_shortest_road(startx,starty,endx,endy,bufferInstance) into v_shPath;
if (v_shPath is not null) then
return v_shPath;
end if;
end loop;
end;
$BODY$
LANGUAGE plpgsql VOLATILE STRICT
COST 100;
ALTER FUNCTION public.pgr_shortest_road(double precision, double precision, double precision, double precision )
OWNER TO postgres;
DROP FUNCTION public._pgr_shortest_road(double precision, double precision, double precision, double precision, double precision);上面的函數(shù)，其實(shí)對(duì)于大部分情況下的操作，基本可以滿足了。
三、效率優(yōu)化
其實(shí)在數(shù)據(jù)查詢方面，我們使用的是起點(diǎn)和終點(diǎn)之間的線性緩沖來提高效率，如下：
SELECT gid as id, source, target, cost,rev_cost as reverse_cost FROM china_road
where geom && st_buffer(st_linefromtext(''linestring('||startx||' ' || starty ||','|| endx ||' ' || endy ||')'',4326),'||bufferDistance||')當(dāng)然這在大部分情況下，依舊是不錯(cuò)的，然后在有些情況下，并不能起到很好的作用，因?yàn)槿绻瘘c(diǎn)和終點(diǎn)之間道路偏移較大（比如直線上的山脈較多的時(shí)候，路就會(huì)比較繞），這個(gè)時(shí)候，可能會(huì)增大緩沖距離，而增加緩沖距離就會(huì)導(dǎo)致，部分區(qū)域的查詢量增大，繼而影響效率，因此其實(shí)我們可以考慮使用mapid這個(gè)參數(shù)，這個(gè)參數(shù)從哪來呢，一般我們拿到的路網(wǎng)數(shù)據(jù)都會(huì)這個(gè)字段，我們只需要生成一個(gè)區(qū)域表，而這個(gè)區(qū)域表就倆個(gè)字段，一個(gè)是mapid，一個(gè)是這個(gè)mapid的polygon范圍，這樣子，上面的查詢條件，就可以換成如下：
SELECT gid as id, source, target, cost,rev_cost as reverse_cost FROM china_road
where mapid in (select mapid from maps where geom && st_buffer(st_linefromtext(''linestring('||startx||' ' || starty ||','|| endx ||' ' || endy ||')''),'||bufferDistance||'))這樣就可以在很大程度上提高效率。
四、數(shù)據(jù)bug處理
其實(shí)有時(shí)候我們拿到的路網(wǎng)數(shù)據(jù)，并不是非常的準(zhǔn)確，或者說是錄入的有瑕疵，我自己遇到的就是生成的topo數(shù)據(jù)，本來一條路的target應(yīng)該和它相鄰路的source的點(diǎn)重合，然后實(shí)際卻是不一樣，這就導(dǎo)致最終規(guī)劃處的有問題，因此，簡(jiǎn)單寫了一個(gè)處理這種問題的函數(shù)
CREATE OR REPLACE FUNCTION public.modity_road_data()
RETURNS void AS
$BODY$
declare
n integer;
begin
for n IN (select distinct(source) from china_road ) loop
update china_road
set geom = st_multi(st_addpoint(ST_geometryN(geom,1),
(select st_pointn(ST_geometryN(geom,1),1) from china_road where source = n
limit 1),
st_numpoints(ST_geometryN(geom,1))))
where target = n;
end loop;
end;
$BODY$
LANGUAGE plpgsql VOLATILE STRICT
COST 100;
ALTER FUNCTION public.modity_road_data()
OWNER TO postgres;
五、后續(xù)規(guī)劃
上面的函數(shù)已在百萬數(shù)據(jù)中做過驗(yàn)證，后續(xù)還會(huì)驗(yàn)證千萬級(jí)別的路網(wǎng)數(shù)據(jù)，當(dāng)然這種級(jí)別，肯定要在策略上做一些調(diào)整了，比如最近測(cè)試的全國(guó)路網(wǎng)中，先規(guī)劃起點(diǎn)至起點(diǎn)最近的高速入口，在規(guī)劃終點(diǎn)至終點(diǎn)最近的高速出口，然后再高速路網(wǎng)上規(guī)劃高速入口到高速出口的路徑，這樣發(fā)現(xiàn)效率提升不少，當(dāng)然，這里面還有很多邏輯和業(yè)務(wù)，等所有東西都驗(yàn)證完畢，會(huì)再出一版，千萬級(jí)別路徑規(guī)劃的文章。
到此這篇關(guān)于基于pgrouting的路徑規(guī)劃處理的文章就介紹到這了,更多相關(guān)pgrouting的路徑規(guī)劃內(nèi)容請(qǐng)搜索本站以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持本站！
版權(quán)聲明：本站文章來源標(biāo)注為YINGSOO的內(nèi)容版權(quán)均為本站所有，歡迎引用、轉(zhuǎn)載，請(qǐng)保持原文完整并注明來源及原文鏈接。禁止復(fù)制或仿造本網(wǎng)站，禁止在非www.sddonglingsh.com所屬的服務(wù)器上建立鏡像，否則將依法追究法律責(zé)任。本站部分內(nèi)容來源于網(wǎng)友推薦、互聯(lián)網(wǎng)收集整理而來，僅供學(xué)習(xí)參考，不代表本站立場(chǎng)，如有內(nèi)容涉嫌侵權(quán)，請(qǐng)聯(lián)系alex-e#qq.com處理。
關(guān)注官方微信