[pgrouting-dev] pgr_trsp with k

[Stephen Woodbridge]

On 3/10/2014 8:42 PM, Julien-Samuel Lacroix wrote:
> Hello,
>
> I'm currently working with pgr_trsp. Would it be possible to get K
> results like when we use pgr_kDijkstra?
>
> I could probably provide a pull request if someone provide me some
> pointers.
>
> Julien

Hi Julien,

I actually have trsp code from the developer sitting in a branch that I 
have not had time to integrate, document, and setup tests for. It does 
not solve the kDijkstra problem using TRSP (but read on). I discussed 
this with Roni and he was interested in developing it. Let me know if 
you have any interest in funding Roni to do it and I'll pass on contact 
info and make introductions.

The changes I have MIGHT be applicable to you problem. They implement 
via points so you can pass multiple location into TRSP and it will 
compute the route from 1-2-3-...-n. To do this you have to setup up the 
graph, and then reinitialize it it on the next leg of the journey. I 
think this could be adapted such that you have a start point and N 
destination and you build one graph and then solve it N times 
reinitialize the existing graph for each solution.

Most of the cost of a solution in pgRouting is reading the edges from 
the database, passing them to the code, building the graph. The graph 
solver is fast. So if you can build one big graph then solve it N times 
it is big win.

We would love to get a pull request for this. And if you have time to 
integrate Roni code I have not gotten to yet, that would be cool also 
and you would need it anyway.

-Steve