Opened 3 years ago

Last modified 3 years ago

#1279 new defect/bug

Routing : some problems analyzed

Reported by: jandegr Owned by: Singesang
Priority: major Milestone: version 1.0
Component: osd/core Version: git master
Severity: normal Keywords:
Cc:

Description

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

Attachments (6)

Screen Shot 2014-12-23 at 2.21.03 PM.png (53.9 KB) - added by kazer 3 years ago.
routing issue example for #1279
Capture.JPG (77.4 KB) - added by jandegr 3 years ago.
first sample for #1276
Capture2.JPG (76.0 KB) - added by jandegr 3 years ago.
second sample for #1279
routing.diff (6.7 KB) - added by jandegr 3 years ago.
xml_sample_sections.txt (4.8 KB) - added by jandegr 3 years ago.
routing2.diff (14.9 KB) - added by jandegr 3 years ago.

Download all attachments as: .zip

Change History (20)

comment:1 Changed 3 years ago by jandegr

First sample : 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'

Last edited 3 years ago by jandegr (previous) (diff)

comment:2 Changed 3 years ago by jandegr

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.

Last edited 3 years ago by jandegr (previous) (diff)

comment:3 Changed 3 years ago by jandegr

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.

Last edited 3 years ago by jandegr (previous) (diff)

comment:4 Changed 3 years ago by jandegr

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 * 80 = 72 for the first case without maxspeed and speed_used = 120 * 80 = 96 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. 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 https://dl.dropboxusercontent.com/u/93775123/Navit/routing/Capture4.JPG

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

Last edited 3 years ago by jandegr (previous) (diff)

Changed 3 years ago by kazer

routing issue example for #1279

comment:5 Changed 3 years ago by kazer

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

routing issue example for #1279

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

Jan, does your patch address this example too?

Thanks!

comment:6 Changed 3 years ago by jandegr

Like this ? 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

Last edited 3 years ago by jandegr (previous) (diff)

Changed 3 years ago by jandegr

first sample for #1276

Changed 3 years ago by jandegr

second sample for #1279

comment:7 Changed 3 years ago by jandegr

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

Last edited 3 years ago by jandegr (previous) (diff)

Changed 3 years ago by jandegr

Changed 3 years ago by jandegr

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

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=<one of item_street_ type codes>? 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.

comment:9 Changed 3 years ago by jandegr

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

Last edited 3 years ago by jandegr (previous) (diff)

comment:10 in reply to: ↑ 8 Changed 3 years ago by jandegr

Replying to https://wiki.navit-project.org/index.php/user:tryagain:

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.

In Belgium every road from primary down to residential has a name, so in the old situation they were all downgraded to 'city' but roundabouts in most cases don't have a streetname, and there the route was suddenly upgraded to 'land'. My changes did not really solve it, since it now upgrades a lot of 'city' roads to 'land'. EDIT : In the Netherlands it also seems that if a primary secondary or teriary road does not have a name in OSM that is due to mappers neglect and I only found very few cases.

It looks like the solution is to reduce the difference in speed between 'city' and their 'land' counterparts and hope there are many OSM_maxspeed tags, so I will revert that whenever I post a new version of the patch.

Last edited 3 years ago by jandegr (previous) (diff)

comment:11 follow-up: Changed 3 years ago by jandegr

I am testing maps with a new AF_LINK flag now, there are no new roadtypes introduced. This seems so far to be the best approach and does not break compatibility with old binaries. Any OSM link type road now gets assigned an AF_LINK flag in maptool. Pirmary_link, secondary_link and tertiary_link now map to the same Navit streettype as primary, secondary and tertiary, but receive the AF_LINK flag. Those are now rendered in the same colour as the road they lead to, they used to be all in the same 'ramp' colour. Also solves the problem that the motorway access restrictions are applied to any OSM link type (see the samples in comment 9) Trunk_link and motorway_link receive the AF_LINK flag as well, but in a transitional period of say six months, trunk_link still map to the old Navit 'ramp' type for the sake of the old binaries.

