[pgrouting-users] Optimize routing - use new sew-devel-2_0 functions

[Stephen Woodbridge]

Basically the wrappers all did variations of the following pattern:

1. take the XY of the start and end point of the route
2. find the nearest edge or vertex to those points
3. compute a BBOX like the following
    japan.geom_way && ST_EXPAND(
       ST_SetSRID(
         ST_MakeLine(
              ST_MakePoint(start_x, start_y),
              ST_MakePoint(end_x, end_y)
         ),
         4326), -- set the SRID
       0.05)    -- expand by this in SRID
4. run one of the shortest path queries.

Regarding which query to run:

Regardless of restrictions, the pgr_trsp() is a good function to use, 
because you and pass it and edge and a percent along the edge for bot 
the start and end points.

Then try algorithms in this order if performance is you goal:

pgr_bdastar - currently has a bug that we hope to fix before release
pgr_astar
pgr_bddijkstra - currently has bug
pgr_dijkstra

Hope this helps,
   -Steve

On 5/22/2013 6:55 AM, Tao Romera Martinez wrote:
> Oh, then use a bounding box. It will improve the speed of the query a lot.
> Something like this:
>
> SELECT * FROM shortest_path('
>                  SELECT gid as id,
>                           source::integer,
>                           target::integer,
>                           length::double precision as cost
>                          FROM japan WHERE japan.geom_way &&
> ST_MakeEnvelope(139.675, 35.729, 139.705, 35.762);',
>                  5700, 6733, false, false);
>
> Don't forget to create an index in the geom column:
>
> CREATE INDEX my_idx ON japan USING GIST(geom);
>
> Tao
>
> 2013/5/22 Tao Romera Martinez <taoromera at gmail.com>:
>> Frederic,
>>
>> The time to generate a route is mostly spent in retrieving the ways
>> from the DB and passing them to the C function that performs the
>> Dikstra, as Stephen once pointed out in a private mail to me. With a
>> small graph, 80% of the time consumed by shortest_path goes to
>> retrieving the ways.
>> If you really need to improve the efficiency of 1 search in your
>> service, you could consider modifying the C code to reuse the ways
>> retrieved from the DB and generate a new route with different
>> parameters.
>>
>> Tao
>>
>> 2013/5/22 Daniel Kastl <daniel at georepublic.de>:
>>>
>>>
>>>
>>> On Wed, May 22, 2013 at 6:42 PM, Frédéric Bonifas
>>> <fredericbonifas at gmail.com> wrote:
>>>>
>>>> I agree the the routes will be relatively short for pedestrian routing,
>>>> but :
>>>> * if I understand correctly how Dijkstra works, the routing time will
>>>> mostly depend on the size of the graph, as the whole graph will be
>>>> visited before giving the shortest_route.
>>>> * the fastest it is, the more I like it :)
>>>> * I show to the user different possible routes (4) so the routing time
>>>> is multiplied by this factor.
>>>>
>>>
>>> Hi Frederic,
>>>
>>> The algorithm doesn't make such  big difference as you might expect.
>>> What matters is the size of the network that you load for a routing request,
>>> which depends on the length of the route and the road density.
>>> For example a 40km route through Tokyo will load a huge amount of data, but
>>> some sparse area in Canada 40km would not be an issue.
>>>
>>> For your pedestrian routing, did you make sure that you don't load the whole
>>> network table for every request?
>>> The easiest way to limit the data you select is using a BBOX.
>>>
>>>   Daniel
>>>
>>>
>>>
>>> --
>>> Georepublic UG & Georepublic Japan
>>> eMail: daniel.kastl at georepublic.de
>>> Web: http://georepublic.de
>>>
>>> _______________________________________________
>>> Pgrouting-users mailing list
>>> Pgrouting-users at lists.osgeo.org
>>> http://lists.osgeo.org/mailman/listinfo/pgrouting-users
>>>
>>
>>
>>
>> --
>> Tao Romera Martínez
>>
>> ---------------------------------------------------------
>> Tel: 080-6805-0945
>> Address: Koganei-shi, Tokyo, Japan
>>
>> Look for me on Facebook and LinkedIn
>> ---------------------------------------------------------
>
>
>