Hi, OSRM is using a much imrpoved version of the CH pre-processing (when compared to the original CH paper): Fully parallelized, and the heuristic for node ordering is much simpler. Since its original code was based on MoNav, you can find a description of the original implementation in [1] (it also describes efficient ways of implementing the fundamental data structures needed). MoNav itself was based on the parallelized version of Time-Dependent CH [2].
Some of OSRM's improvements upon that were described in [3] Turn costs and more complex maneuver restrictions can be handled in a complex, but compact way [4], or by modeling them into the input graph (standard expanded graph model). Overall you should be able to achieve <1ms on a map of Poland, but that highly depends on the quality of your node ordering heuristic, your witness search, stall-on-demand, and efficiency of your data structures. An easy benchmark, that disregards the efficiency of your data structures and just measures the algorithmic details, would be comparing the amount of vertices settled in the query. E.g. Poland without turn costs should most likely be < 400 or so. Best regards, Christian Vetter [1] https://code.google.com/p/monav/downloads/detail?name=thesis.pdf&can=2&q=#makechanges [2] http://algo2.iti.kit.edu/download/vetter_sa.pdf [3] http://arxiv.org/pdf/1208.2543.pdf [4] http://algo2.iti.kit.edu/download/turn_ch.pdf On Fri, Nov 21, 2014 at 8:58 AM, Alexander Chernetsky <[email protected]> wrote: > Hi, > > Currently I am working on understanding and implementation of CH algorithm. > So far I am using static graph information and iterative node contraction > (node by node). I do not have a good overview of literature on this topic > out there. OSRM is—obviously—far superior comparing to my implementation, in > terms of speed and memory requirements. Usually most good tricks and tips, > improving performance, are scattered throughout many articles. In addition I > am trying to incorporate turn costs and modeling turn restriction in CH. > > Could you please kindly point me to articles, data structures, whatever you > consider would be helpful, so that after reading—I hope—I will be able to > speed up my implementation? Currently I am stuck. It’s able to find a route > in 10ms with Poland and Belarus maps. > > Thanks in advance! > > _______________________________________________ > Routing mailing list > [email protected] > https://lists.openstreetmap.org/listinfo/routing > _______________________________________________ Routing mailing list [email protected] https://lists.openstreetmap.org/listinfo/routing
