[pgrouting-users] Shortest path with Dijkstra going through a set of points

Tao_Romera_Martinez · September 9, 2012, 4:24am

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?

Thanks in advance for your help,

Tao

dkastl · September 9, 2012, 9:59am

On Sun, Sep 9, 2012 at 1:24 PM, Tao Romera Martinez <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.

Daniel

–
Georepublic UG & Georepublic Japan
eMail: daniel.kastl@georepublic.de
Web: http://georepublic.de

Stephen_Woodbridge1 · September 9, 2012, 1:33pm

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

Tao_Romera_Martinez · September 10, 2012, 2:02am

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.
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!

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

Stephen_Woodbridge1 · September 10, 2012, 3:38am

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

Tao_Romera_Martinez · September 10, 2012, 4:07am

Hi Steve,

Thank you for the hints. I expect to be able to work on this in 3 or 4
weeks, until then I am overbooked. I will let you know when I fork the
code.
Thaks again,

Tao

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

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

_______________________________________________
Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

Talin_Salway · September 10, 2012, 5:06pm

The other option might be to just increase the speed that individual
legs of the route calculate at. 0.3 seconds for a shortest_path query
seems a bit long.

How many points are in your network, total? How long does your sql
passed to shortest_path take to retrieve all the points?

On Sun, Sep 9, 2012 at 9:07 PM, Tao Romera Martinez <taoromera@gmail.com> wrote:

Hi Steve,

Thank you for the hints. I expect to be able to work on this in 3 or 4
weeks, until then I am overbooked. I will let you know when I fork the
code.
Thaks again,

Tao

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

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

_______________________________________________
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

Stephen_Woodbridge1 · September 10, 2012, 7:23pm

On 9/10/2012 1:06 PM, Talin Salway wrote:

The other option might be to just increase the speed that individual
legs of the route calculate at. 0.3 seconds for a shortest_path query
seems a bit long.

How many points are in your network, total? How long does your sql
passed to shortest_path take to retrieve all the points?

Yes this would be excellent. Patches or pull requests welcome.

Also did you read my break down of the costs below? My guess is dijkstra's algorithm is the smallest component of the solution. I think you need to do some real testing using real networks to get a good handle on where the costs are actually coming from. Making Dijkstra's algorithm 50% faster does not help if it is only 5% of the total cost. At this point we do not have any real good analysis of the cost breakdown.

It might make sense to review the postgresql performance tuning as this might speed up the costs in items 1-2. This could allow for better caching of pages that might decrease the amount of time required to fetch the records needed for each via pair.

-Steve

On Sun, Sep 9, 2012 at 9:07 PM, Tao Romera Martinez <taoromera@gmail.com> wrote:

Hi Steve,

Thank you for the hints. I expect to be able to work on this in 3 or 4
weeks, until then I am overbooked. I will let you know when I fork the
code.
Thaks again,

Tao

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

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

_______________________________________________
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

_______________________________________________
Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

Tao_Romera_Martinez · September 11, 2012, 11:29am

Dear Talin, Stephen,

Here some timing info:

Time taken by shortest_path: 350 ms
Time taken by the SQL query passed to shortest_path: 25 ms
Number of ways in the network: 4400

The network is very small, because I cut it off with an envelope in
the SQL passed to shortest_path.
I have indeces for geom_way, the primary id, source, target, x1, y1, x2, y2.

It's the first time I use pgrouting, so I have no prior experience to
compare with. Do you think 300 ms is too much for such a small
network?

Tao

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

On 9/10/2012 1:06 PM, Talin Salway wrote:

The other option might be to just increase the speed that individual
legs of the route calculate at. 0.3 seconds for a shortest_path query
seems a bit long.

How many points are in your network, total? How long does your sql
passed to shortest_path take to retrieve all the points?

Yes this would be excellent. Patches or pull requests welcome.

Also did you read my break down of the costs below? My guess is dijkstra's
algorithm is the smallest component of the solution. I think you need to do
some real testing using real networks to get a good handle on where the
costs are actually coming from. Making Dijkstra's algorithm 50% faster does
not help if it is only 5% of the total cost. At this point we do not have
any real good analysis of the cost breakdown.

It might make sense to review the postgresql performance tuning as this
might speed up the costs in items 1-2. This could allow for better caching
of pages that might decrease the amount of time required to fetch the
records needed for each via pair.

-Steve

On Sun, Sep 9, 2012 at 9:07 PM, Tao Romera Martinez <taoromera@gmail.com>
wrote:

Hi Steve,

Thank you for the hints. I expect to be able to work on this in 3 or 4
weeks, until then I am overbooked. I will let you know when I fork the
code.
Thaks again,

Tao

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

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

_______________________________________________
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

_______________________________________________
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

dkastl · September 11, 2012, 11:53am

Time taken by shortest_path: 350 ms
Time taken by the SQL query passed to shortest_path: 25 ms
Number of ways in the network: 4400

Is this your complete network or the size of the selected road links that you use for your shortest path query?

Daniel

–
Georepublic UG & Georepublic Japan
eMail: daniel.kastl@georepublic.de
Web: http://georepublic.de

Tao_Romera_Martinez · September 11, 2012, 12:33pm

It is the size of the selected road links that I use on the shortest path query.
The whole network has several millions.

On 2012/09/11, at 20:53, Daniel Kastl <daniel@georepublic.de> wrote:

Time taken by shortest_path: 350 ms
Time taken by the SQL query passed to shortest_path: 25 ms
Number of ways in the network: 4400

