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

[Stephen Woodbridge]

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
>