Opened 8 years ago

Last modified 12 months ago

#630 new defect/bug

Bad routing when a turn restriction is involved

Reported by: chr Owned by: KaZeR
Priority: major Milestone: version 0.6.0
Component: core Version: git master
Severity: complex Keywords: routing, turn, restrictions
Cc:

Description

Hello!

I guess I found a routing bug in combination with turn restrictions. Here comes an examples. Routing from Germany > Düsseldorf > Hermannstraße 51.23093 N, 6.80705 E to Neanderstraße 51.22935 N, 6.80449 E is fine.Routing a little bit further northwards to Neanderstraße 51.23052 N, 6.80369 E results in a wrong route. With 'wrong route' I mean it is not the fastest nor the shortest. Extending the first solution a little bit to the second target seems to be omitted somehow. The related turn restriction is at the northern end of the Hermannstraße. I prepared two screenshots, but I don't know how to share.

regards,

Christian

Attachments (5)

turn-restriction-1.png (122.5 KB) - added by chr 8 years ago.
successful routing
turn-restriction-2.png (122.0 KB) - added by chr 8 years ago.
bad routing solution due to only_right_turn restriction
turn-restriction-7.png (81.5 KB) - added by chr 8 years ago.
routing in Hilden, not convincing
turn-restriction-21.png (98.7 KB) - added by chr 8 years ago.
turn-restriction-23.png (103.5 KB) - added by chr 8 years ago.

Download all attachments as: .zip

Change History (15)

Changed 8 years ago by chr

successful routing

Changed 8 years ago by chr

bad routing solution due to only_right_turn restriction

comment:1 in reply to: ↑ description Changed 8 years ago by tegzed

Hello Chr,

Maybe it is not a Navit issue, this can be caused by the type of the streets in the osm database and the weight assigned for those street types. Navit's maptool maps osm road types to its own road types in maptool/osm.c Eg.:


    534         "w      highway=plaza                           poly_plaza\n"
    535         "w      highway=motorway                        highway_land\n"
    536         "w      highway=motorway,rural=0                highway_city\n"
    537         "w      highway=motorway_link                   ramp\n"
    538         "w      highway=trunk                           street_4_land\n"
    539         "w      highway=trunk,name=*,rural=1            street_4_land\n"
    540         "w      highway=trunk,name=*                    street_4_city\n"
    541         "w      highway=trunk,rural=0                   street_4_city\n"
    542         "w      highway=trunk_link                      ramp\n"
    543         "w      highway=primary                         street_4_land\n"
    544         "w      highway=primary,name=*,rural=1          street_4_land\n"
    545         "w      highway=primary,name=*                  street_4_city\n"
    546         "w      highway=primary,rural=0                 street_4_city\n"
    547         "w      highway=primary_link                    ramp\n"
    548         "w      highway=secondary                       street_3_land\n"

And these internal road types's routing weight is set in navit.xml in the roadprofile tags' route_weight attribute. Maybe Dorotheenstrasse and Grafenberger Allee have much better weight than Neanderstrasse and Ackerstrasse. I experienced a similar problem that is described at http://sourceforge.net/projects/navit/forums/forum/512960/topic/3702652 . You can change the type of the roads in osm or you chan change the assigned route_weight in navit.xml's roadprofile.

Bye, David

comment:2 Changed 8 years ago by chr

Hello David,

thank you for your answer and giving me a better unserstanding for navit's routing using osm-maps! I think you are at least partially right. With your information it is difficult for me to proof my theses.

For a better evaluation I miss the information about the calculated time to go and the calculated distance to go. The OSD presents these values just when I start the journey. But I do click with the mouse on 'set as destination' and 'set as position' and actually never start the jouney. Where do I find the route data?

I found another example to suspend this bug report. It seems to be more abvious. The routing goes from Germany > Hilden > Gerresheimerstraße 51.18817 N, 6.92200 E to Lodenheide 51.18827 N, 6.92522 E. The turn restriction is 'only_straight_on' on the Gerresheimerstraße corner Lodenheide. The routing result is shown in the attached image (turn-restriction-7.png).

Google-maps calculates the route to 600m and 1 minute routing Gerresheimer > Kosenberg > Lodenheide. Forcing Google-maps to choose navit's route, I get 2.9 km and 7 minutes. Can this difference still be explained with 'route_weight' tags? If yes, I really have to examine my navit.xml file.

And last not least. When the target is set few meters further south-east-wards in the Lodenheide, navit chooses the short route via Kosenberg.

Regards,

Christian

Changed 8 years ago by chr

routing in Hilden, not convincing

comment:3 Changed 8 years ago by woglinde

Hi,

