Hi Tao,

On 9/9/2012 10:02 PM, Tao Romera Martinez wrote:

Dear Daniel and Stephen,

Thank you very much for your answers.

I have not had time to dive into the pgrouting source code and the

dijkstra algorithm, so I very much appreciate your detailed

explanation about the possibilities to speed up the algorithm.

I think that being able to dynamically generate the graph to be used

in the routing algorithm is a great function, but having the

possibility to work with a static graph would be fantastic if the

speed improvement is in the order of 10x-100x, especially for

web-related services, where the time response is crucial. I don't know

how much time it would take to implement this feature, but I

definitely put my vote for this one.

In the meanwhile, I would like to help in the implementation of the

via-TRSP (ie, the TRSP going through a set of points). Just one

question: what is the speed up order we can expect? If the dijkstra

algorithm itself is taking most of the time, I guess there is no point

in spending time implementing it, but if generating the graph is

consuming most of the processing time, the speed improvement could be

big.

It is hard to estimate this, the best thing to do would be to take some measurements. The time consists of the following:

1. time for SQL query and fetch the edges needed to build the graph

2. time for SQL query and fetch associated turn restrictions if any

3. time to build the graph

4. time to solve the graph

5. time to return the results

My assumption is that 1-3 take significant % of the total time. but there are a lot of variables, like how many edges are needed.

Stephen, I have not written a line of C for ages, but I can get to it

again if you allow some time for warming up. Also, I have an

intermediate level of SQL, and have been a heavy user of postgis and

pgrouting since April this year. Tell me how I can help you and I will

be more than eager to work on the via TRSP function!

So the way I would approach this is to:

1. figure out a new signature for calling this new method

2. make changes or write new code to implement the new signatures

The Current signatures for trsp are:

CREATE OR REPLACE FUNCTION turn_restrict_shortest_path(

sql text,

source_vid integer,

target_vid integer,

directed boolean,

has_reverse_cost boolean,

turn_restrict_sql text)

RETURNS SETOF path_result

AS '$libdir/librouting_trsp', 'turn_restrict_shortest_path_vertex'

LANGUAGE 'C' IMMUTABLE;

CREATE OR REPLACE FUNCTION turn_restrict_shortest_path(

sql text,

source_eid integer,

source_pos float8,

target_eid integer,

target_pos float8,

directed boolean,

has_reverse_cost boolean,

turn_restrict_sql text)

RETURNS SETOF path_result

AS '$libdir/librouting_trsp', 'turn_restrict_shortest_path_edge'

LANGUAGE 'C' IMMUTABLE;

So I think I might try changing this to be something like:

CREATE OR REPLACE FUNCTION turn_restrict_shortest_path(

sql text, -- sql for the edges

point_eid integer, -- array of edge ids[start,via,...,end]

point_pos float8, -- array of position on edges [start,via,...,end]

directed boolean,

has_reverse_cost boolean,

turn_restrict_sql text)

RETURNS SETOF path_result

AS '$libdir/librouting_trsp', 'turn_restrict_shortest_path_vias'

LANGUAGE 'C' IMMUTABLE;

This would call the C function turn_restrict_shortest_path_vias() and function similar in concept to turn_restrict_shortest_path_edge() but would compute multiple solutions on the assembled graph.

If you want to work on this, create a github account and fork pgrouting in your account and let me know where it is so I can clone it and see what you are doing. Then we can work together on it. I have not had time to look closely at the code, so things might change if we run into problems.

To get started you might want to clone pgrouting and add some code into trsp to raise notices with timing information to get a better idea of what each piece is costing.

Thanks,

-Steve

Tao

2012/9/9 Stephen Woodbridge <woodbri@swoodbridge.com>:

On 9/9/2012 5:59 AM, Daniel Kastl wrote:

On Sun, Sep 9, 2012 at 1:24 PM, Tao Romera Martinez <taoromera@gmail.com

<mailto:taoromera@gmail.com>> wrote:

Dear all,

I am using shortest_path() to find the shortest route between 2

points. I have a set of points (P1, P2, P3, P4...) through which I

want to go in order to reach the start and end points (S and E). Right

now, I am calling shortest_path() to link each pair of points

separately (S-P1, P1-P2, P2-P3, ...). The function shortest_path()

computes in 0.3 seconds, but since I have to call it many times, the

total time required to generate the final route gets quite high.

Does someone know how I could speed up the generation of the final

route (ie., the route going through all the points)? Is there a way of

calling shortest_path but with "via" points?

Unfortunately there is not such a function, as far as I know.

This is correct, no function like that today.

The optimization might be that you could build the graph once, then solve it

repeatedly for each consecutive pair of nodes. My guess is that this only

works well if the points are clustered in a small area as opposed to laid

out in a long linear path. The trade-off here is that creating N small

graphs and solving them each once versus creating one larger graph and

solving it N time.

I believe it would be pretty easy to build this in just the plpsql and C

wrappers. Something along these lines:

1. get the extents of the points and expand it

2. convert the points to edges or nodes

3. build the graph from the edges in the expanded extents

4. for each pair, solve the graph and return the edges

5. cleanup and return

If anyone has time or funding for this, I would be interested in doing this

for the TRSP algorithm. This has the best ability to match points in partial

edges and has support for turn restrictions.

Another way of solving this problem is to provide support for a faster

solver, like highway contraction hierarchy that is on our wish list. This

solves problems 10-100x faster but does not fit well into the pgRouting

structure of dynamically building graphs.

-Steve W

_______________________________________________

Pgrouting-users mailing list

Pgrouting-users@lists.osgeo.org

http://lists.osgeo.org/mailman/listinfo/pgrouting-users

_______________________________________________

Pgrouting-users mailing list

Pgrouting-users@lists.osgeo.org

http://lists.osgeo.org/mailman/listinfo/pgrouting-users