Take the 2-minute tour ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer

up vote 1 down vote accepted

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

  1. Enable postp.2.class=de.cm.osm2po.converter.MlgBuilder (config)
  2. Enable graph.support.extensions=true (config)
  3. Run osm2po with at least (cmd=gp)
  4. Enable one or more MlgRouters (config)
  5. 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.

share|improve this answer
    
ok, it looks like this router is reasonable to use for routing between different cities and for long distances. But would be any performance degradation in case if MlgRouter will be used for small distances inside one city? (I mean on run time not on precalculation time) –  Andrew Apr 22 '13 at 21:37
    
You are right. It doesn't make sense to use such a technique for short distances. Here a normal Dijkstra or AStar should be sufficient. –  Carsten Apr 23 '13 at 17:01
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.