>From my experience with CH and turn costs, there are basically two ways to >handle them, both mentioned in said paper: > - Use an unpacked representation, two vertices per street, and each junction >a set of >edges. This blows up the CH space consumption and query speed by a factor of 3 >( tested >with MoNav, OSRM on OSM data, and also on Navteq data, using a large variety >of >different turn costs ) > - Use the specialised variant from that paper, which has a turn cost matrix >per junction, >but needs special coding in the CH do handle it properly. This makes >preprocessing and >query speed slower by a factor 3, but does not require much >more size than the simple >variant. However, it is not trivial to implement it properly.
My implementation required only one byte per direct edge (and 48+ bits for each shortcut edge), so it wasn't fully unpacked; it grouped all edges by node, and grouped all nodes together with the intersection that they leave, which enabled some space optimization. Unfortunately, once it became clear that my implementation was too slow, I also realized that the exact form of "topological sorting" described in the paper was not possible in my implementation. I did implement a topological sort, but it was limited by my data structure, which was structurally constrained to hold all nodes of an intersection in the same disk block. So for the purpose of sorting, I treated intersections as if they were big nodes (or something like that... it was a long time ago now.) I guess I am an object lesson in what happens if you don't do CHs exactly right. I paid for my mistakes dearly (whatever they were), having to abandon my implementation in the end. A flawed CH implementation can be far, far slower than a simpler hierarchical algorithm. I'd recommend anyone using CHs to just use as much of one of these GPL/AGPL implementations as possible. I didn't use the GPL implementation because my company likes closed source, but in hindsight, it should have occurred to me that I didn't have to open-source the entire mapping product, in fact I could have even used the GPL contraction algorithm "as-is" and postprocessed the output into the proprietary format. Oh well. I feel dumb now. >In my experience an A* has can seldom outperform CH, especially on mobile >devices. >Even more so, if your routing graph does not fit into memory entirely, and >you'd like to >handle graphs larger than a city. Also a heuristic hierarchical algorithm can >give you really >subobtimal routing results, leading to bad user experience. Yes. My CH implementation replaced a unidirectional A* implementation and it was a lot faster, overall, at long-distance routing. A footnote though: from a users' perspective it did not seem faster, because my A* code provided an initial "guess route" to the user within 5 seconds, so they could start driving (it didn't work correctly if the final route had to go around a large body of water, but we had no customers in that circumstance.) A CH cannot provide any directions until the route unpacking stage begins, which in my case took up to 20 seconds to reach. My heuristic algorithm works very well though, I haven't seen a bad route from it yet. _______________________________________________ Routing mailing list Routing@openstreetmap.org http://lists.openstreetmap.org/listinfo/routing
