Routing result against one-way roads
Status: Pre-Alpha
Brought to you by:
sakaal
Menu
▾
▴
#10 Routing result against one-way roads
I developed a crude capability to graphically show routing queries. Testing with revision 73 has been quite satisfactory for general road situations using a osm dataset of just Washington DC. Congrats!
One a slight negative, I did come across a number of instances where a routing solution which ran opposite the traffic flow on one-way roads was returned. I realize this may not be osm2postgis causing it. However, I thought I would pass this along just in case. In the attached picture, the route selected is supposed to run from the left side of the picture to the right. As you can see, it chose to go against a one-way road segment. If I reverse the start and end points for the routing query, it still picks the same (lane) over the bridge, so I am confident that I am using the right order in the query parameters.
routing test result
Just wondering is it always going against one way roads, or are these isolated cases? If it does it every time, then it may be that the directions have somehow switched place. Also, can you get the routing query result easily? The picture is very useful, but it would be even more useful with the respective query data. With a list of the related OSM way id's this would be easy to debug. I could trace back to the OSM tags on those ways.
The bridge section seems to be OSM way 50716077. Using Potlach, I can see that it's tagged oneway=yes and OSM2PostGIS should recognize that tag.
Can you do this query (and post the results here) to show the evaluation that OSM2PostGIS has done:
SELECT id,way,source,target,cost,reverse_cost,length FROM navigation_motor WHERE way=50716077;
Sakari, Here is the query result you requested for way 50716077:
51199; 50716077; 646202779; 646202789; 39.5740165710449; 86400; 549.63916
Of the testing that I've done so far, once in a great while I'll see a correct determination for a one way street. It seems to succeed where the first edge is one way, but fails 100% of the time for other cases.
Result returned fromshortest_path_shooting_star, annotated with way id:
(StartEdge: 12903 EndEdge: 8967)
vertex_id: 20946, edge_id: 12903, cost: 14.0819787979126 (way=6061635)
vertex_id: 20948, edge_id: 51191, cost: 6.43440961837769 (way=50715852)
vertex_id: 8004, edge_id: 51192, cost: 1.72699213027954 (way=50715852)
vertex_id: 14036, edge_id: 8209, cost: 2.07699537277222 (way=6057239)
vertex_id: 14037, edge_id: 8215, cost: 0.248953104019165 (way=6057247)
vertex_id: 14048, edge_id: 8216, cost: 0.591792643070221 (way=6057247)
vertex_id: 5793, edge_id: 3555, cost: 7.41017484664917 (way=6052481)
vertex_id: 5794, edge_id: 3556, cost: 10.1127004623413 (way=6052481)
vertex_id: 5796, edge_id: 51198, cost: 22.8415088653564 (way=50716076)
vertex_id: 75312, edge_id: 51254, cost: 6.92742729187012 (way=50716427)
vertex_id: 75379, edge_id: 51252, cost: 13.9738359451294 (way=50716426)
vertex_id: 5774, edge_id: 51253, cost: 9.70720863342285 (way=50716426)
vertex_id: 75313, edge_id: 51199, cost: 39.5740165710449 (way=50716077)
vertex_id: 75314, edge_id: 51200, cost: 5.52570104598999 (way=50716078)
vertex_id: 75316, edge_id: 51201, cost: 14.9950923919678 (way=50716078)
vertex_id: 5684, edge_id: 51204, cost: 6.3350625038147 (way=50716083)
vertex_id: 6100, edge_id: 51205, cost: 28.4503269195557 (way=50716083)
vertex_id: 24231, edge_id: 49183, cost: 6.74420309066772 (way=50515728)
vertex_id: 13889, edge_id: 49189, cost: 6.45031356811523 (way=50515729)
vertex_id: 15262, edge_id: 8967, cost: 11.830267906189 (way=6057801)
Thanks for the results, but it seems that the reverse_cost is missing. The "cost" column is estimated seconds in the direction of the road. The "reverse_cost" column is the same in the opposite direction. To show if OSM2PostGIS has evaluated the route correctly, we need to see both these columns. The value is currently configured to be 86400 in the opposite direction, if it's one-way. The number 86400 is just an arbitrary choice i.e. the number of seconds in 24 hours.
Right now I'm processing my local data so I can check the results with routes I know. Lately, I have had too much other things to do. This is still my number one hobby project, so I will be using several hours per week fixing and developing it.
It looks like what I posted earlier was grabbed from the wrong test results (a hazard of having a long series captured). Please see the following:
SQL: SELECT * FROM shortest_path_shooting_star('SELECT id,source,target,cost,reverse_cost,x1,x2,y1,y2,to_cost,rule FROM navigation_motor', 8967, 12903, true, true)
vertex_id: 15262, edge_id: 8967, cost: 11.830267906189, way:6057801
vertex_id: 15264, edge_id: 38012, cost: 6.49384641647339, way:29961677
vertex_id: 13891, edge_id: 8123, cost: 11.8467779159546, way:6057104
vertex_id: 13889, edge_id: 49183, cost: 6.74420309066772, way:50515728
vertex_id: 24231, edge_id: 51205, cost: 28.4503269195557, way:50716083
vertex_id: 6100, edge_id: 51204, cost: 6.3350625038147, way:50716083
vertex_id: 5684, edge_id: 51201, cost: 14.9950923919678, way:50716078
vertex_id: 75316, edge_id: 51200, cost: 5.52570104598999, way:50716078
vertex_id: 75314, edge_id: 51199, cost: 39.5740165710449, way:50716077
vertex_id: 75313, edge_id: 51253, cost: 9.70720863342285, way:50716426
vertex_id: 5774, edge_id: 51252, cost: 13.9738359451294, way:50716426
vertex_id: 75379, edge_id: 51254, cost: 6.92742729187012, way:50716427
vertex_id: 75312, edge_id: 51198, cost: 22.8415088653564, way:50716076
vertex_id: 5796, edge_id: 3556, cost: 10.1127004623413, way:6052481
vertex_id: 5794, edge_id: 3555, cost: 7.41017484664917, way:6052481
vertex_id: 5793, edge_id: 8216, cost: 0.591792643070221, way:6057247
vertex_id: 14048, edge_id: 8215, cost: 0.248953104019165, way:6057247
vertex_id: 14037, edge_id: 8209, cost: 2.07699537277222, way:6057239
vertex_id: 14036, edge_id: 51192, cost: 1.72699213027954, way:50715852
vertex_id: 8004, edge_id: 51191, cost: 6.43440961837769, way:50715852
vertex_id: 20948, edge_id: 12903, cost: 14.0819787979126, way:6061635
Ok, well the routing algorithm is consuming all the right data, but it's not showing the intermediate query in the results. What I'm interested in is the inner query results. The following queries should give the intermediate results that are most interesting:
To show the OSM tags:
SELECT id,k,v FROM osm_way_tags WHERE ID in (6057801, 29961677, 6057104, 50515728, 50716083, 50716083, 50716078, 50716078, 50716077, 50716426, 50716426, 50716427, 50716076, 6052481, 6052481, 6057247, 6057247, 6057239, 50715852, 50715852, 6061635);
To show the evaluation from OSM2PostGIS:
SELECT way,id,source,target,cost,reverse_cost,length FROM navigation_motor WHERE way IN (6057801, 29961677, 6057104, 50515728, 50716083, 50716083, 50716078, 50716078, 50716077, 50716426, 50716426, 50716427, 50716076, 6052481, 6052481, 6057247, 6057247, 6057239, 50715852, 50715852, 6061635) ORDER BY way;
If the result is too big, you can also attach it / them as files. But it's just fine posting as a comment as well.
I ran the two queries and posted the results as files.
In looking at things closer, I noticed that the geometry in navigation_motor are polylines, vice simple edges. Could this make a difference? For example:
SELECT AsText(geom) FROM navigation_motor WHERE id=51199 produces:
"LINESTRING(-76.9615545 38.8898509,-76.9637969 38.8898529,-76.967898 38.889855)"
This ticket on pgrouting may be related:
http://pgrouting.postlbs.org/ticket/190
F = Forward direction from source to target node
R = Reverse direction from target to source node
"way";"id";"source";"target";"cost";"reverse_cost";"length"
F 6057801;8967;49744907;49763154;11.830267906189;11.830267906189;164.30928
F 29961677;38012;49763154;49763155;6.49384641647339;6.49384641647339;90.192314
R 6057104;8123;49744908;49763155;11.8467779159546;11.8467779159546;164.53859
*R 50515728;49183;49744693;49744908;6.74420309066772;86400;93.66949
*R 50716083;51205;49734195;49744693;28.4503269195557;86400;395.14343
*R 50716083;51204;49729507;49734195;6.3350625038147;86400;87.986984
*R 50716078;51201;646202796;49729507;14.9950923919678;86400;208.26518
*R 50716078;51200;646202789;646202796;5.52570104598999;86400;76.74585
*R 50716077;51199;646202779;646202789;39.5740165710449;86400;549.63916
*R 50716426;51253;646216531;646202779;9.70720863342285;86400;134.82234
*R 50716426;51252;646216523;646216531;13.9738359451294;86400;194.08105
*R 50716427;51254;646216538;646216523;6.92742729187012;86400;96.21427
*R 50716076;51198;646216756;646216538;22.8415088653564;86400;317.2432
*R 6052481;3556;49730371;646216756;10.1127004623413;86400;140.45418
*R 6052481;3555;639496184;49730371;7.41017484664917;86400;102.9191
R 6057247;8216;639496089;639496184;0.591792643070221;0.591792643070221;8.219342
R 6057247;8215;646216410;639496089;0.248953104019165;0.248953104019165;3.4576821
R 6057239;8209;639470020;646216410;2.07699537277222;2.07699537277222;28.84716
R 50715852;51192;646216885;639470020;1.72699213027954;1.72699213027954;23.986002
R 50715852;51191;49830228;646216885;6.43440961837769;6.43440961837769;89.366806
R 6061635;12903;49857755;49830228;14.0819787979126;14.0819787979126;195.58304
From this result you can see that the routing algorithm apparently has chosen the reverse direction for several route segments even when they have a very high cost. Those lines are marked with an asterisk in the above listing. The reverse cost for those segments has been evaluated at 86400 seconds--that is supposed to be prohibitively high, but the algorithm seems to have chosen them regardless. It means that basically OSM2PostGIS has evaluated the route correctly, but pgRouting cannot find any alternative route or is not working right. More likely it's a bug in pgRouting.
I'm not even sure if it's related to the ticket you found, because in our case the first and the last edge are bidirectional. All our one-way segments are in the middle of the route.
We need to keep this bug open until it's solved. When we have more time to test, maybe we can find more similar examples and post this as a bug to pgRouting. Or, maybe there's something about pgRouting that we are doing wrong... I would bet the bug is with pgRouting but we'll see.
Interesting data points. I agree with your assessment; thanks!
Bruce, could you try this again with different last two parameters for the shooting star call: false, true
I browsed through the pgRouting forums and found some posts where they explain that their 'directed' graph means the graph should specify each edge twice - separately for both directions. The OSM2PostGIS generated graphs only specify each edge one time, but with the reverse cost column. So, in pgRouting terminology that might be an 'undirected' graph with reverse cost.
I know matemathically speaking an 'undirected graph with reverse cost' would actually be considered a directed graph. It just guarantees that all the edges exist in both directions, one with cost, the other with reverse cost.
I don't have the time to test this myself right now, but maybe you are better active on this case to try it out?
SELECT * FROM shortest_path_shooting_star('SELECT
id,source,target,cost,reverse_cost,x1,x2,y1,y2,to_cost,rule FROM
navigation_motor', 8967, 12903, false, true)
By the way, if this does solve the problem, then there would be an error in pgRouting documentation that says the reverse_cost is used only when the graph is directed. Go figure...
I ran your query using my code as well as PGADMIN. The results appear to be the same regardless of the directed flag. It's almost like shooting_star_... is not seeing the reverse_cost at all. I did a hand trace of the code looking for the obvious but so far have come up empty handed.
Anyway, for verification here are the results using directed=true vs false. This dataset was created using osm2postgis rev 77.
SQL: SELECT * FROM shortest_path_shooting_star('SELECT id,source,target,cost,reverse_cost,x1,y1,x2,y2,rule,to_cost FROM navigation_motor', 8967, 12903, true, true)
vertex_id: 15262, edge_id: 8967, cost: 11.830267906189, way: 6057801
vertex_id: 15264, edge_id: 38012, cost: 6.49384641647339, way: 29961677
vertex_id: 13891, edge_id: 8123, cost: 11.8467779159546, way: 6057104
vertex_id: 13889, edge_id: 49183, cost: 6.74420309066772, way: 50515728
vertex_id: 24231, edge_id: 51205, cost: 28.4503269195557, way: 50716083
vertex_id: 6100, edge_id: 51204, cost: 6.3350625038147, way: 50716083
vertex_id: 5684, edge_id: 51201, cost: 14.9950923919678, way: 50716078
vertex_id: 75316, edge_id: 51200, cost: 5.52570104598999, way: 50716078
vertex_id: 75314, edge_id: 51199, cost: 39.5740165710449, way: 50716077
vertex_id: 75313, edge_id: 51253, cost: 9.70720863342285, way: 50716426
vertex_id: 5774, edge_id: 51252, cost: 13.9738359451294, way: 50716426
vertex_id: 75379, edge_id: 51254, cost: 6.92742729187012, way: 50716427
vertex_id: 75312, edge_id: 51198, cost: 22.8415088653564, way: 50716076
vertex_id: 5796, edge_id: 3556, cost: 10.1127004623413, way: 6052481
vertex_id: 5794, edge_id: 3555, cost: 7.41017484664917, way: 6052481
vertex_id: 5793, edge_id: 8216, cost: 0.591792643070221, way: 6057247
vertex_id: 14048, edge_id: 8215, cost: 0.248953104019165, way: 6057247
vertex_id: 14037, edge_id: 8209, cost: 2.07699537277222, way: 6057239
vertex_id: 14036, edge_id: 51192, cost: 1.72699213027954, way: 50715852
vertex_id: 8004, edge_id: 51191, cost: 6.43440961837769, way: 50715852
vertex_id: 20948, edge_id: 12903, cost: 14.0819787979126, way: 6061635
SQL: SELECT * FROM shortest_path_shooting_star('SELECT id,source,target,cost,reverse_cost,x1,y1,x2,y2,rule,to_cost FROM navigation_motor', 8967, 12903, false, true)
vertex_id: 15262, edge_id: 8967, cost: 11.830267906189, way: 6057801
vertex_id: 15264, edge_id: 38012, cost: 6.49384641647339, way: 29961677
vertex_id: 13891, edge_id: 8123, cost: 11.8467779159546, way: 6057104
vertex_id: 13889, edge_id: 49183, cost: 6.74420309066772, way: 50515728
vertex_id: 24231, edge_id: 51205, cost: 28.4503269195557, way: 50716083
vertex_id: 6100, edge_id: 51204, cost: 6.3350625038147, way: 50716083
vertex_id: 5684, edge_id: 51201, cost: 14.9950923919678, way: 50716078
vertex_id: 75316, edge_id: 51200, cost: 5.52570104598999, way: 50716078
vertex_id: 75314, edge_id: 51199, cost: 39.5740165710449, way: 50716077
vertex_id: 75313, edge_id: 51253, cost: 9.70720863342285, way: 50716426
vertex_id: 5774, edge_id: 51252, cost: 13.9738359451294, way: 50716426
vertex_id: 75379, edge_id: 51254, cost: 6.92742729187012, way: 50716427
vertex_id: 75312, edge_id: 51198, cost: 22.8415088653564, way: 50716076
vertex_id: 5796, edge_id: 3556, cost: 10.1127004623413, way: 6052481
vertex_id: 5794, edge_id: 3555, cost: 7.41017484664917, way: 6052481
vertex_id: 5793, edge_id: 8216, cost: 0.591792643070221, way: 6057247
vertex_id: 14048, edge_id: 8215, cost: 0.248953104019165, way: 6057247
vertex_id: 14037, edge_id: 8209, cost: 2.07699537277222, way: 6057239
vertex_id: 14036, edge_id: 51192, cost: 1.72699213027954, way: 50715852
vertex_id: 8004, edge_id: 51191, cost: 6.43440961837769, way: 50715852
vertex_id: 20948, edge_id: 12903, cost: 14.0819787979126, way: 6061635
Sakari, I've done some more testing and posted a comment to the pgrouting forum: http://pgrouting.postlbs.org/discussion/topic/339#message1434
I went ahead and moved my comment to a new thread on pgrouting ( http://pgrouting.postlbs.org/discussion/topic/344 ).
Also, I came across this pgrouting code change which I believe is related to this issue:
http://pgrouting.postlbs.org/changeset/355/trunk/core/src/shooting_star_boost_wrapper.cpp
I had suspected this block during my hand trace. Unfortunately I am not able to build the revised pgrouting libs yet (win32, sigh) so I can try the fix.
Again great thanks Bruce! It seems that I will be experimenting also with some of my own routing algorithms in the months to come... Of course we want to make OSM2PostGIS work with pgRouting but it seems that pgRouting itself still has some problems. Of course OSM2PostGIS doesn't have to be limited to just pgRouting. There may be other routing applications (that may or may not exist yet) that can use the same basic data. This should be beneficial for the development of pgRouting as well - when we can point out and help fix their inconsistencies.