[pgrouting-users] pgr_apspjohnson algorithm

[Stephen Woodbridge]

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