[pgrouting-users] pgr_apspjohnson algorithm

[Helder Alves]

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

Maybe this help to understand my doubts...

Thanks!

----
Helder Alves
On Jan 5, 2014 2:54 AM, "Stephen Woodbridge" <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
>
> 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
>
> -Steve
> _______________________________________________
> 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/cc17ee31/attachment.html>