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

Stephen Woodbridge woodbri at swoodbridge.com
Mon Sep 10 12:23:57 PDT 2012 

On 9/10/2012 1:06 PM, Talin Salway wrote:
> 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?
>

Yes this would be excellent. Patches or pull requests welcome.

Also did you read my break down of the costs below? My guess is 
dijkstra's algorithm is the smallest component of the solution. I think 
you need to do some real testing using real networks to get a good 
handle on where the costs are actually coming from. Making Dijkstra's 
algorithm 50% faster does not help if it is only 5% of the total cost. 
At this point we do not have any real good analysis of the cost breakdown.

It might make sense to review the postgresql performance tuning as this 
might speed up the costs in items 1-2. This could allow for better 
caching of pages that might decrease the amount of time required to 
fetch the records needed for each via pair.

-Steve

> 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
> _______________________________________________
> 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