Routing : some problems analyzed

[aerostitch]

Issue migrated from trac ticket # 1279

component: osd/core | priority: major

2014-12-23 04:52:11: @jandegr created the issue

---

Below a few samples, causes and hopefully even solutions to some common routing problems

[aerostitch]

2014-12-23 05:09:08: @jandegr commented

---

First sample : [[Image(https://dl.dropboxusercontent.com/u/93775123/Navit/routing/Capture.JPG)]] Using the 'car' profile from navit_shipped.xml The route goes over the roundabout instead of over the bypassing branch of the ramp. The ramp does not have an OSM maxspeed tag and uses the 'route weight' from the roadprofile. The route over the roundabout is calculated as 1 second faster, compared to the shortcutting ramp (the piece on the roundabout is 1.1 second). Reason/cause : maptool maps all the following OSM types to type ramp : motorway_link, trunk_link, primary_link, secondary_link and tertiary_link. The solution is to differentiate those mappings, so a motorway_link (and trunk_link) can be assigned a higher 'route weight' If this is not realistic then an alternative could be to map primary_link, secondary_link and tertiary_link to their corresponding road types and let ramp only be a motorway_link or a trunk_link, and then they can have a more realistic 'route_weight'

[aerostitch]

2014-12-23 05:09:08: @jandegr

[aerostitch]

2014-12-23 05:09:08: @jandegr

[aerostitch]

2014-12-23 05:09:08: @jandegr

[aerostitch]

2014-12-23 05:09:08: @jandegr

[aerostitch]

2014-12-23 05:38:08: @jandegr commented

---

Second sample:

The problem can not be shown in one single screenshot, but it happens there : [http://www.openstreetmap.org/#map=14/51.1382/4.1561] At exit 14;15 one can leave the motorway and drive over a number of ramps/parallel roads to merge on the motorway agian 3809 meter further, and it's exactly what the routing engine does. The motorway and the ramps all have OSM maxspeed = 120 and an identical length of 3809 meter between the exit and the point where Navit joins the motorway again. The ramp-route has 10 segments and the motorway-route has 3 segments, because of rounding the time over the ramps is calculated as 0,3 seconds shorter, despite identical speed and length. However all of that is circumstantial and the problem is that Navit has no way to average OSM maxspeed. route_seg_speed() in route.c now uses OSM_maxspeed if available, or otherwise it uses route_weight. The solution is to change as follows : In the roadprofile we need 'road_default_speed' and 'road_speed_avaraging'

In case there is OSM maxspeed then route_seg_speed() uses speed_to_use = (OSM maxspeed) * 'road_speed_avaraging'/100

otherwise:

speed_to_use = 'road_default_speed' * 'road_speed_avaraging'/100

And for motorway's we could have in Navit.xml

motorway road_default_speed="120" road_speed_averaging=100 ramp road_default_speed="100" road_speed_averaging=80

giving 120 resp 80 km/h as 'speed_to_use'

in the above sample this would become 120 resp. 96 km/h in case both have OSM maxspeed=120.

In the first sample (with the roundabout), the ramps would be calculated with 'speed_to_use' = 80km/h, solving the case as well.

I already test such a modification and will post a patch after some more testing, but pls. anyone give your opinion. Now the speed_to_use for a ramp can be anywhere from 40km/h from the xml up to 120km/h from OSM maxspeed, making it impossible to calculate a good route. The speeds and averaging for in the xml are subject to further refining.

[aerostitch]

2014-12-23 05:38:08: @jandegr

[aerostitch]

2014-12-23 05:38:08: @jandegr

[aerostitch]

2014-12-23 05:38:08: @jandegr

[aerostitch]

2014-12-23 05:38:08: @jandegr

[aerostitch]

2014-12-23 06:01:01: @jandegr commented

---

A few more notes :

The 'roundabout' entry in the xml with a route_weight="10" is not applicable to OSM, we don't have a roadtype roundabout in OSM. In the first sample the speed_to_use is 80km/h from street_4_land in the xml. In route_seg_speed() the speed could be reduced to 50% or even less of the speed for the roadtype as a penalty for a roundabout.

Also read-up on #417

Up to now I found not a single place in the code where the speed-tag of the roadprofile is actually used. I even went as far as deleting all of them in the XML file and expected everything to go wrong, but Navit just worked the same as before, routing, eta, ... noticed no difference.

[aerostitch]

2014-12-23 06:01:01: @jandegr

[aerostitch]

2014-12-23 06:01:01: @jandegr

[aerostitch]

2014-12-23 06:01:01: @jandegr

[aerostitch]

2014-12-23 06:01:01: @jandegr

[aerostitch]

2014-12-23 06:01:01: @jandegr

[aerostitch]

2014-12-23 06:01:01: @jandegr

[aerostitch]

2014-12-23 12:18:33: @jandegr commented

---

First test results with averaging : the roadprofile->speed attribute is now used as default speed for a road type. the roadprofile->route_weight attribute is used as averaging factor motorway has speed=120 and route_weight=100 in navit.xml, if you want to you can average at approx. maxspeed on motorways, so it's speed is not modified. ramp has speed=90 and route_weight=80, so speed_used # 90 8072 for the first case without maxspeed and speed_used # 120 8096 km/h for the second case where the ramp has a maxspeed=120.

The first case :-->solved despite of the roundabout only averaged according to roadtype and not penalized for being a roundabout yet. The ramp in the other direction has OSM maxspeed = 70 km/h, averaged to 55km/h now. [[Image(https://dl.dropboxusercontent.com/u/93775123/Navit/routing/Capture3.JPG)]]

The second case : --> speed on the ramp is now reduced to 95km/h from it's maxspeed of 120km/h The motorway stays at 120km/h because of route_weight=100 (value not shown on the screencap) --> case solved [[Image(https://dl.dropboxusercontent.com/u/93775123/Navit/routing/Capture4.JPG)]]

I will provide a patch for route.c after some more testing.

[aerostitch]

2014-12-23 12:18:33: @jandegr

[aerostitch]

2014-12-23 12:18:33: @jandegr

[aerostitch]

2014-12-23 12:18:33: @jandegr

[aerostitch]

2014-12-23 12:18:33: @jandegr

[aerostitch]

2014-12-23 12:18:33: @jandegr

[aerostitch]

2014-12-23 14:36:02: @pgrandin uploaded file Screen Shot 2014-12-23 at 2.21.03 PM.png (53.9 KiB)

routing issue example for #1279

[aerostitch]

2014-12-23 14:44:01: @pgrandin commented

---

As discussed on IRC here is an example of a similar issue I spotted.

[[Image(Screen Shot 2014-12-23 at 2.21.03 PM.png​)]]

The relevant OSM way id: http://www.openstreetmap.org/way/174948429

Jan, does your patch address this example too?

Thanks!

[aerostitch]

2014-12-23 22:45:59: @jandegr commented

---

Like this ? [[Image(https://dl.dropboxusercontent.com/u/93775123/Navit/routing/Capture5.JPG)]] The issue is very similar to my sample with the roundabout, but in your case the values in the XML should be 'americanized' and for real-life routing the primary,secondary and tertiary link's must not be mapped to 'ramp' anymore in maptool. In this case the ramp is in fact a type primary_link in OSM and in my proposal this would be mapped to the same street_4_city as those other roads, have the same speed so provide a faster path to cut the corner. It would also be rendered in the same colour as the street_4_city 's.

A small recap of all posts above : Mapping all link types to ramp is really wrong and leads to all kind of bad routes. This is to be fixed in maptool and in XML increase the speed for the 2 remaining ramp's. The patch for route.c can average or reduce speeds for certain roadtypes, and this applies to OSM maxspeed as well, preventing certain roads to be preferred by Navit too much.

Will probably not do : add a penalty for each traffic light, will cost more CPU and the possibility to 'average' speeds may already do some compensation.

EDIT : I now also have roundabout_weight : speed_used for a roundabout is now

speed_used = (OSM_maxspeed or roadprofile_speed) * route_weight/100 * roundabout_weight/100

A few valid sample lines from Navit.xml :

<roadprofile item_types="highway_land" speed="120"  />
<roadprofile item_types="street_n_lanes" speed="120" route_weight="95" />
<roadprofile item_types="street_4_land" speed="80" route_weight="90" roundabout_weight="60"/>
<roadprofile item_types="street_3_city" speed="50" roundabout_weight="55"/>

merry christmass to all the Navit-ers

[aerostitch]

2014-12-23 22:45:59: @jandegr

[aerostitch]

2014-12-23 22:45:59: @jandegr

[aerostitch]

2014-12-23 22:45:59: @jandegr

[aerostitch]

2014-12-23 22:45:59: @jandegr

[aerostitch]

2014-12-23 22:45:59: @jandegr

[aerostitch]

2014-12-23 22:45:59: @jandegr

[aerostitch]

2014-12-23 22:45:59: @jandegr

[aerostitch]

2014-12-23 22:45:59: @jandegr

[aerostitch]

2014-12-25 00:00:24: @jandegr uploaded file Capture.JPG (77.4 KiB)

first sample for #1276

[aerostitch]

2014-12-25 00:00:58: @jandegr uploaded file Capture2.JPG (76.0 KiB)

second sample for #1279

[aerostitch]

2014-12-26 00:36:42: @jandegr commented

---

A patch to illustrate the proposed changes :

-has averaging for speed, OSM maxspeed and for roundabouts

-differentiates ramp's : motorway and trunk link still are mapped to ramp, primary secondary and tertiary link's are mapped to their corresponding street type as a temporary solution to mapping all link types to 4 new different types and the existing ramp type. The maptool patch is not mandatory to test the changes in routing, but it is advised to rebuild the map if the routing changes are used for real driving, otherewise the 3 lowest link types can experience an increase in speed.

-Requires you to change your navit.xml as in the provided sample sections. The proposed values in the xml samples are subject to further refining.

-includes a new routing mode for testing, shortest_new uses real distance as cost and can give more realistic driving time. This is just a test to see if the calculation of the cost of a route can be changed, so it might have bugs, but I made it calculate shortest route's up to 370km and no problems showed up yet

Late addidtion (not in the patch yet) : Higway=unclassified is above highway=residential, but maptool maps both to street_1_city. Street_1_land has only higway=minor as donor, which was proposed to replace unclassified outside the UK, but apparently abandoned [http://wiki.openstreetmap.org/wiki/Proposed_features/highway:minor] so I propose to change the mapping of unclassified from street_1_city to street_1_land, relates to #1245

[aerostitch]

2014-12-26 00:36:42: @jandegr

[aerostitch]

2014-12-26 00:36:42: @jandegr

[aerostitch]

2014-12-26 00:36:42: @jandegr

[aerostitch]

2014-12-26 00:36:42: @jandegr

[aerostitch]

2014-12-26 00:36:42: @jandegr

[aerostitch]

2014-12-26 00:36:42: @jandegr

[aerostitch]

2014-12-26 00:37:38: @jandegr uploaded file routing.diff (6.7 KiB)

[aerostitch]

2014-12-26 00:41:35: @jandegr uploaded file xml_sample_sections.txt (4.8 KiB)

[aerostitch]

2014-12-26 12:57:35: tryagain commented

---

Great work, jandegr!

A few questions follow.

IIRC navigation.c code has some differences processing items of type "ramp" when deciding whether to announce a given manoeuvre. Wouldn't your change break that logic?

How do you plan to do transition from current items mapping to suggested new, which will have different items for link types? I guess there's no way to do so keeping map compatible with older programs.

What if we keep map item type for any link type to be ramp, but add some distinguishing field like ramp_type=? Another way would be to keep your change ramp=>street_n_kind, but add some flag attribute to keep additional street type info. Both ways would allow us to keep compatibility with older maps/binaries with minimal distortions.

Another question, why do you change mapping of "highway=secondary,name=*" from street_3_city to street_3_land? Logic behind current is that typical city road usually has some name, while off city roads are mapped as unnamed or have ref's instead of names.

[aerostitch]

2014-12-27 03:18:28: @jandegr commented

---

thanks for the comments tryagain,

It will take several posts to answer your questions, I'll start around a case of tertiary_link. [http://www.openstreetmap.org/#map=19/-21.21070/-50.46033] [https://www.google.be/maps/@-21.2109295,-50.4603622,3a,90y,5.98h,88.61t/data=!3m4!1e1!3m2!1sWubVb7683eEe6MMFWkH9yg!2e0] Maptool now throws that in type ramp and according to navit_shipped_xml it's speed becomes 40km/h versus 30km/h of street_2_city, so the routing will like the link better than the road itself. When I switch to bike, pedestrian or horse, routing gives me a nice detour around it. Nor routing, nor the old nor the new navigation code cares about this being a link. Both the old and new navigation code would even benifit if this were not a ramp anymore. So it seems appropriate to change the mapping of tertiary_link to it's equivalent street, does not break anything and can potentially solve some 'weird routing' cases, we don't need a key signalling this is a link either. No need for a new roadtype either

A little further on that road a secondary link : [http://www.openstreetmap.org/#map=19/-21.20706/-50.44523] Makes me come a similar conclusion as for tertiary link

The case from Kazer above is primary link iirc, to investigate if we would want a key signalling this is a link. This sample makes me think we want to know it's a link : [http://www.openstreetmap.org/#map=18/-21.18552/-50.46808]

[aerostitch]

2014-12-27 03:18:28: @jandegr

[aerostitch]

2014-12-27 03:18:28: @jandegr

[aerostitch]

2014-12-27 03:18:28: @jandegr