Opened 8 years ago

Closed 3 years ago

#876 closed defect/bug (worksforme)

Bad routing analysed: attached bookmarks and screenshots for debugging

Reported by: joysfera Owned by: KaZeR
Priority: critical Milestone: version 0.5.1
Component: core Version: git master
Severity: normal Keywords: routing, highway
Cc: pstehlik@…, fre.labrosse@…, cp15

Description

I was wondering why current SVN Navit, when asked to plan route using OSM map between Zlin and Plzen (=Pilsen, both in Czech Republic) plans out a route via Austria that is 2,5x longer than needed (840+ km instead of 340 km). I tried to pinpoint the problem and have come to the following:

From "Zlin" (exact point given in the attached bookmark.txt) up to "Lodenice" the route is correct - using the D1 and D5 highways. When going farther in the "Plzen/Pilsen?" direction on the D5 highway Navit breaks and stops routing altogether. When one gets to the point of "Zdice" Navit suddenly starts routing via Austria, a trip 2,5x longer than necessary!

Please try out using the attached bookmark.txt - it has three bookmarks named Start, Good and Bad. Use Start as Position and Good/Bad? as Destination. The Good and Bad are exact points on the D5 highway where Navit starts breaking - move 100 m farther and Navit doesn't route at all.

Attached are also two screenshots showing the correct route to "Lodenice" and completely bogus one to neighbor "Zdice".

"Beroun" (another town on the D5 highway sitting in between of "Lodenice" and "Zdice") is an example of Destination that Navit cannot route to at all.

Note that it is crucial to use the "Start" bookmark as Position. If you use "Zlin" as position the breakpoints are different (but close to what I pinpointed above).

I have used a clean svn checkout (revision 4510/26104), selfcompiled and run with config file from Ubuntu Lucid Lynx's Navit 0.2.0~svn2897+dfsg.1-1build1.

Attachments (5)

bookmark.txt (180 bytes) - added by joysfera 8 years ago.
Use these bookmarks
Lodenice.png (41.0 KB) - added by joysfera 8 years ago.
Good route using D1 and D5 highways
Zdice.png (36.8 KB) - added by joysfera 8 years ago.
Bad (insane) route via Austria - 2,5x longer than needed
unconnected-route-graph.jpg (77.9 KB) - added by tryagain 8 years ago.
Sample of the edge which is not connected to the rest of the route graph.
maptool_higway_trunk_routable.diff (610 bytes) - added by tryagain.myopenid.com 8 years ago.
makes roads of internal type street_4_land, street_4_city (marked highway=trunk in OSM) avaliable for distant routing.

Download all attachments as: .zip

Change History (31)

Changed 8 years ago by joysfera

Use these bookmarks

Changed 8 years ago by joysfera

Good route using D1 and D5 highways

Changed 8 years ago by joysfera

Bad (insane) route via Austria - 2,5x longer than needed

Changed 8 years ago by tryagain

Sample of the edge which is not connected to the rest of the route graph.

comment:1 follow-up: Changed 8 years ago by tryagain

It's well known that Navit doesn't have good routing for long distances. And it's supposed that problem is in the way it limits the data used for route graph building process.

But look here.

I've been playing with quite long route from Белгород (at the South) to Фатеж (at the North), RU. It just don't build. Then I tried to seek the point where route graph breaks. Switched on route graph display in Settings - Maps and got one interesting screenshot:

http://trac.navit-project.org/attachment/ticket/876/unconnected-route-graph.jpg

What I see is route grapth edge (shown at the bottom right) that has no connection with other route graph edges (closest to it are shown at the upper left).

Both vertexes of botom right edge are marked with "-". Rg_segment debug: attribute contains data "len 504 time 453 start 0xe32ac8 end 0xd78" (rest is invisible). Right rg_point has label '-', debug "0 1 0xd78e88 (0x3d3e70,0x66a301)". Left rg_point has label '-', debug '1 0 0xe32ac8 (0x3d3c85, 0x66a07b)'.

Road drawn in red is street_4_land (osm_wayid:106486214) and is not followed by route graph in the south direction. I thoght it's big road enough to be taken into account at any distance from the endpoints.

If I correctly understand route algorythm used, route graph at any step should remain connected. Then we have a problem with core of routing algorithm implementation, not with some road network data skipped at long distances. In the latter case routing graph should end up connected but not reached Position.

Last edited 6 years ago by usul (previous) (diff)

comment:2 in reply to: ↑ 1 Changed 8 years ago by tryagain

Well, I've got a half of answer. rg_point(s) and rg_segment(s) are created for each way segment available for routing at the first stage. So unconnected elements may appear and will remain tagged with '-' at the end of the routing.

But why did south part of red road (osm_wayid:106486214) did not came to the routing graph? Is it considered too small for far routing?

comment:3 Changed 8 years ago by joysfera

I think you (user:tryagain) are discussing something maybe related but still different from my bug report. So feel free to create your own trac ticket.

