[pgrouting-users] TRSP Problem

Christophe_Damour · March 3, 2014, 7:20pm

Hi,

Sorry to post twice, I forgot the attached file...

I use pgRouting to calculate accessible routes for disabled pedestrians.
Network edges have some attributes that are used to filter the accessible network in both ways depending on the user capacities (where clause).
Network edges have also attributes that are used to update cost / rev_cost depending on the routing way : If an edge is forbidden in the digitizing way, cost is set to 1 000 000. If it is forbidden in the reverse way, rev_cost is set to 1 000 000. If it is forbidden in both ways, cost and rev_cost are set to 1 000 000.

Now, in some cases, despite there is no accessible route according to the where clause, pgr_trsp() returns a route going through edges with cost / rev_cost set to 1 000 000.
If I change the where clause so that there is actually an alternative route, same edges with cost / rev_cost set to 1 000 000 are taken into account, and the calculated route is correct.

I attached to this message images of both results (forbidden edges in red, returned paths in blue).
Routing is calculated from edge n°18295 (vertex n°19314) to edge n°23805 (vertex n°10776).
Wrong edge is n°30606 in test 2.

Here is the sql code of the first test :
SELECT * FROM pgr_trsp(
'SELECT id_tron::integer AS id, source::integer, target::integer,
cost::double precision, rev_cost::double precision AS reverse_cost
FROM rp_test
WHERE type_tron NOT IN(3, 8, 9) AND largeur_c > 90 AND largeur_p > 75 AND etat_revet >= 2',
19314::INTEGER, 10776::INTEGER, true, true,
'SELECT to_cost::double precision, target_id::integer, via_path::text FROM reseau_global_rest');

And here is the sql code of the second test :
SELECT * FROM pgr_trsp(
'SELECT id_tron::integer AS id, source::integer, target::integer,
cost::double precision, rev_cost::double precision AS reverse_cost
FROM rp_test
WHERE type_tron NOT IN(3, 8, 9) AND largeur_c > 90 AND largeur_p > 75',
19314::INTEGER, 10776::INTEGER, true, true,
'SELECT to_cost::double precision, target_id::integer, via_path::text FROM reseau_global_rest');

I also attach to this message a shape file of the network.

Do I miss something, or is it a bug ?

Thanks for any help,

--
Christophe DAMOUR

bug_trsp.zip (88.2 KB)

Christophe_Damour · March 7, 2014, 6:41pm

Hi,

No answer... I am stuck with this one.

Is it possible that there is a conflict between the where clause processing and the cost / rev_cost ?

I have the same behaviour with edge start / target instead of vertex start / target.

Here is the wrong query result :
seq id1 id2 cost
0 19314 23805 25.2230680696244
1 16327 15869 200.551744693165
2 16328 30606 1000000
3 22180 30607 12.1375967381755
4 14374 28286 249.361944927019
5 14371 18295 111.604786405456
6 10776 -1 0

In my understanding, it shouldn't be possible to have an edge with cost 1000000 in the resulting path (it is the only one in the network to have such a cost, and the network is very small) !

Thanks for any hint,

--
Christophe DAMOUR

Le 03/03/2014 20:20, Christophe Damour a écrit :

Hi,

Sorry to post twice, I forgot the attached file...

I use pgRouting to calculate accessible routes for disabled pedestrians.
Network edges have some attributes that are used to filter the accessible network in both ways depending on the user capacities (where clause).
Network edges have also attributes that are used to update cost / rev_cost depending on the routing way : If an edge is forbidden in the digitizing way, cost is set to 1 000 000. If it is forbidden in the reverse way, rev_cost is set to 1 000 000. If it is forbidden in both ways, cost and rev_cost are set to 1 000 000.

Now, in some cases, despite there is no accessible route according to the where clause, pgr_trsp() returns a route going through edges with cost / rev_cost set to 1 000 000.
If I change the where clause so that there is actually an alternative route, same edges with cost / rev_cost set to 1 000 000 are taken into account, and the calculated route is correct.

