[pgrouting-users] pgr_apspjohnson algorithm

[Helder Alves]

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

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>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> 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[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
>>> 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/20140106/9c8a777e/attachment.html>