[pgrouting-dev] K-Shortest Paths performance issues

[Paulo Figueiras]

Hello, Stephen.

So the point of situation is as follows:

 - Tried k=2 in my development machine: 30 minutes to get query answer
 - Tried k=1 in my development machine: 30 minutes to get query answer
 - Tried also for k=1,2 in my server, and the time is the same, although
the server machine is much better in terms of performance than my
development machine.

So this is weird, because it does not depend on the number of routes you
want to calculate, or the performance of the machine... I suspect that the
algorithm may have some error.

The query I'm using is the following:

SELECT seq, id1 AS route, id2 AS node, id3 AS edge, cost FROM
public.pgr_ksp('SELECT gid AS id,source,target,length AS cost FROM ways
WHERE class_id NOT IN
(112,113,114,115,116,117,118,119,120,121,122,501,502)', 40881, 290690, 1,
false);

I know that the route is possible, because I'm calculating the same route
with the same restrictions with Dijkstra (less than 30 seconds to answer in
the server).

Because the algorithm is taking so long to respond, I'm having some trouble
on getting the actual result of the algorithm. As soon as I have it, I'll
send you the result.

Again, thank you very much.

Best,

P.


2014-01-23 Stephen Woodbridge <woodbri at swoodbridge.com>

> On 1/23/2014 5:34 PM, Paulo Figueiras wrote:
>
>> Hi, Steve.
>>
>> Thanks for your fast response.
>>
>>
>>     The seems a little excessive to me, but I have not used it enough to
>>     have any idea what to expect.
>>
>>
>> So it seems :) I'm running pgrouting on a Ubuntu virtual machine with 2
>> cores and 4GB of RAM.
>>
>>     Can you run ksp with k=1? or does it automatically adjust it upward
>>     to k=2?
>>
>> I can try to run with k=1, although I use Dijkstra or A* for single
>> routes. I would really like to use KSP for 2 to 5 route options.
>>
>
> Right, but this will indicate if the problem is with the basic algorithm
> implementation, ie: k=1 should be able the same as Dijkstra, or if the
> problem is extracting the additional routes.
>
> Another test would be time k=1, k=2, k=3, k=4, k=5 using the same input
> parameters, so we can see how the graphs out.
>
>
>      Does this happen for ALL cases? or only sometimes?
>>
>> I tried a few times and it is consistent.
>>
>>
>>     Can you make a small graph test case the shows this behavior? The
>>     can be used to debugging the problem.
>>
>> What I'll do is I'll migrate my code to a more powerful server this
>> weekend, and I'll test KSP with k=2 there to check for improvements. In
>> the meantime, I'll try k=1 in the virtual machine.
>>
>> I'll report results next week. Again, thank you very much.
>>
>
> Ok, cool. My experience with VMs is that they tend to have performance
> issues, but it not a large sample. Anyway, Look forward to any addition
> results you can generate.
>
> Thanks,
>   -Steve
>
>  Best,
>>
>> --
>>
>> Paulo Figueiras <paf at uninova.pt <mailto:%3Crddc at uninova.pt>>____
>>
>> cid:image002.jpg at 01C8AEC7.2F6E45A0 <http://www.uninova.pt/>____
>>
>> __ __
>>
>>
>>
>> UNINOVA, Centre of Technology and Systems
>> Campus da Caparica, Quinta da Torre
>> 2829-516 Monte Caparica, PORTUGAL____
>>
>>
>> Phone: (+351) 212948312 | Fax: (+351) 212957786 | Website:
>> http://www.uninova.pt/
>>
>>
>>
>> _______________________________________________
>> pgrouting-dev mailing list
>> pgrouting-dev at lists.osgeo.org
>> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>>
>>
> _______________________________________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>



-- 

Paulo Figueiras <paf at uninova.pt <%3Crddc at uninova.pt>>

[image: cid:image002.jpg at 01C8AEC7.2F6E45A0] <http://www.uninova.pt/>



UNINOVA, Centre of Technology and Systems
Campus da Caparica, Quinta da Torre
2829-516 Monte Caparica, PORTUGAL

Phone: (+351) 212948312 | Fax: (+351) 212957786 | Website:
http://www.uninova.pt/
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20140127/05a92727/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image001.jpg
Type: image/jpeg
Size: 2416 bytes
Desc: not available
URL: <http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20140127/05a92727/attachment.jpg>