基于pgrouting的路径规划处理

Python微信订餐小程序课程视频

https://blog.csdn.net/m0_56069948/article/details/122285951

Python实战量化交易理财系统

https://blog.csdn.net/m0_56069948/article/details/122285941
对于GIS业务来说，路径规划是非常基础的一个业务，一般公司如果处理，都会直接选择调用已经成熟的第三方的接口，比如高德、百度等。当然其实路径规划的算法非常多，像比较著名的Dijkstra、A*算法等。当然本篇文章不是介绍算法的，本文作者会根据pgrouting已经集成的Dijkstra算法来，结合postgresql数据库来处理最短路径。

一、数据处理

路径规划的核心是数据，数据是一般的路网数据，但是我们拿到路网数据之后，需要对数据进行处理，由于算法的思想是基于有向图的原理，因此首先需要对数据做topo处理，通过topo我们其实就建立了路网中各条道路的顶点关系，下面是主要命令：

--开启执行路网topo的插件
create extension postgis;
create extension postgis\_topology;
--数据创建拓扑
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是将路网数据导入到postgresql中的表名。

处理完topo之后，基本就够用了，我们就可以借助pgrouting自带的函数，其实有很多，我们选择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;

从函数输入参数可以看到，我们需要一个查询sql,一个起始点、一个结束点、以及是否考虑方向，好了了解到调用函数输入参数，我们就来写这个函数。

二、原理分析

一般路径规划，基本都是输入一个起点位置、一个终点位置然后直接规划，那么对于我们来说，要想套用上面的函数，必须找出起点位置target ，以及终点位置的source，然后规划根据找出的这两个topo点，调用上面的函数，来返回自己所需要的结果。

如何根据起始点找到对应的target呢，其实就是找离起点最近线的target，同理终点的source，其实就是找离终点最近线的source,当然将这两个点规划规划好之后，基本就可以了，但是最后还需要将起点到起点最近先的target连接起来，终点到终点最近线的source连接起来，这样整个路径规划就算完成了。

下面我们来看具体的实现存储过程：

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;--离起点最近的线 
v\_endLine geometry;--离终点最近的线 
v\_startTarget integer;--距离起点最近线的终点 
v\_endSource integer;--距离终点最近线的起点 
v\_statpoint geometry;--在v\_startLine上距离起点最近的点 
v\_endpoint geometry;--在v\_endLine上距离终点最近的点 
v\_res geometry;--最短路径分析结果 
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 
--查询离起点最近的线 
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; 
--查询离终点最近的线 
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; 

--计算距离起点最近线上的点在该线中的位置
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;

上面这种实现，是将所有查询道路返回一个集合，然后客户端来将各个线路进行合并，这种方式对最终效率影响比较大，所以一般会在函数中将道路何合并为一条道路，我们可以使用postgis的st_union函数来处理，小编经过长时间的试验，在保证效率和准确性的情况下，对上面的存储过程做了很多优化，最终得出了如下：

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;--离起点最近的线 
 v\_endLine geometry;--离终点最近的线 
 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);

上面的函数，其实对于大部分情况下的操作，基本可以满足了。

三、效率优化

其实在数据查询方面，我们使用的是起点和终点之间的线性缓冲来提高效率，如下：

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||')

当然这在大部分情况下，依旧是不错的，然后在有些情况下，并不能起到很好的作用，因为如果起点和终点之间道路偏移较大（比如直线上的山脉较多的时候，路就会比较绕），这个时候，可能会增大缓冲距离，而增加缓冲距离就会导致，部分区域的查询量增大，继而影响效率，因此其实我们可以考虑使用mapid这个参数，这个参数从哪来呢，一般我们拿到的路网数据都会这个字段，我们只需要生成一个区域表，而这个区域表就俩个字段，一个是mapid，一个是这个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||'))

这样就可以在很大程度上提高效率。

四、数据bug处理

其实有时候我们拿到的路网数据，并不是非常的准确，或者说是录入的有瑕疵，我自己遇到的就是生成的topo数据，本来一条路的target应该和它相邻路的source的点重合，然后实际却是不一样，这就导致最终规划处的有问题，因此，简单写了一个处理这种问题的函数

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;

五、后续规划

上面的函数已在百万数据中做过验证，后续还会验证千万级别的路网数据，当然这种级别，肯定要在策略上做一些调整了，比如最近测试的全国路网中，先规划起点至起点最近的高速入口，在规划终点至终点最近的高速出口，然后再高速路网上规划高速入口到高速出口的路径，这样发现效率提升不少，当然，这里面还有很多逻辑和业务，等所有东西都验证完毕，会再出一版，千万级别路径规划的文章。