What I am showing here is that I've located an exact point on a huge highway where routing stops working sanely. Move back 100 metres and it routes fine - move forward 100 metres and it breaks like if the road didn't continue. This is not about unconnected route graphs or taking various roads into account - this shows that the routing goes crazy even on a short trip (300 km) between two large cities connected via a highway.

comment:4 Changed 8 years ago by tryagain.myopenid.com

joysfera, no, the problem is the same. Look at your screenshots: there is a piece of road around Praha missing. I bet it's missing not only from screen representation but from routing graph too. Navit may use for routing "minor" roads only close to Destination and Source.

We both had failed to have Navit to build quite a long route via a way tagged in OSM as highway=trunk. You have alternate route via highway=motorway, but I'm not.

So, I conclude, we have to review (at least for Russia, we have really big distances and very limited number of roads that can be tagged as highway=motorway or even with motorroad=yes).

I'd suggest to change maptool to rise level of roads tagged as highway=trunk. Primary routing for Russia probably should be done on these roads.

Changed 8 years ago by tryagain.myopenid.com

makes roads of internal type street_4_land, street_4_city (marked highway=trunk in OSM) avaliable for distant routing.

comment:5 Changed 8 years ago by tryagain.myopenid.com

Please try this if you can build Navit and maps yourself. As the patch changes maptool, you will not able to test the patch unless you build your map yourself with patched maptool from osm data. You can get osm data from geofabrik.de to build a map .

I've got Navit to build for me a route from Belgorod to Moscow, 700 km of length, optimal at first glance (bypassing cities, not making too big detours). That distance is not a limit. No other patches to increase the routing distance are needed.

comment:6 Changed 8 years ago by tryagain.myopenid.com

http://wiki.openstreetmap.org/wiki/Tag:highway%3Dtrunk says:

Important roads that aren’t motorways. Often suitable for long journeys or relatively high speeds. ... Australia National highways; state strategic road network. Connecting major population centres. For example Bruce Highway, Pacific Highway.

It's not a surprise we have big detours by highway=motorway without this patch.

comment:7 Changed 8 years ago by fred labrosse

  • Cc fre.labrosse@… added

comment:8 Changed 8 years ago by tryagain.myopenid.com

  • Resolution set to fixed
  • Status changed from new to closed

Patch maptool_higway_trunk_routable.diff was added in Revision 4536

comment:9 Changed 8 years ago by arnaud le meur

It's a very good news to have added this patch, I will be able to going back home :)

Do you know when this release will be used in planet extractor ? If it will be...

Last edited 8 years ago by arnaud le meur (previous) (diff)

comment:10 Changed 8 years ago by joysfera

I have tried it yesterday with Navit 4536 running on N810 and maps downloaded freshly from http://maps.navit-project.org/ - the Zlin->Plzen route is still incorrect as described in this ticket.

So either the maps.navit-project.org doesn't use an up-to-date maptool or the fix doesn't work.

comment:11 Changed 8 years ago by joysfera

  • Resolution fixed deleted
  • Status changed from closed to reopened

comment:12 Changed 8 years ago by tryagain.myopenid.com

maps at maps.navit-project.org are not updated that fast.

If you decide to make maps yourself to test it, be warned that it was slightly rolled back in revision 4537:

http://navit.svn.sourceforge.net/viewvc/navit/trunk/navit/navit/maptool/misc.c?r1=4536&r2=4537

So it's adviceable to test it with both revisions of maptool if fresh svn version will not satisfy your needs.

Last edited 8 years ago by tryagain.myopenid.com (previous) (diff)

comment:13 Changed 8 years ago by arnaud le meur

does rev4537 maintain the bug fixing ?

comment:14 Changed 8 years ago by tryagain.myopenid.com

With current release to get it working you'll need to change by hand in route.c route_rect(4, to route_rect(5, see http://irclogs.navit.ie/%23navit-2011-06-24.log and use self-compiled navit version.

comment:15 follow-up: Changed 8 years ago by joysfera

I have just tried up-to-date SVN of Navit, self-compiled maptool's converted fresh OSM map, navit patched with route_rect(4,..) -> route_rect(5,..)

Route Zlin -> Plzen NOT FOUND ("navit:route_path_new:no route found, pos blocked")

This bug is still valid, unfortunately.

Last edited 8 years ago by joysfera (previous) (diff)

comment:16 in reply to: ↑ 15 Changed 8 years ago by arnaud le meur

Replying to joysfera:

I have just tried up-to-date SVN of Navit, self-compiled maptool's converted fresh OSM map, navit patched with route_rect(4,..) -> route_rect(5,..)

Route Zlin -> Plzen NOT FOUND ("navit:route_path_new:no route found, pos blocked")

This bug is still valid, unfortunately.

Try to replace route_rect(4,..) by route_rect(6,..) to route with trunk roads.

I had the same problem to reach Brest in France, only trunk roads are available, not highways.

With 5, the route is not found, with 6, it works. See http://irclogs.navit.ie/%23navit-2011-07-01.log 20:56

You will find an explanation about this parameter.

