Facts about: Leveling
Posted: Mon Oct 05, 2020 8:09 am
HI there,
as some of you may have noticed our routing engine provides a set of parameters which influence the so-called leveling (abbreviated as "L." in this article). Let me give you more insights into what the motivation of L. is and also about when to use it and when not... Most developers/users won't have to touch this but in some rare cases it makes sense.
What is LEVELLING?
In fact L. is a very simple strategy which is applied to achieve a better routing performance with an acceptable loss of precision: Imagine you want to drive from A-street in the inner city of A-town to the B-street in the inner city of B-town with A-town and B-town being located far away from each other, hundreds oreven thousands of kilometers. What is the first thing you'd do when you route from A to B? You try to reach some upper roads such as highways or country roads, then you travel on these roads until you reached the area of B-town and there you try to find your final way to B-street. This is what a L. algorithm does, too: by filtering all minor roads which are far away from any involved wayopint the total number of segments that have to be evaluated by the algorithm is reduced significantly though in most cases this change from "exact" data to "heuristic" data has no relevant impact on the quality of a route. It is seen as an exception if a route can't be found due to L. or if the "optimal" route (considering ALL network classes) is much "better" than the route returned after L.
What are the side-effects?
Bernd
as some of you may have noticed our routing engine provides a set of parameters which influence the so-called leveling (abbreviated as "L." in this article). Let me give you more insights into what the motivation of L. is and also about when to use it and when not... Most developers/users won't have to touch this but in some rare cases it makes sense.
What is LEVELLING?
In fact L. is a very simple strategy which is applied to achieve a better routing performance with an acceptable loss of precision: Imagine you want to drive from A-street in the inner city of A-town to the B-street in the inner city of B-town with A-town and B-town being located far away from each other, hundreds oreven thousands of kilometers. What is the first thing you'd do when you route from A to B? You try to reach some upper roads such as highways or country roads, then you travel on these roads until you reached the area of B-town and there you try to find your final way to B-street. This is what a L. algorithm does, too: by filtering all minor roads which are far away from any involved wayopint the total number of segments that have to be evaluated by the algorithm is reduced significantly though in most cases this change from "exact" data to "heuristic" data has no relevant impact on the quality of a route. It is seen as an exception if a route can't be found due to L. or if the "optimal" route (considering ALL network classes) is much "better" than the route returned after L.
- red - road belongs to minor network
green - road belongs to major network
Route through A to somewhere "far away": not possible because the major network can't be reached in the scope of red.
Route through B to somewhere "far away": not possible. Though the red scope contains red AND green roads they are not connected inside the close area.
Route through C to "far away" - possible if not ruined due to other waypoint's scope
Route through D to "far away" - possible if not ruined due to other waypoint's scope
- From a performance point of view L. changes the runtime: by increasing the scope of a network class you would increase the total number of segments to be evaluated - decreasing the scope means to reduce the total number of segments and therefore could have positive effect. The price you pay for this is the precision of the output.
- Decreasing the scope of a minor NC could also lead to "route not found" exceptions in cases where the nearest major roads are too far away from at least one waypoint.
- On the other hand we sometimes recommend to change the default settings for L. if the geographic region you are dealing has a sparse street network (because it is sparse in reality or because you have installed a surficial map such as a transit map).
-
HIGH PERFORMANCE ROUTING does not apply L. because the creation of the required search graphs always considers the complete network. Therefore besides the incredible speedup of a HPR based matrix routing the second benefit is the precision of HPRs output: HPR is an EXACT algorithm (while CONVENTIONAL with LEVELING is a HEURISTIC). - Unfortunately there's another side effect in CONVENTIONAL routing with distance matrices... As this approach is based on the temporary data structures and also on [1:N] partial routings the "sequence of creation and updating" matrices may cause different traveltimes/distances even with two conventional matrices containing the same set of waypoints: The following two transaction sequences will create a 4² matrix but can lead to such gaps...
- createDistanceMatrix([A,B,C,D]x[A,B,C,D])
- createDistanceMatrix([A,B]x[A,B]) + updateDistanceMatrix([C,D]x[C,D])
- L. is a technical mechanism, not a functional one: Usually a regular user is not expected to know what L. is. Though the end user of an application is familiar with mechanisms such as Truck Attributes, the difference of speed values or Toll features I wouldn't suppose him to understand technical mechanisms such as what is L., A* routing, Linking... Therefore choose wisely whether you want to forward L. properties to the frontend or not.
- But you could apply an iterative approach such as "try to find a route with the default L settings. If you encounter a "route not found" message you could increase the scope and try it again. If your routings are running into the second case too often change the defaut settings.
Bernd