I attached to this message images of both results (forbidden edges in red, returned paths in blue).
Routing is calculated from edge n°18295 (vertex n°19314) to edge n°23805 (vertex n°10776).
Wrong edge is n°30606 in test 2.

Here is the sql code of the first test :
SELECT * FROM pgr_trsp(
'SELECT id_tron::integer AS id, source::integer, target::integer,
cost::double precision, rev_cost::double precision AS reverse_cost
FROM rp_test
WHERE type_tron NOT IN(3, 8, 9) AND largeur_c > 90 AND largeur_p > 75 AND etat_revet >= 2',
19314::INTEGER, 10776::INTEGER, true, true,
'SELECT to_cost::double precision, target_id::integer, via_path::text FROM reseau_global_rest');

And here is the sql code of the second test :
SELECT * FROM pgr_trsp(
'SELECT id_tron::integer AS id, source::integer, target::integer,
cost::double precision, rev_cost::double precision AS reverse_cost
FROM rp_test
WHERE type_tron NOT IN(3, 8, 9) AND largeur_c > 90 AND largeur_p > 75',
19314::INTEGER, 10776::INTEGER, true, true,
'SELECT to_cost::double precision, target_id::integer, via_path::text FROM reseau_global_rest');

I also attach to this message a shape file of the network.

Do I miss something, or is it a bug ?

Thanks for any help,
--
Christophe DAMOUR

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

bug_trsp.zip (88.2 KB)

Stephen_Woodbridge1 · March 7, 2014, 7:10pm

Hi Christophe,

Sorry you are having problems with this. I have a major deadline and have not had time to look at this. Typically the large cost value means that you are requesting a route and the only way to follow the route is to go the wrong way down a one-way street.

This might be because you are missing some edges because your where clause to not including enough edges or there is some other issue with your graph like it is not noded correctly.

We have supplied some tools in the 2.0 release to help node a newwork and to help analyze it for problems. Read the docs
http://docs.pgrouting.org/2.0/en/doc/index.html
Specifically the Tutorials on "Routing Topology" and Graph Analytics"

When I have some free time, I will look at your issue, but please don't wait on me as it may be a while.

Best,
-Steve

On 3/7/2014 1:41 PM, Christophe Damour wrote:

Hi,

No answer... I am stuck with this one.

Is it possible that there is a conflict between the where clause
processing and the cost / rev_cost ?

I have the same behaviour with edge start / target instead of vertex
start / target.

Here is the wrong query result :
seq id1 id2 cost
0 19314 23805 25.2230680696244
1 16327 15869 200.551744693165
2 16328 30606 1000000
3 22180 30607 12.1375967381755
4 14374 28286 249.361944927019
5 14371 18295 111.604786405456
6 10776 -1 0

In my understanding, it shouldn't be possible to have an edge with cost
1000000 in the resulting path (it is the only one in the network to have
such a cost, and the network is very small) !

Thanks for any hint,

--
Christophe DAMOUR

Le 03/03/2014 20:20, Christophe Damour a écrit :

Hi,

Sorry to post twice, I forgot the attached file...

I use pgRouting to calculate accessible routes for disabled pedestrians.
Network edges have some attributes that are used to filter the
accessible network in both ways depending on the user capacities
(where clause).
Network edges have also attributes that are used to update cost /
rev_cost depending on the routing way : If an edge is forbidden in the
digitizing way, cost is set to 1 000 000. If it is forbidden in the
reverse way, rev_cost is set to 1 000 000. If it is forbidden in both
ways, cost and rev_cost are set to 1 000 000.

Now, in some cases, despite there is no accessible route according to
the where clause, pgr_trsp() returns a route going through edges with
cost / rev_cost set to 1 000 000.
If I change the where clause so that there is actually an alternative
route, same edges with cost / rev_cost set to 1 000 000 are taken into
account, and the calculated route is correct.

I attached to this message images of both results (forbidden edges in
red, returned paths in blue).
Routing is calculated from edge n°18295 (vertex n°19314) to edge
n°23805 (vertex n°10776).
Wrong edge is n°30606 in test 2.

