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

[Frédéric Bonifas]

Thank you very much for all your answers. Using a bounding-box does
indeed improve the performances.
I will stick to Dijkstra for now.

Best

Frédéric

2013/5/22 Stephen Woodbridge <woodbri at swoodbridge.com>:
> 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
>>> ---------------------------------------------------------
>>
>>
>>
>>
>
> _______________________________________________
> Pgrouting-users mailing list
> Pgrouting-users at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-users



--
Frédéric Bonifas
+33672652807 skype:fredericbonifas