[pgrouting-users] pgr_apspjohnson algorithm

[Stephen Woodbridge]

Helder,

On 1/6/2014 12:11 AM, Helder Alves wrote:
> Hi,
>
> I was able to make pgr_apspjohnson work but came to the conclusion that
> when we have available a valid distance matrix suitable for TSP/VRP it
> makes no sense to feed anything else to pgr_tsp or pgr_vpronedepot as
> the results will be suboptimal.
>
> Regarding pgr_vrponedepot I was able to also make it work however I
> guess I stumbled on several issues:
>
>   * Depot open/close time seems to not be obeyed;
>   * Traveltime also seems to not being considered between departure and
>     arrival time every time;

One thing that may not be obvious is that times in pgr_vrponedepot are 
all zero based on the depot open time. So depot open time should always 
be zero and then are other time should be time units in the future from 
the open time.

>   * After each query I have to restart PostgreSQL as last query result
>     seems to be stuck "somewhere" (memory?) and all subsequent queries
>     return the very same result;

you might need to change the pgr_vrponedepot sql wrapper to volatile if 
it is not.

pgrouting/src/vrp_basic/sql/routing_vrp.sql

should say:

LANGUAGE c VOLATILE STRICT;


>   * When I have to cancel some running query, cancelling procedure takes
>     forever and the only way I found to stop it is by killing postgresql
>     process.

Once it get into the C/C++ code we do not get the cancel request. I'll 
have to do some research and see if there is a function call we can 
check for a pending CancelRequest.

-Steve

> As some of these issues are too serious, I'm not sure if my merging &
> build may have some problem...
> If someone want to get a look, I've merged several Steve's develop tree
> with Daniel's develop-vrp, and also merged by hand some other small
> fixes and contributions I found interesting like Dave Potts and others,
> that I'm testing as I have free time. You can find everything here:
> https://github.com/ZupoLlask/pgrouting/tree/develop.
>
> --
> Helder Alves
>
>
> On Sun, Jan 5, 2014 at 8:28 PM, Helder Alves <helderalvespt at gmail.com
> <mailto:helderalvespt at gmail.com>> wrote:
>
>     Hi Steve,
>
>     I'm already beyond that stage but thanks anyway! ;-)
>
>     Steve/Daniel,
>
>     Regarding my assumptions regarding pgr_apspjohnson, they seem to be
>     wrong. Can you please elaborate a little bit on exactly which data
>     must be fed into pgr_apspjohnson?
>
>      From the pgRouting examples I read, it seems to return the
>     equivalent to the distance matrix used by pgr_TSP however I don't
>     understand exactly which part of a routable table must be queried in
>     a viable way for an algorithm to be able to infer which nodes have
>     to be routed. Can you help me with this one?
>
>     Thanks!
>
>     --
>     Helder Alves
>
>
>     On Sun, Jan 5, 2014 at 7:52 PM, Stephen Woodbridge
>     <woodbri at swoodbridge.com <mailto:woodbri at swoodbridge.com>> wrote:
>
>         On 1/5/2014 2:16 PM, Helder Alves wrote:
>
>             Hi Daniel,
>
>             Regarding pgr_apspjohnson, I came to the conclusion that SQL
>             query
>             passed into pgr_apspjohnson must already return a shortest
>             path distance
>             matrix including all the stop points we want to optimize. Am
>             I getting
>             it right?
>
>             What I'm about to try now is to unnest the distance matrix
>             generated for
>             pgr_TSP to feed pgr_apspjohnson...
>
>
>         You might be able to use something like this to convert the
>         distance matrix into a table:
>
>         with dm as (
>            select '{{1,2,3,4,5},
>                     {6,7,8,9,10},
>                     {11,12,13,14,15},
>                     {16,17,18,19,20},
>                     {21,22,23,24,25}}'::int[] as dm
>         )
>         select i, j, dm.dm <http://dm.dm>[j][i]
>            from generate_series(1, 5) i,
>                 generate_series(1, 5) j,
>                 dm;
>
>         -Steve
>
>             Problem was that from all my previous reading I thought that
>             at some
>             point APSP Johnson would itself generate the routing graphs,
>             what seems
>             not to be the case, if my understanding from the source code
>             is right...
>             Meaning APSP Johnson only takes care of the total route
>             minimum cost
>             (permutations) avoiding the problem of TSP with negative costs.
>
>             Please let me know if I made foolish assumptions! :-)
>
>             --
>             Helder Alves
>
>
>
>
>
>             _________________________________________________
>             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
>         <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
>