Hi,<br><br><div class="gmail_quote">On Tue, Dec 11, 2012 at 8:50 PM, David Piepgrass <span dir="ltr"><<a href="mailto:dpiepgrass@mentoreng.com" target="_blank">dpiepgrass@mentoreng.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div class="im">
</div>
The inventors of the CH wrote another brief paper ("Route Planning in Road Networks with Turn Costs") that solved the problem (in the same way I had earlier), by representing roads as pairs of nodes (one for each direction of travel) and intersections as clusters of edges (one edge per transition between roads.) Their paper on the subject leaves out the fact that the contraction hierarchy expands wildly in size when you use this representation, especially if you also model turn costs (as I did, with different costs for left and right turns). I found out (too late to change my implementation) that the CH becomes about 10x as large and contracts far, far more slowly (it's 3x bigger due to the change in representation and >3x again due to the additional shortcuts).<br>
</blockquote><div><br>From my experience with CH and turn costs, there are basically two ways to handle them, both mentioned in said paper:<br> - 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 )<br>
 - 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.<br>
 </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
So ultimately, my home-grown implementation, with its vastly larger hierarchy, was more than 100x slower than theirs. Not only was the hierarchy as a whole 10x bigger, I suspect the size increases were disproportionately in the higher levels of the hierarchy, where the routing algorithm spends most of its time. Plus my data structures re-used my existing serialization code so they weren't well optimized for CHs specifically. Plus my flash memory was really slow. Bottom line, if you're gonna use CHs, either settle for the simple kind (which will not enforce turn restrictions or represent turn costs) or figure out some hybrid approach.<br>
</blockquote><div><br>My guess is, that you overlooked some important optimization for CH, which can easily lead to a suboptimal performance. CH should really shine with slow I/O like flash memory. I've seen this many times with MoNav, testing it on a variety of devices.<br>
 </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
I would be curious to hear if someone knows how to represent turn restrictions without greatly bloating up the CH. As for me, I couldn't think of a way to support the turn restrictions, and ended up rewriting all the routing code to use a relatively simple "heuristic" hierarchical algorithm that was about 10x faster and required far less space, but still modeled turn restrictions and turn costs and cheaply allowed dynamic cost increases (e.g. temporarily prohibiting routing on ferries or gravel roads or roads with less than 9 feet of clearance, which CHs don't normally handle dynamically.)</blockquote>
<div><br>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.<br>
<br><br>Best regards,<br><br>Christian Vetter<br></div></div><br>