png7 looks like an error in osm Data too. To understand routing please read here

http://wiki.navit-project.org/index.php/Routing

and especially for osm data here:

http://wiki.navit-project.org/index.php/OpenStreetMap#Routes_go_through_a_city_instead_around_of_it

comment:4 Changed 8 years ago by chr

Hello Woglinde,

what do you mean? What do you call an osm error?

Regards,

Christian

comment:5 Changed 8 years ago by woglinde

I checked the data with josm its not a bug in the osm-data. From your picture it looked like the bus stop is involved but it is not. I have no clue at the moment mabyee the gtk-gui may help. To understand it. Maybee the higher speedlimit on westring is an issue.

comment:6 Changed 8 years ago by chr

Hello,

Thanks to Woglinde for the links! They made me understand the 'Route Graph' information. With the help of 'Route Graph' I investigated two additional routing examples at Germany > Hilden > Lodenheide (see image: turn-restriction-21.png and turn-restriction-23.png). These routing examples defers only few meters in the destination. Both routes pass the crossing Gerresheimer - Kosenberg. In examples turn-restriction-21.png there are 97.2 seconds to go to the destination, in examples turn-restriction-23.png there are 99.3 seconds to go. Thus the difference is 2.1 seconds. With this information I am now sure, the strange routing of turn-restriction-21.png is not influenced by route weights. It is a bug in navit.

Bug description: When a turn restriction becomes operative for a node, not only the motion in the restricted directions is disabled. The motion in all directions is disabled and routings is blocked at this node.

Regards,

Christian

Changed 8 years ago by chr

Changed 8 years ago by chr

comment:7 Changed 8 years ago by chr

Hi,

Here comes an osm mini-abstraction of the streets Gerresheimer - Kosenberg - Lodenheide for verification of the bug. Navit does not find a route from the northern end of Gerresheimer to the western part of Lodenheide.

Regards,

Christian

<?xml version='1.0' encoding='UTF-8'?>
<osm version='0.6' generator='JOSM'>
  <node id='-3314' visible='true' lat='51.18858856969027' lon='6.923953936956098' />
  <node id='-3312' visible='true' lat='51.188461077515754' lon='6.9249960469043135' />
  <node id='-3307' visible='true' lat='51.1876074342603' lon='6.926182278441112' />
  <node id='-3299' visible='true' lat='51.18643228899955' lon='6.924081429130614' />
  <node id='-3297' visible='true' lat='51.187923393127576' lon='6.922274366135304' />
  <node id='-3296' visible='true' lat='51.18877149324501' lon='6.9212599718772' />
  <way id='-3317' action='modify' visible='true'>
    <nd ref='-3307' />
    <nd ref='-3312' />
    <nd ref='-3314' />
    <nd ref='-3297' />
    <tag k='highway' v='living_street' />
    <tag k='name' v='Lodenheide' />
  </way>
  <way id='-3309' action='modify' visible='true'>
    <nd ref='-3299' />
    <nd ref='-3307' />
    <tag k='highway' v='living_street' />
    <tag k='name' v='Kosenberg' />
  </way>
  <way id='-3301' action='modify' visible='true'>
    <nd ref='-3297' />
    <nd ref='-3299' />
    <tag k='highway' v='living_street' />
    <tag k='name' v='Gerresheimer' />
  </way>
  <way id='-3298' action='modify' visible='true'>
    <nd ref='-3296' />
    <nd ref='-3297' />
    <tag k='highway' v='living_street' />
    <tag k='name' v='Gerresheimer' />
  </way>
  <relation id='-3320' visible='true'>
    <member type='way' ref='-3298' role='from' />
    <member type='way' ref='-3301' role='to' />
    <member type='node' ref='-3297' role='via' />
    <tag k='restriction' v='only_straight_on' />
    <tag k='type' v='restriction' />
  </relation>
</osm>
Last edited 5 years ago by usul (previous) (diff)

comment:8 Changed 8 years ago by kazer

  • Milestone set to version 0.3.0

comment:9 Changed 5 years ago by usul

  • Keywords routing turn restrictions added
  • Milestone changed from version 0.5.0 to version 0.5.1

We need some informations here!

  • Is Navit working on turning-restrictions in general?
  • How about restrictions between mixed street-classes as described?

comment:10 Changed 12 months ago by http://wiki.navit-project.org/index.php/user:jkoan

  • Milestone changed from version 0.5.1 to version 0.6.0
  • Severity set to complex

Probably we should also add tests to our routing qa. But for now I move this to 0.6 because we want to get the 0.5.2 out in a short time, and this one will probably complex.

Note: See TracTickets for help on using tickets.