[pgrouting-users] pgr_apspjohnson algorithm

Sun Jan 5 21:55:31 PST 2014

Hi Helder,

Thank you for testing and telling us about the problems.
I have not  tested the VRP function much, but what I tried has worked so
far.
What has several bugs is the demo application I made.

A few weeks ago I wrote a blog post, which hopefully explains a few points
of the VRP function:
http://blog.georepublic.info/2013/pgrouting-preview-the-new-vrp-solver/
And the blog article also contains a link to the demo and a short
presentation. Same as Steve I use OSRM to compute the distance matrix. But
I just use the HTTP API and pass the result as a huge SQL statement to
PostgreSQL without writing anything to the database. And I think that the
NodeJS psql module has some limitation with very long SQL statements, and
therefor it will fail for too many stop points.
But so far I have not found any other problems and the routes looked
usually OK.

If you are able to create (reproducible) bug reports in the Github issue
tracker, that would be helpful.

Daniel

PS: be careful with the demo. It's just an experiment and multiple users
accessing at the same time will experience a single-user (wrong) Websocket
implementation ;-)

On Mon, Jan 6, 2014 at 2:11 PM, Helder Alves <helderalvespt at gmail.com>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;
>    - 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
>>>
>>
>>
>
> _______________________________________________
> Pgrouting-users mailing list
> Pgrouting-users at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-users
>

-- 
Georepublic UG & Georepublic Japan
eMail: daniel.kastl at georepublic.de
Web: http://georepublic.de
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/pgrouting-users/attachments/20140106/24885fdf/attachment-0001.html>