[pgrouting-users] Shortest path with Dijkstra going through a set of points
Tao Romera Martinez
taoromera at gmail.com
Tue Sep 11 04:29:24 PDT 2012
Dear Talin, Stephen,
Here some timing info:
Time taken by shortest_path: 350 ms
Time taken by the SQL query passed to shortest_path: 25 ms
Number of ways in the network: 4400
The network is very small, because I cut it off with an envelope in
the SQL passed to shortest_path.
I have indeces for geom_way, the primary id, source, target, x1, y1, x2, y2.
It's the first time I use pgrouting, so I have no prior experience to
compare with. Do you think 300 ms is too much for such a small
network?
Tao
2012/9/11 Stephen Woodbridge <woodbri at swoodbridge.com>:
> 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
>>
>
> _______________________________________________
> 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