Here is the sql code of the first test :
SELECT * FROM pgr_trsp(
'SELECT id_tron::integer AS id, source::integer, target::integer,
cost::double precision, rev_cost::double precision AS reverse_cost
FROM rp_test
WHERE type_tron NOT IN(3, 8, 9) AND largeur_c > 90 AND largeur_p > 75
AND etat_revet >= 2',
19314::INTEGER, 10776::INTEGER, true, true,
'SELECT to_cost::double precision, target_id::integer, via_path::text
FROM reseau_global_rest');

And here is the sql code of the second test :
SELECT * FROM pgr_trsp(
'SELECT id_tron::integer AS id, source::integer, target::integer,
cost::double precision, rev_cost::double precision AS reverse_cost
FROM rp_test
WHERE type_tron NOT IN(3, 8, 9) AND largeur_c > 90 AND largeur_p > 75',
19314::INTEGER, 10776::INTEGER, true, true,
'SELECT to_cost::double precision, target_id::integer, via_path::text
FROM reseau_global_rest');

I also attach to this message a shape file of the network.

Do I miss something, or is it a bug ?

Thanks for any help,
--
Christophe DAMOUR

_______________________________________________
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

Christophe_Damour · March 8, 2014, 7:06am

Hi Steven,

Thank you for answering.

I double checked the topology and it looks ok.

By the way, when you say "the only way to follow the route is to go the wrong way down a one-way street" :
Do you mean that this is the expected behaviour ?

I expected an error or an exception saying : "Path Not Found" in such a case.
Is there a workaround for that situation or should I handle it with a post-query process ?

Thank you again for your time.

--
Christophe DAMOUR

Le 07/03/2014 20:10, Stephen Woodbridge a écrit :

Hi Christophe,

Sorry you are having problems with this. I have a major deadline and have not had time to look at this. Typically the large cost value means that you are requesting a route and the only way to follow the route is to go the wrong way down a one-way street.

This might be because you are missing some edges because your where clause to not including enough edges or there is some other issue with your graph like it is not noded correctly.

We have supplied some tools in the 2.0 release to help node a newwork and to help analyze it for problems. Read the docs
http://docs.pgrouting.org/2.0/en/doc/index.html
Specifically the Tutorials on "Routing Topology" and Graph Analytics"

When I have some free time, I will look at your issue, but please don't wait on me as it may be a while.

Best,
-Steve

On 3/7/2014 1:41 PM, Christophe Damour wrote:

Hi,

No answer... I am stuck with this one.

Is it possible that there is a conflict between the where clause
processing and the cost / rev_cost ?

I have the same behaviour with edge start / target instead of vertex
start / target.

Here is the wrong query result :
seq id1 id2 cost
0 19314 23805 25.2230680696244
1 16327 15869 200.551744693165
2 16328 30606 1000000
3 22180 30607 12.1375967381755
4 14374 28286 249.361944927019
5 14371 18295 111.604786405456
6 10776 -1 0

In my understanding, it shouldn't be possible to have an edge with cost
1000000 in the resulting path (it is the only one in the network to have
such a cost, and the network is very small) !

Thanks for any hint,

--
Christophe DAMOUR

Le 03/03/2014 20:20, Christophe Damour a écrit :

Hi,

Sorry to post twice, I forgot the attached file...

I use pgRouting to calculate accessible routes for disabled pedestrians.
Network edges have some attributes that are used to filter the
accessible network in both ways depending on the user capacities
(where clause).
Network edges have also attributes that are used to update cost /
rev_cost depending on the routing way : If an edge is forbidden in the
digitizing way, cost is set to 1 000 000. If it is forbidden in the
reverse way, rev_cost is set to 1 000 000. If it is forbidden in both
ways, cost and rev_cost are set to 1 000 000.

Now, in some cases, despite there is no accessible route according to
the where clause, pgr_trsp() returns a route going through edges with
cost / rev_cost set to 1 000 000.
If I change the where clause so that there is actually an alternative
route, same edges with cost / rev_cost set to 1 000 000 are taken into
account, and the calculated route is correct.

I attached to this message images of both results (forbidden edges in
red, returned paths in blue).
Routing is calculated from edge n°18295 (vertex n°19314) to edge
n°23805 (vertex n°10776).
Wrong edge is n°30606 in test 2.

Here is the sql code of the first test :
SELECT * FROM pgr_trsp(
'SELECT id_tron::integer AS id, source::integer, target::integer,
cost::double precision, rev_cost::double precision AS reverse_cost
FROM rp_test
WHERE type_tron NOT IN(3, 8, 9) AND largeur_c > 90 AND largeur_p > 75
AND etat_revet >= 2',
19314::INTEGER, 10776::INTEGER, true, true,
'SELECT to_cost::double precision, target_id::integer, via_path::text
FROM reseau_global_rest');

And here is the sql code of the second test :
SELECT * FROM pgr_trsp(
'SELECT id_tron::integer AS id, source::integer, target::integer,
cost::double precision, rev_cost::double precision AS reverse_cost
FROM rp_test
WHERE type_tron NOT IN(3, 8, 9) AND largeur_c > 90 AND largeur_p > 75',
19314::INTEGER, 10776::INTEGER, true, true,
'SELECT to_cost::double precision, target_id::integer, via_path::text
FROM reseau_global_rest');

I also attach to this message a shape file of the network.

Do I miss something, or is it a bug ?

Thanks for any help,
--
Christophe DAMOUR

_______________________________________________
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 · March 8, 2014, 4:38pm

On 3/8/2014 2:06 AM, Christophe Damour wrote:

Hi Steven,

Thank you for answering.

I double checked the topology and it looks ok.

By the way, when you say "the only way to follow the route is to go the
wrong way down a one-way street" :
Do you mean that this is the expected behaviour ?

The code is in somewhat of a transition in this regard. Historically we could not set the cost to -1 (meaning not allowed) so users set the cost (or reverse cost) to a large number.

I have been up dating the code as I I fix things so that it accepts negative values and eliminates that edge from the graph so it will fail if not route is found.

I thought TRSP already did this. so look at your data and make sure you are not setting and costs to large values.

I expected an error or an exception saying : "Path Not Found" in such a
case.
Is there a workaround for that situation or should I handle it with a
post-query process ?

You can try to set the cost to -1 instead of a large value to eliminate that directed edge. It should work most places but you might run into some algorithms that do not support that and should write a bug if you find one.

Thanks,
-Steve

Thank you again for your time.

Christophe_Damour · March 8, 2014, 5:35pm

Steven,

Thank you very much again for your time !
Setting cost to -1 indeed solved the problem, the query returning "Path not found" as I expected.
I just wasn't aware of that option.

You and other devs do a really great work on pgRouting.
I appreciate and wish I can help in anyway.

--
Christophe DAMOUR

Le 08/03/2014 17:38, Stephen Woodbridge a écrit :

On 3/8/2014 2:06 AM, Christophe Damour wrote:

Hi Steven,

Thank you for answering.

I double checked the topology and it looks ok.

By the way, when you say "the only way to follow the route is to go the
wrong way down a one-way street" :
Do you mean that this is the expected behaviour ?

The code is in somewhat of a transition in this regard. Historically we could not set the cost to -1 (meaning not allowed) so users set the cost (or reverse cost) to a large number.

I have been up dating the code as I I fix things so that it accepts negative values and eliminates that edge from the graph so it will fail if not route is found.

I thought TRSP already did this. so look at your data and make sure you are not setting and costs to large values.

I expected an error or an exception saying : "Path Not Found" in such a
case.
Is there a workaround for that situation or should I handle it with a
post-query process ?

You can try to set the cost to -1 instead of a large value to eliminate that directed edge. It should work most places but you might run into some algorithms that do not support that and should write a bug if you find one.

Thanks,
-Steve

Thank you again for your time.

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