[pgrouting-users] pgr_apspjohnson algorithm

[Helder Alves]

Hi Steve,

I think I get it!
As soon I settle the reasoning in my head I'll contribute for the
project... :-)

--
Helder Alves


On Sun, Jan 5, 2014 at 1:18 PM, Stephen Woodbridge
<woodbri at swoodbridge.com>wrote:

> 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
>>
>>
> _______________________________________________
> Pgrouting-users mailing list
> Pgrouting-users at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-users
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/pgrouting-users/attachments/20140105/ada4531b/attachment-0001.html>