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@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@uninova.pt mailto:%[3Crddc@uninova.pt](mailto:3Crddc@uninova.pt)>____
cid:image002.jpg@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@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
–
Paulo Figueiras <paf@uninova.pt>
![cid:image002.jpg@01C8AEC7.2F6E45A0]()
|
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/