[pgrouting-users] pgr_apspjohnson algorithm

[Stephen Woodbridge]

I opened this ticket up for the cancel request issue:
https://github.com/pgRouting/pgrouting/issues/232

On 1/6/2014 9:14 AM, Stephen Woodbridge wrote:
> 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
>>
>
> _______________________________________________
> Pgrouting-users mailing list
> Pgrouting-users at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-users