comment:17 Changed 8 years ago by joysfera

With SVN 4578 and fresh map from maps.navit-project.org the Zlin -> Plzen route works even with route_rect(4, ..). I was about to start celebrating but then I happened to try Zlin -> Usti nad Labem route and found out that without route_rect(6,) the report is just "navit:route_path_new:no route found, pos blocked".

So for routing in Czech Republic (max ~400 km) using OSM data the route_rect(6,..) seems to be the minimal acceptable value for a working Navit navigation.

comment:18 Changed 8 years ago by tryagain

Route Zlin -> Usti nad Labem built with Clodmade goes in its middle part via several highway=primary roads, for example, Za Viaduktem, Praha, http://www.openstreetmap.org/browse/way/33772842

These roads are invisible for Navit in the middle part of route. As per OSM, http://wiki.openstreetmap.org/wiki/Tag:highway%3Dprimary, these are "A major highway linking large towns, normally with 2 lanes. The traffic for both directions is usually not separated by a central barrier". We do not use such roads for distant routing, requiring to have at least highway=trunk roads be available in the middle of route.

I don't think that in Praha, you have to drive by two-lane road without central barrier to get from one highway=motorway to another.

So I'd suggest to review OSM tagging of roads used by Cloudmade near Praha and check if it can be changed from highway=primary to highway=trunk. Also good candidate seems to be Kbelska http://www.openstreetmap.org/browse/way/16588880, Prumyslova http://www.openstreetmap.org/browse/way/16589007 (and others), which may give better route outside the city.

Last edited 8 years ago by tryagain (previous) (diff)

comment:19 follow-up: Changed 8 years ago by korrosa

Just an FYI for those who may not be aware:

Please note that Cloudmade maps for Navit use outdated versions of Maptool, which is why the wiki warns against using them: http://wiki.navit-project.org/index.php/OpenStreetMaps#Cloudmade

If testing routing with the view to patching, please either process your own maps or use those from the map extractor: http://maps.navit-project.org/

comment:20 in reply to: ↑ 19 Changed 8 years ago by tryagain

Replying to http://wiki.navit-project.org/index.php/user:korrosa:

Just an FYI for those who may not be aware: If testing routing with the view to patching, please either process your own maps or use those from the map extractor: http://maps.navit-project.org/

I'm aware, I used cloudmade web interface only to test if routing is at all possible with osm data. Current svn of navit with current maptool-generated maps seems not to be able to build any route Zlin -> Usti nad Labem.

comment:21 Changed 6 years ago by usul

  • Cc cp15 added
  • Keywords routing highway added
  • Milestone set to version 0.5.1
  • Priority changed from major to critical

This bug has to be checked for the current release/map data. Anybody else has bad routing experience from OSM? Please crosscheck with OSRM!

As a heavy bug related to routing, I schedule it for 0.5.1 hotfix

comment:22 Changed 4 years ago by klosels

  • Severity set to normal

I do have another sample where routing even never yields any result at all unless an additional waypoint is added. The route is less than 200km. Here we go:

  • set "73000 Chambéry, France, Rhone-Alpes" as current position
  • set "05700 Orpierre, France, Hautes-Alpes" as destination

=> Navit never suceeds in finding a route

  • set "38640 Claix, France, Rhone-Alpes" as additional waypoint in between

=> Navit finds the correct/quickest route

Claix is very near the direct route, so it doesn't change the resulting route much aside from a quick turn-off and back to the main road.

The puzzling thing is: Navit succeeds to find the route from Chambéry to Claix as well as from Claix to Orpierre!

OSRM has no problems finding the route without the middle waypoint.

I notices this first with an older Navit version from approx. one year ago, but it hasn't changed in current versions.

comment:23 Changed 4 years ago by tryagain

"73000 Chambéry, France, Rhone-Alpes" -> "05700 Orpierre, France, Hautes-Alpes" worked well for me after i have selected the car(Pedantic) vehicle profile from settings->vehicle.

Pedantic car profile was first described at #456 comment 49 and some discussion follows there.

comment:24 Changed 4 years ago by tryagain

I have reviewed cases reported before. Route Zlin->Usti Nad Labem works for me ok (i.e. routes through Praha), with "car pedantic" profile. But i had to select a different starting point, for example, on the road in around hundred meters to the east.

Zlin -> Plzen works fine even with simple "car" vehicle profile, with same starting point modification.

The square at the Zlin centre has routable streets not connected to other roads, so car route can't start from that place. Probably http://www.openstreetmap.org/way/66890737 makes navit to fail, because it's the closest car routable street but you cant get from it anywhere by car. I guess osm data needs some fixing here. Anyway, it's a different problem.

comment:25 Changed 3 years ago by kazer

Since this problem seems to be solved by switched to route_pedantic, can we close this ticket?

It looks like #1296

comment:26 Changed 3 years ago by kazer

  • Resolution set to worksforme
  • Status changed from reopened to closed

Got an email from Petr to close this ticket.

Note: See TracTickets for help on using tickets.