Is this your complete network or the size of the selected road links that you use for your shortest path query?

Daniel

–
Georepublic UG & Georepublic Japan
eMail: daniel.kastl@georepublic.de
Web: http://georepublic.de

Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

Stephen_Woodbridge1 · September 11, 2012, 2:23pm

Tao,

This seems like a long time, but I do not have any hard numbers to compare it to. Can you post the query you are running for this?

For comparison, it would be interesting to compare performance for:

Dijkstra shortest path
AStar shortest path
TRSP shortest path (pass NULL for the restriction query)

For pgRouting, indexes are only used on the SQL side of things, like a spatial index to select the edges in the network, and maybe an index on the gid if you join the results back to the original edge table. Once the edges are read into pgRouting C code to build the graph, the graph is all in memory and the solution is all performed in memory, then the results are passed back to the SQL.

-Steve

On 9/11/2012 8:33 AM, Tao Romera Martinez wrote:

It is the size of the selected road links that I use on the shortest
path query.
The whole network has several millions.

On 2012/09/11, at 20:53, Daniel Kastl <daniel@georepublic.de
<mailto:daniel@georepublic.de>> wrote:

    Time taken by shortest_path: 350 ms
    Time taken by the SQL query passed to shortest_path: 25 ms
    Number of ways in the network: 4400

Is this your complete network or the size of the selected road links
that you use for your shortest path query?

Daniel

--
Georepublic UG & Georepublic Japan
eMail: daniel.kastl@georepublic.de <mailto:daniel.kastl@georepublic.de>
Web: http://georepublic.de/>
_______________________________________________
Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org <mailto: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

Talin_Salway · September 11, 2012, 3:41pm

What does your memory and CPU usage look like during execution? Is it 350ms of pure CPU, or is there disk IO? Are you hitting memory limits and swapping?

I ask because there are some edge cases where pgRouting uses too much memory.If it hits disk, it’d slow down your query.

On Sep 11, 2012 7:26 AM, “Stephen Woodbridge” <woodbri@swoodbridge.com> wrote:

Tao,

This seems like a long time, but I do not have any hard numbers to compare it to. Can you post the query you are running for this?

For comparison, it would be interesting to compare performance for:

Dijkstra shortest path
AStar shortest path
TRSP shortest path (pass NULL for the restriction query)

For pgRouting, indexes are only used on the SQL side of things, like a spatial index to select the edges in the network, and maybe an index on the gid if you join the results back to the original edge table. Once the edges are read into pgRouting C code to build the graph, the graph is all in memory and the solution is all performed in memory, then the results are passed back to the SQL.

-Steve

On 9/11/2012 8:33 AM, Tao Romera Martinez wrote:

It is the size of the selected road links that I use on the shortest
path query.
The whole network has several millions.

On 2012/09/11, at 20:53, Daniel Kastl <daniel@georepublic.de
mailto:[daniel@georepublic.de](mailto:daniel@georepublic.de)> wrote:

Time taken by shortest_path: 350 ms
Time taken by the SQL query passed to shortest_path: 25 ms
Number of ways in the network: 4400

Is this your complete network or the size of the selected road links
that you use for your shortest path query?

Daniel

–
Georepublic UG & Georepublic Japan
eMail: daniel.kastl@georepublic.de mailto:[daniel.kastl@georepublic.de](mailto:daniel.kastl@georepublic.de)
Web: http://georepublic.de <http://georepublic.de/>

Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org mailto:[Pgrouting-users@lists.osgeo.org](mailto: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

Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

Tao_Romera_Martinez · September 12, 2012, 12:22am

CPU usage: 11%
Mem usage: 1.1%
Disk I/O (%wa): 0.2% (the first time, then 0%)

The results with the directed graph turned on are similar.

2012/9/12 Talin Salway <talin@codeforamerica.org>:

What does your memory and CPU usage look like during execution? Is it 350ms
of pure CPU, or is there disk IO? Are you hitting memory limits and
swapping?

I ask because there are some edge cases where pgRouting uses too much
memory.If it hits disk, it'd slow down your query.

On Sep 11, 2012 7:26 AM, "Stephen Woodbridge" <woodbri@swoodbridge.com>
wrote:

Tao,

This seems like a long time, but I do not have any hard numbers to compare
it to. Can you post the query you are running for this?

For comparison, it would be interesting to compare performance for:

Dijkstra shortest path
AStar shortest path
TRSP shortest path (pass NULL for the restriction query)

For pgRouting, indexes are only used on the SQL side of things, like a
spatial index to select the edges in the network, and maybe an index on the
gid if you join the results back to the original edge table. Once the edges
are read into pgRouting C code to build the graph, the graph is all in
memory and the solution is all performed in memory, then the results are
passed back to the SQL.

-Steve

On 9/11/2012 8:33 AM, Tao Romera Martinez wrote:

It is the size of the selected road links that I use on the shortest
path query.
The whole network has several millions.

On 2012/09/11, at 20:53, Daniel Kastl <daniel@georepublic.de
<mailto:daniel@georepublic.de>> wrote:

    Time taken by shortest_path: 350 ms
    Time taken by the SQL query passed to shortest_path: 25 ms
    Number of ways in the network: 4400

Is this your complete network or the size of the selected road links
that you use for your shortest path query?

Daniel

--
Georepublic UG & Georepublic Japan
eMail: daniel.kastl@georepublic.de <mailto:daniel.kastl@georepublic.de>
Web: http://georepublic.de/>
_______________________________________________
Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org <mailto: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

_______________________________________________
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