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

[Stephen Woodbridge]

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