in the new osm2po v4.7.7 release notes I see that there is new MlgRouter (MultiLevelGridRouter) "which is an at least five times faster DefaultRouter". Could someone clarify why it's so fast (what assumptions/concept cause such dramatic speedup? what is the main idea of Multi Level Grid?) and for what cases it's applicable/recommended to use?
Answer
There are many (even optimal) speed-up-techniques for goal directed routing. One very prominent candidate is the AStar-Algo which uses heuristics based on geographic informations. Another one is the MultiLevel-Routing which bases on precalculated highway levels. The precalculation step detects low and high level roads and the routing algo can ignore low level streets in the middle of the path. One of the best algos of this class is the CH used by OSRM or MoNav. The disadvantage is the memory overhead and a very long precalculating time. Hence osm2po uses a very simple technique which doesn't hurt the memory and the runtime too much. Another disadvantage is that one precalculated set of levels only fits to exactly one use case. "fastest-path" e.g. would be one, "shortest-path" another.
In order to enable this feature, read the comments/hints in osm2po.config. All you have to to is
- Enable postp.2.class=de.cm.osm2po.converter.MlgBuilder (config)
- Enable graph.support.extensions=true (config)
- Run osm2po with at least (cmd=gp)
- Enable one or more MlgRouters (config)
- Open the WebTestUI
Tipp: Test it with a medium sized country, Spain eg. and you'll see the difference between the DefaultRouter and the MlgRouter.
No comments:
Post a Comment