[pgrouting-users] pgr_apspjohnson algorithm

[Stephen Woodbridge]

On 1/4/2014 11:28 PM, Helder Alves wrote:
> Hi Steve,
>
> I'm following those experiments you are working on... :-)
>
> Regarding APSP I think currently it's not clear on what circumstances
> these functions can be used. I found some explicit reference on
> develop-vrp or gsoc-vrp branch and after that I realized no one seems to
> be using those algorithms, apart from the fact that Johnson's
> implementation seems to not handle at all negative costs which I think
> that may defeat it theoretical purpose (but this is not the reason of
> this e-mail as I'm still studying that subject).

The two APSP algorithms were random additions from two of our GSoC 
students. I'm not sure what they are useful for, I'll need to go back to 
my graph theory and look that up again. I think that they have value 
where you construct a specific graph of important nodes and edges around 
a specific problem set and then you can solve that specific class of 
problems. I do not think it is useful to load a huge street network and 
solve it with APSP.

Graph theory supports an abstract model for solving a lot more problems 
than vehicle routing. While MOST of our user base is focused on vehicle 
routing not everyone is so some of the tools we offer are more to 
support general graph solutions than just vehicle routing solutions.

> Maybe this help to understand my doubts...

Understood. We are always looking and hoping to get support from the 
community. My skills are more generally focused on C development and 
process management rather than on the specifics of implementing any 
given graph solution. So pull requests are welcome. These could be for 
code, tests, and/or docs. I also enjoy a good discussion (like this) 
with our users. It is hard to know what is important to add to the 
product with such a discussion around limits and short comings and 
concerns that users have.

Best regards,
   -Steve

> Thanks!
>
> ----
> Helder Alves
>
> On Jan 5, 2014 2:54 AM, "Stephen Woodbridge" <woodbri at swoodbridge.com
> <mailto:woodbri at swoodbridge.com>> wrote:
>
>     On 1/4/2014 8:58 PM, Helder Alves wrote:
>
>         Hi List,
>
>         I've search the Internet for an example of a practical appliance of
>         pgr_apspjohnson function using OSM data.
>
>         If this algorithm is supposed to feed VRP using a VRP distance
>         table,
>         from the found documentation I suppose it must generate the
>         equivalent
>         to TSP distance matrix but in a record format pair by pair of
>         all the
>         vertices instead of the multi-dimensional array used by pgr_TSP,
>         please
>         correct me if I'm wrong.
>
>         Problem is, what data is supposed to feed pgr_apspjohnson?
>         source/target/cost ways (table) data for the vids I want to
>         order using
>         pgr_pointtovids function, for example? If not, I would like
>         someone to
>         elaborate a bit on this...
>
>         What about pgr_apspwarshall? Is it the same or not?
>
>         Thanks in advance for your help!
>
>
>     Helder,
>
>     I'm not sure that either of these are very useful as they in theory
>     generate ALL pairs for all nodes in the graph and VRP and TSP want a
>     matrix of some defined locations in the graph and not ALL locations
>     in the graph.
>
>     I had the same problem and my solution to this was to create
>
>     https://github.com/woodbri/__osrm-tools
>     <https://github.com/woodbri/osrm-tools>
>
>     which provides some postgresql wrapper functions that call to a
>     local instance of OSRM and creates the distances or tables needed to
>     feed into VRP or TSP. This is much faster than pgrouting path
>     generation, but does not allow for all the flexibility of pgRouting.
>     Also you have the added headache of setting up ORSM.
>
>     The other option that I created was to create a function
>     pgr_vidsToDMatrix()
>
>     This creates and array vetrex ids into a distance matrix.
>
>     https://github.com/pgRouting/__pgrouting/tree/develop/src/__common/doc/convenience
>     <https://github.com/pgRouting/pgrouting/tree/develop/src/common/doc/convenience>
>
>     -Steve
>     _________________________________________________
>     Pgrouting-users mailing list
>     Pgrouting-users at lists.osgeo.__org
>     <mailto:Pgrouting-users at lists.osgeo.org>
>     http://lists.osgeo.org/__mailman/listinfo/pgrouting-__users
>     <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
>