[pgrouting-users] best/fastest way to calculate thousands of trsp routes
Vicky Vergara
vicky at georepublic.de
Tue Apr 25 12:06:21 PDT 2017
He is using ordinace surveay, he said so in this twit
On Tue, Apr 25, 2017 at 12:36 PM, Stephen Woodbridge <
woodbri at swoodbridge.com> wrote:
> Hi Ross,
>
> Out of curiosity, what data are you using? Ordinance Survey? or OSM or
> something else.
>
> We hope to have a GSoC student do some work on the TRSP code. Ideally, we
> would like to migrate that code to use boost graph and to bring it in
> alignment with the other Dijkstra functions.
>
> Most real world routing application need support for turn restriction, OSM
> has been adding them but it will be a while before they are well
> represented in most areas and that leaves data commercial data sets as the
> only source for routable data that contains turn restrictions. I pretty
> sure that Ordinance Survey has them as does Nokia HERE.
>
> Thanks for sharing you stored procedure, I'm sure others can learn a lot
> from it.
>
> Best regards,
> -Steve
>
>
> On 4/25/2017 12:15 PM, McDonaldR wrote:
>
>> Hi Steve
>>
>> Thanks for the pointers - I've got it working now. It's much slower than
>> node to node (about 0.8s per route compared to about 0.3s per route) but a
>> more accurate result.
>>
>> The function FWIW:
>>
>> CREATE OR REPLACE FUNCTION corporate.pupil_journeys_routes2()
>> RETURNS character varying AS
>> $BODY$
>> DECLARE
>>
>> cur_pupil refcursor;
>> v_pid integer;
>> v_seid integer;
>> v_spos float8;
>> v_teid integer;
>> v_tpos float8;
>> v_geom geometry;
>> v_sql varchar(1000);
>>
>> BEGIN
>> OPEN cur_pupil FOR EXECUTE format('SELECT pupilid, source_eid,
>> source_pos, target_eid, target_pos FROM edn_pupilschoolroute WHERE pupil_nn
>> IS NOT NULL LIMIT 1000');
>> LOOP
>> FETCH cur_pupil INTO v_pid, v_seid, v_spos, v_teid, v_tpos;
>> EXIT WHEN NOT FOUND;
>> RAISE NOTICE 'Processing pupil % journey...', v_pid;
>> WITH results AS (
>> SELECT d.seq, d.id1 AS _node, d.id2 AS _edge, cost,
>> r.centrelinegeometry AS geometry FROM pgr_trsp('
>> SELECT ogc_fid AS id,
>> source::integer,
>> target::integer,
>> cost_len::double precision AS cost,
>> rcost_len::double precision AS reverse_cost
>> FROM hw_roadlink'::text, -- the trsp route
>> v_seid, --pupil source edge id
>> v_spos, --source edge position
>> v_teid, --school target edge id
>> v_tpos, --target edge position
>> true, --directed
>> true, --reverse costs
>> 'select to_cost, teid as target_id,
>> feid||coalesce('',''||via,'''') as via_path from
>> hw_nt_restrictions'::text) AS d
>> INNER JOIN hw_roadlink r ON d.id2 = r.ogc_fid
>> ORDER BY d.seq),
>> max_seq AS (
>> SELECT max(seq) AS max_seq FROM results
>> ),
>> network AS
>> (
>> SELECT ogc_fid AS id, source, target FROM hw_roadlink a, results
>> WHERE a.ogc_fid = results._edge
>> ),
>> path_geom AS
>> (
>> (SELECT ST_LineSubstring(geometry,v_spos,1.0) AS geometry -- source
>> edge and first row
>> FROM results, network
>> WHERE seq = (SELECT min(seq) FROM results)
>> AND network.target = (SELECT _node FROM results WHERE seq = 1)
>> AND network.id = (SELECT _edge FROM results WHERE seq = 0)
>> UNION
>> SELECT ST_LineSubstring(ST_Reverse(geometry),v_spos,1.0) AS geometry
>> -- source edge and first row
>> FROM results, network
>> WHERE seq = (SELECT min(seq) FROM results)
>> AND network.source = (SELECT _node FROM results WHERE seq = 1)
>> AND network.id = (SELECT _edge FROM results WHERE seq = 0)
>> )
>> UNION
>> (SELECT ST_LineSubstring(geometry,0.0,1.0 - v_tpos) AS geometry --
>> target edge and last row
>> FROM results, network
>> WHERE seq = (SELECT max(seq) FROM results)
>> AND network.source = (SELECT _node FROM results, max_seq WHERE seq =
>> max_seq)
>> AND network.id = (SELECT _edge FROM results, max_seq WHERE seq =
>> max_seq)
>> UNION
>> SELECT ST_LineSubstring(ST_Reverse(geometry),0.0,1.0 - v_tpos) AS
>> geometry -- target edge and last row
>> FROM results, network
>> WHERE seq = (SELECT max(seq) FROM results)
>> AND network.target = (SELECT _node FROM results, max_seq WHERE seq =
>> max_seq)
>> AND network.id = (SELECT _edge FROM results, max_seq WHERE seq =
>> max_seq)
>> )
>> UNION
>> SELECT geometry -- intermediate edges and rows
>> FROM results WHERE seq NOT IN ((SELECT max(seq) FROM results),(SELECT
>> min(seq) FROM results))
>> )
>> SELECT ST_Multi(ST_Union(geometry)) AS geometry FROM path_geom INTO
>> v_geom;
>>
>> -- insert route cost into pupil data table
>> EXECUTE format('INSERT INTO %s(pupilid,geometry) VALUES
>> ($1,$2)','corporate.edn_pupilroutes2')
>> USING v_pid, v_geom;
>>
>> END LOOP;
>> RETURN 'Oooh, get in!';
>> CLOSE cur_pupil;
>> END;
>> $BODY$
>> LANGUAGE plpgsql VOLATILE
>> COST 100;
>>
>>
>>
>>
>>
>>
>> -----Original Message-----
>> From: Pgrouting-users [mailto:pgrouting-users-bounces at lists.osgeo.org]
>> On Behalf Of Stephen Woodbridge
>> Sent: 24 April 2017 15:23
>> To: pgrouting-users at lists.osgeo.org
>> Subject: Re: [pgrouting-users] best/fastest way to calculate thousands of
>> trsp routes
>>
>> On 4/24/2017 4:55 AM, McDonaldR wrote:
>>
>>> Thanks Steve
>>>
>>> The function to get the source and target points on to the nearest
>>> edges gives a much better result than using nearest node. Now I just
>>> need to work out how to get the geometry of the route from these
>>> projected points.
>>>
>>
>> For the first and last edgeid in the result, use the linear referencing
>> functions to split that edge and keep the part you need instead of the
>> whole thing. the "pos" can be used as the split location on the edge.
>>
>> -Steve
>>
>> Thanks very much for the help
>>>
>>> Ross
>>>
>>> -----Original Message----- From: Pgrouting-users
>>> [mailto:pgrouting-users-bounces at lists.osgeo.org] On Behalf Of Stephen
>>> Woodbridge Sent: 20 April 2017 16:50 To:
>>> pgrouting-users at lists.osgeo.org Subject: Re: [pgrouting-users]
>>> best/fastest way to calculate thousands of trsp routes
>>>
>>> On 4/20/2017 6:49 AM, McDonaldR wrote:
>>>
>>>> Hi List,
>>>>
>>>> I’m running pgRouting 2.1 with PostGIS 2.2.2 on PostgreSQL 9.2.20.
>>>>
>>>> I have 16,000 pupils going to 57 schools. I have a network with turn
>>>> restrictions. I have a function (below) that loops through all the
>>>> pupils and calculates a TRSP route and updates the pupil table with
>>>> the route cost. I have some questions too.
>>>>
>>>> 1.It’s going to take ~ 2 hours to process all the pupils. Will it
>>>> make things faster if I created, say, 4 functions that each processed
>>>> a different set of pupils? I have a multicore server and memory to
>>>> spare. I have to run this for time and distance and also for all the
>>>> pupils assigned an “optimally located” school. What’s the
>>>> best/fastest way to do this?
>>>>
>>>
>>> Yes, this sounds reasonable.
>>>
>>> 2.I pre-processed the pupil data to assign each pupil the nearest
>>>> node on the network. Some pupils in rural areas are a mile from the
>>>> nearest node and are assigned the node at the end furthest from the
>>>> school. How would I use the pgr_trsp with edges and edge position to
>>>> create a position for each pupil at a point on the nearest edge?
>>>>
>>>
>>> Here is a function that might be useful, or you might modify it for
>>> your specific needs. tol is maximum search distance in degrees, you
>>> can estimate this degrees = meters/111120.0. It returns the edge_id,
>>> pos on the that edge and these can be used to args to trsp.
>>>
>>> -Steve W
>>>
>>> create or replace function pointToEdgePos(edge_table text, lon float8,
>>> lat float8, tol float8, OUT edge_id integer, OUT pos float8) returns
>>> record as $body$ -- ASSUMPTIONS -- * edge_table as columns "gid" and
>>> "geom" -- * edge_able.geom uses srid=4326 declare rr record; pct
>>> float8; pnt geometry; geom geometry;
>>>
>>> begin -- create a point from lon, lat pnt :=
>>> st_setsrid(st_makepoint(lon,lat), 4326);
>>>
>>> -- set the error condition edge_id := null; pos := -1.0;
>>>
>>> -- find the closest edge within tol distance execute 'select * from '
>>> || _pgr_quote_ident(edge_table) || ' where st_dwithin(''' ||
>>> pnt::text || '''::geometry, geom, ' || tol || ') order by
>>> st_distance(''' || pnt::text || '''::geometry, geom) asc limit 1'
>>> into rr;
>>>
>>> if rr.geom is not null then -- deal with MULTILINESTRINGS geom :=
>>> rr.geom; if geometrytype(geom)='MULTILINESTRING' THEN geom :=
>>> ST_GeometryN(geom, 1); end if;
>>>
>>> -- project the point onto the linestring pos :=
>>> st_line_locate_point(geom, pnt); edge_id := rr.gid; end if;
>>>
>>> end; $body$ language plpgsql stable;
>>>
>>>
>>> CREATE OR REPLACE FUNCTION public.pupil_journeys()
>>>>
>>>> RETURNS character varying AS
>>>>
>>>> $BODY$
>>>>
>>>> DECLARE
>>>>
>>>> cur_pupil refcursor;
>>>>
>>>> v_pid integer;
>>>>
>>>> v_pnn integer;
>>>>
>>>> v_snn integer;
>>>>
>>>> v_cost double precision;
>>>>
>>>> v_sql varchar(1000);
>>>>
>>>> BEGIN
>>>>
>>>> RAISE NOTICE 'Processing pupil journeys...';
>>>>
>>>> OPEN cur_pupil FOR EXECUTE format('SELECT pupilid, pupil_nn,
>>>> school_nn FROM edn_pupilschoolroute WHERE pupil_NN IS NOT NULL');
>>>>
>>>> LOOP
>>>>
>>>> FETCH cur_pupil INTO v_pid, v_pnn, v_snn;
>>>>
>>>> EXIT WHEN NOT FOUND;
>>>>
>>>> SELECT SUM(cost) AS v_cost FROM pgr_trsp('
>>>>
>>>> SELECT ogc_fid AS id,
>>>>
>>>> source::integer,
>>>>
>>>> target::integer,
>>>>
>>>> cost_len::double precision AS cost,
>>>>
>>>> rcost_len::double precision AS reverse_cost
>>>>
>>>> FROM hw_roadlink'::text,
>>>>
>>>> v_pnn, --pupil_nn gets inserted here
>>>>
>>>> v_snn, --school_nn gets inserted here
>>>>
>>>> true,
>>>>
>>>> true,
>>>>
>>>> 'select to_cost, teid as target_id, feid||coalesce('',''||via,'''')
>>>> as via_path from hw_nt_restrictions'::text) INTO v_cost;
>>>>
>>>> -- insert route cost into pupil data table
>>>>
>>>> v_sql:='UPDATE edn_pupilschoolroute SET p_dist = ' || v_cost || '
>>>> WHERE pupil_nn = ' || v_pnn || ' AND school_nn = ' || v_snn || '
>>>> AND pupilid = ' || v_pid;
>>>>
>>>> EXECUTE v_sql;
>>>>
>>>> END LOOP;
>>>>
>>>> RETURN ‘Well, that worked!';
>>>>
>>>> CLOSE cur_pupil;
>>>>
>>>> END;
>>>>
>>>> $BODY$
>>>>
>>>> LANGUAGE plpgsql VOLATILE
>>>>
>>>> COST 100;
>>>>
>>>> Thanks in advance
>>>>
>>>> Ross
>>>>
>>>> *Ross McDonald | *GIS Data Coordinator | Angus Council | Angus House,
>>>> Orchardbank Business Park, Sylvie Way, Forfar DD8 1AT*| t:
>>>> 01307 476419*
>>>>
>>>> This message is strictly confidential. If you have received this in
>>>> error, please inform the sender and remove it from your system.
>>>> If received in error you may not copy, print, forward or use it or
>>>> any attachment in any way. This message is not capable of creating a
>>>> legal contract or a binding representation and does not represent the
>>>> views of Angus Council. Emails may be monitored for security and
>>>> network management reasons.Messages containing inappropriate content
>>>> may be intercepted. Angus Council does not accept any liability for
>>>> any harm that may be caused to the recipient system or data on it by
>>>> this message or any attachment.
>>>>
>>>>
>>>>
>>>> _______________________________________________ Pgrouting-users
>>>> mailing list Pgrouting-users at lists.osgeo.org
>>>> https://lists.osgeo.org/mailman/listinfo/pgrouting-users
>>>>
>>>>
>>>
>>> --- This email has been checked for viruses by Avast antivirus
>>> software. https://www.avast.com/antivirus
>>>
>>> _______________________________________________ Pgrouting-users
>>> mailing list Pgrouting-users at lists.osgeo.org
>>> https://lists.osgeo.org/mailman/listinfo/pgrouting-users
>>>
>>> This message is strictly confidential. If you have received this in
>>> error, please inform the sender and remove it from your system. If
>>> received in error you may not copy, print, forward or use it or any
>>> attachment in any way. This message is not capable of creating a legal
>>> contract or a binding representation and does not represent the views
>>> of Angus Council. Emails may be monitored for security and network
>>> management reasons. Messages containing inappropriate content may be
>>> intercepted. Angus Council does not accept any liability for any harm
>>> that may be caused to the recipient system or data on it by this
>>> message or any attachment.
>>> _______________________________________________ Pgrouting-users
>>> mailing list Pgrouting-users at lists.osgeo.org
>>> https://lists.osgeo.org/mailman/listinfo/pgrouting-users
>>>
>>>
>>
>> ---
>> This email has been checked for viruses by Avast antivirus software.
>> https://www.avast.com/antivirus
>>
>> _______________________________________________
>> Pgrouting-users mailing list
>> Pgrouting-users at lists.osgeo.org
>> https://lists.osgeo.org/mailman/listinfo/pgrouting-users
>>
>> This message is strictly confidential. If you have received this in
>> error, please inform the sender and remove it from your system. If received
>> in error you may not copy, print, forward or use it or any attachment in
>> any way. This message is not capable of creating a legal contract or a
>> binding representation and does not represent the views of Angus Council.
>> Emails may be monitored for security and network management reasons.
>> Messages containing inappropriate content may be intercepted. Angus Council
>> does not accept any liability for any harm that may be caused to the
>> recipient system or data on it by this message or any attachment.
>> _______________________________________________
>> Pgrouting-users mailing list
>> Pgrouting-users at lists.osgeo.org
>> https://lists.osgeo.org/mailman/listinfo/pgrouting-users
>>
>>
>
> ---
> This email has been checked for viruses by Avast antivirus software.
> https://www.avast.com/antivirus
>
> _______________________________________________
> Pgrouting-users mailing list
> Pgrouting-users at lists.osgeo.org
> https://lists.osgeo.org/mailman/listinfo/pgrouting-users
>
--
Georepublic UG (haftungsbeschränkt)
Salzmannstraße 44,
81739 München, Germany
Vicky Vergara
Operations Research
eMail: vicky at georepublic.de
Web: https://georepublic.info
Tel: +49 (089) 4161 7698-1
Fax: +49 (089) 4161 7698-9
Commercial register: Amtsgericht München, HRB 181428
CEO: Daniel Kastl
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/pgrouting-users/attachments/20170425/75095824/attachment-0001.html>
More information about the Pgrouting-users
mailing list