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

[Tao Romera Martinez]

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.
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!

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