[pgrouting-users] Shortest path with Dijkstra going through a set of points

Talin Salway talin at codeforamerica.org
Mon Sep 10 10:06:21 PDT 2012 

The other option might be to just increase the speed that individual
legs of the route calculate at. 0.3 seconds for a shortest_path query
seems a bit long.

How many points are in your network, total? How long does your sql
passed to shortest_path take to retrieve all the points?

On Sun, Sep 9, 2012 at 9:07 PM, Tao Romera Martinez <taoromera at gmail.com> wrote:
> Hi Steve,
>
> Thank you for the hints. I expect to be able to work on this in 3 or 4
> weeks, until then I am overbooked. I will let you know when I fork the
> code.
> Thaks again,
>
> Tao
>
> 2012/9/10 Stephen Woodbridge <woodbri at swoodbridge.com>:
>> Hi Tao,
>>
>>
>> On 9/9/2012 10:02 PM, Tao Romera Martinez wrote:
>>>
>>> Dear Daniel and Stephen,
>>>
>>> Thank you very much for your answers.
>>> I have not had time to dive into the pgrouting source code and the
>>> dijkstra algorithm, so I very much appreciate your detailed
>>> explanation about the possibilities to speed up the algorithm.
>>>
>>> I think that being able to dynamically generate the graph to be used
>>> in the routing algorithm is a great function, but having the
>>> possibility to work with a static graph would be fantastic if the
>>> speed improvement is in the order of 10x-100x, especially for
>>> web-related services, where the time response is crucial. I don't know
>>> how much time it would take to implement this feature, but I
>>> definitely put my vote for this one.
>>>
>>> In the meanwhile, I would like to help in the implementation of the
>>> via-TRSP (ie, the TRSP going through a set of points). Just one
>>> question: what is the speed up order we can expect? If the dijkstra
>>> algorithm itself is taking most of the time, I guess there is no point
>>> in spending time implementing it, but if generating the graph is
>>> consuming most of the processing time, the speed improvement could be
>>> big.
>>
>>
>> It is hard to estimate this, the best thing to do would be to take some
>> measurements. The time consists of the following:
>>
>> 1. time for SQL query and fetch the edges needed to build the graph
>> 2. time for SQL query and fetch associated turn restrictions if any
>> 3. time to build the graph
>> 4. time to solve the graph
>> 5. time to return the results
>>
>> My assumption is that 1-3 take significant % of the total time. but there
>> are a lot of variables, like how many edges are needed.
>>
>>
>>> Stephen, I have not written a line of C for ages, but I can get to it
>>> again if you allow some time for warming up. Also, I have an
>>> intermediate level of SQL, and have been a heavy user of postgis and
>>> pgrouting since April this year. Tell me how I can help you and I will
>>> be more than eager to work on the via TRSP function!
>>
>>
>> So the way I would approach this is to:
>>
>> 1. figure out a new signature for calling this new method
>> 2. make changes or write new code to implement the new signatures
>>
>> The Current signatures for trsp are:
>>
>> CREATE OR REPLACE FUNCTION turn_restrict_shortest_path(
>>                 sql text,
>>                 source_vid integer,
>>         target_vid integer,
>>         directed boolean,
>>         has_reverse_cost boolean,
>>         turn_restrict_sql text)
>>         RETURNS SETOF path_result
>>         AS '$libdir/librouting_trsp', 'turn_restrict_shortest_path_vertex'
>>         LANGUAGE 'C' IMMUTABLE;
>>
>> CREATE OR REPLACE FUNCTION turn_restrict_shortest_path(
>>                 sql text,
>>                 source_eid integer,
>>         source_pos float8,
>>         target_eid integer,
>>         target_pos float8,
>>         directed boolean,
>>         has_reverse_cost boolean,
>>         turn_restrict_sql text)
>>         RETURNS SETOF path_result
>>         AS '$libdir/librouting_trsp', 'turn_restrict_shortest_path_edge'
>>         LANGUAGE 'C' IMMUTABLE;
>>
>> So I think I might try changing this to be something like:
>>
>> CREATE OR REPLACE FUNCTION turn_restrict_shortest_path(
>>         sql text,             -- sql for the edges
>>         point_eid integer[],  -- array of edge ids[start,via,...,end]
>>         point_pos float8[],   -- array of position on edges
>> [start,via,...,end]
>>         directed boolean,
>>         has_reverse_cost boolean,
>>         turn_restrict_sql text)
>>         RETURNS SETOF path_result
>>         AS '$libdir/librouting_trsp', 'turn_restrict_shortest_path_vias'
>>         LANGUAGE 'C' IMMUTABLE;
>>
>> This would call the C function turn_restrict_shortest_path_vias() and
>> function similar in concept to turn_restrict_shortest_path_edge() but would
>> compute multiple solutions on the assembled graph.
>>
>> If you want to work on this, create a github account and fork pgrouting in
>> your account and let me know where it is so I can clone it and see what you
>> are doing. Then we can work together on it. I have not had time to look
>> closely at the code, so things might change if we run into problems.
>>
>> To get started you might want to clone pgrouting and add some code into trsp
>> to raise notices with timing information to get a better idea of what each
>> piece is costing.
>>
>> Thanks,
>>   -Steve
>>
>>
>>>
>>> Tao
>>>
>>> 2012/9/9 Stephen Woodbridge <woodbri at swoodbridge.com>:
>>>>
>>>> On 9/9/2012 5:59 AM, Daniel Kastl wrote:
>>>>>
>>>>>
>>>>>
>>>>>
>>>>> On Sun, Sep 9, 2012 at 1:24 PM, Tao Romera Martinez <taoromera at gmail.com
>>>>> <mailto:taoromera at gmail.com>> wrote:
>>>>>
>>>>>      Dear all,
>>>>>
>>>>>      I am using shortest_path() to find the shortest route between 2
>>>>>      points. I have a set of points (P1, P2, P3, P4...) through which I
>>>>>      want to go in order to reach the start and end points (S and E).
>>>>> Right
>>>>>      now, I am calling shortest_path() to link each pair of points
>>>>>      separately (S-P1, P1-P2, P2-P3, ...). The function shortest_path()
>>>>>      computes in 0.3 seconds, but since I have to call it many times,
>>>>> the
>>>>>      total time required to generate the final route gets quite high.
>>>>>
>>>>>      Does someone know how I could speed up the generation of the final
>>>>>      route (ie., the route going through all the points)? Is there a way
>>>>> of
>>>>>      calling shortest_path but with "via" points?
>>>>>
>>>>>
>>>>> Unfortunately there is not such a function, as far as I know.
>>>>
>>>>
>>>>
>>>> This is correct, no function like that today.
>>>>
>>>> The optimization might be that you could build the graph once, then solve
>>>> it
>>>> repeatedly for each consecutive pair of nodes. My guess is that this only
>>>> works well if the points are clustered in a small area as opposed to laid
>>>> out in a long linear path. The trade-off here is that creating N small
>>>> graphs and solving them each once versus creating one larger graph and
>>>> solving it N time.
>>>>
>>>> I believe it would be pretty easy to build this in just the plpsql and C
>>>> wrappers. Something along these lines:
>>>>
>>>> 1. get the extents of the points and expand it
>>>> 2. convert the points to edges or nodes
>>>> 3. build the graph from the edges in the expanded extents
>>>> 4. for each pair, solve the graph and return the edges
>>>> 5. cleanup and return
>>>>
>>>> If anyone has time or funding for this, I would be interested in doing
>>>> this
>>>> for the TRSP algorithm. This has the best ability to match points in
>>>> partial
>>>> edges and has support for turn restrictions.
>>>>
>>>> Another way of solving this problem is to provide support for a faster
>>>> solver, like highway contraction hierarchy that is on our wish list. This
>>>> solves problems 10-100x faster but does not fit well into the pgRouting
>>>> structure of dynamically building graphs.
>>>>
>>>> -Steve W
>>>>
>>>> _______________________________________________
>>>> Pgrouting-users mailing list
>>>> Pgrouting-users at lists.osgeo.org
>>>> http://lists.osgeo.org/mailman/listinfo/pgrouting-users
>>>
>>> _______________________________________________
>>> Pgrouting-users mailing list
>>> Pgrouting-users at lists.osgeo.org
>>> http://lists.osgeo.org/mailman/listinfo/pgrouting-users
>>>
>>
>> _______________________________________________
>> Pgrouting-users mailing list
>> Pgrouting-users at lists.osgeo.org
>> http://lists.osgeo.org/mailman/listinfo/pgrouting-users
> _______________________________________________
> Pgrouting-users mailing list
> Pgrouting-users at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-users

More information about the Pgrouting-users mailing list