[pgrouting-dev] APSP Implementation

[Stephen Woodbridge]

On 12/1/2010 11:36 PM, Daniel Kastl wrote:
>
>         I think there will be both cases. DARP/TSP might only need the
>         matrix at
>         first. But when you got your optimized tour result you had to
>         run again
>         the shortest path search to retrieve a path, which causes two
>         problems:
>
>             * The network (conditions) might have changed if you run
>         those path
>               queries later.
>
>
>     I guess this assumes the you are getting live feed data for traffic
>     or something like that. What are you think here? Also be aware that
>     the algorithms can select any of equal distance alternatives and the
>     later if you single shortest path it might pick a different path,
>     which may or may not be problematic.
>
>
> I actually don't assume live feed data but the fact that pgRouting keeps
> the network in a database and it's possible to change attributes for
> example, that are part of your cost parameter, at any time. Or maybe
> road links become unavailable during a long APSP query.
>
> I think the library should ensure that when you make a query it reads
> the network data available at that time. If the query for processing a
> huge distance matrix takes one hour for example, but makes steadily new
> requests to the database, it could happen that some attributes change
> over time.
> Whether this is problematic for an application or not depends on the
> application. In most cases it probably isn't, that's true. But pgRouting
> isn't limited to road networks, so who knows what kind of applications
> will make use of it.

OK, these are good points. I tend to over look these because I view the 
graph as relatively static for my purposes, but you are right to not 
assume that is the case. Thanks.

>             * It might be slower to later run single shortest path
>         queries again
>               independently
>
>
>     It would be interesting to enhance our single shortest path to be
>     able to extract multiple single shortest paths based on a single
>     graph build. So input might be something like
>
>
> This would be the same as k-Shortest Path, right?
> http://www.pgrouting.org/rfc/rfc-04.html
> <http://www.pgrouting.org/rfc/rfc-04.html>

No, K-shortest paths is more like what google does when it gives you 
alternative routes. You start and end stay constant but you get the 
shortest, then the next shortest, etc

I'm thinking of the case for example where you solve a TSP and now you 
want to extract the shortest paths from A-B, B-C, ... , Z-A and you only 
want to load and build the graph once but get back all the routes. You 
could probably think of it as via points. like start-A-B-C-D-end.
You could run 5 separate queries to get all the route segments, or we 
could have a function that you pass it a set of path control points and 
it build one graph and resturns all the segments in one call. I thought 
you were referencing doing this in an earlier email. Regardless this 
would be much faster than dosing N separate queries and having to build 
the graph N times.

-Steve

> Daniel
>
>
>
> --
> Georepublic UG & Georepublic Japan
> eMail: daniel.kastl at georepublic.de <mailto:daniel.kastl at georepublic.de>
> Web: http://georepublic.de <http://georepublic.de/>
>
>
>
> _______________________________________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev