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

[Tao Romera Martinez]

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