New navigation code is to be modified so it can handle both the old ramp type and the future situation where trunk_link will eventually be mapped into it's respective trunk roadtype as primary, secondary and tertiary would be from the start.

motorway_link is to be mapped to 'ramp' forever, it gives even more control over routing, map rendering is not affected and compatibility with old binaries remains even after trunk_link maps to street_n_lanes with AF_LINK.

I also have a new modifier in navit.xml now as well, link_weight works in the same way for route.c as roundabout_weight already did.

some samples :

<roadprofile item_types="street_3_land" speed="70" route_weight="90" 
roundabout_weight="75" link_weight="90"/>
<roadprofile item_types="street_n_lanes" speed="100" link_weight="90"/>

As before, xml provides a default speed to replace missing OSM maxspeed, the modifiers route_wieght, roundabout_weight and link_weight are applied by route.c to the default xml speed or the OSM maxspeed alike. roundabout_weight and link_weight are applied cummulative on to route_weight but not on to each other, if there is AF_ROUNDABOUT and roundabout_weight, then link_weight is ignored in case there also is an AF_LINK.

in maptool I now have a few lines like :

"w     highway=tertiary_link	street_2_city,AF_LINK\n" /*was ramp*/

Only remaining issue is the city/land logic based on the presence of a name attr. There must have been a point in time or still regions where that works, for many regions today it simply introduces some randomness.

Last edited 3 years ago by jandegr (previous) (diff)

comment:12 in reply to: ↑ 11 Changed 3 years ago by tryagain

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

I am testing maps with a new AF_LINK flag now, there are no new roadtypes introduced. This seems so far to be the best approach and does not break compatibility with old binaries.

Agreed.

Only remaining issue is the city/land logic based on the presence of a name attr. There must have been a point in time or still regions where that works, for many regions today it simply introduces some randomness.

It worked great for me in Russia and Ukrain, suggesting to go around the city instead of crossing it, and i've not seen too much maxspeed tags in these countries. And out of city roads have no names there.

I guess we will have to introduce country boundary information into the map at some point for purposes besides simply drawing it on the map. OSM rules vary from country to country, and that differences actually make sense.

For countries mapped like Russia, we still could use named/unnamed property of road. Some others (Belgium, Netherlands) have most city roads tagged with maxspeed, but outside roads untagged. It won't be a surprise to have countries in which we will have to use some other logic.

comment:13 Changed 3 years ago by jandegr

Hi, an updated version (routing2.diff), introducing route_graph_flood_frugal(), once a path is found it only searches for paths with a lesser cost. On a test route from the center of Paris to the center of Amsterdam the number of edges visited drop from 480775 to 324230 or a decrease of roughly 30% On short testroutes a decrease of over 90% was observed. This compensates for the extra work done to process the new speed modifiers and will probably even result in an overall speed increase in route calculation, so I have a little slack for when I start to not let it route over gates, bollards and other such road blockers.

Further testing of the earlier changes went very well and is now focused on refining the values in the XML for optimal routing.

The named/unnamed issue is not changed in maptool but is dealt with by assigning the same values for the named and their unnamed type in XML for regions where this logic does not make sense. This does not break anything for regions where this logic does make sense. We only need a region-specific XML but I came to the conclusion that a 'one XML is good for the entire world' is an illusion for any version of the code anyway.

regards, Jan

Last edited 3 years ago by jandegr (previous) (diff)

Changed 3 years ago by jandegr

comment:14 Changed 3 years ago by tryagain

jandegr, do you know actual performance results from these changes?

I'm afraid this won't actually give much results, because of preceeding steps cost. But your change seems to force navit to rebuild whole route from scratch almost each time you make a small detour. Currently navit has whole route graph, and can build new route fast, without touching binfile at all.

And I do not agree that one xml for entire world is impossible. We just have to add more intellect to maptool, at least let navit way to know in which country it's building the rouite.

tryagain.

Note: See TracTickets for help on using tickets.