[Routing] How to Establish Road Hierarchy

[Christian Vetter]

Hi,

On Tue, Dec 11, 2012 at 8:50 PM, David Piepgrass
<dpiepgrass at mentoreng.com>wrote:

>  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).
>

>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.


>
> 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.
>

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.


>
> 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.)


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.


Best regards,

Christian Vetter
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/routing/attachments/20121211/fea8f024/attachment.html>