> See here for results on a mobile implementation.
>
> http://algo2.iti.kit.edu/1264.php
>
> > I would be interested to hear how OSRM can be both simpler and
> improved at the same time.
Yeah, I've seen that. This reminds me: one should not expect anywhere near
100ms from one's own implementation, it's not realistic for a commercial-grade
product. Their optimizations were very good, plus they used a "simple"
contraction hierarchy in which nodes in the graph represent intersections and
edges in the graph represent roads. So their code was very fast but it has a
key problem: it cannot represent turn restrictions.
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).
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.
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.)
_______________________________________________
Routing mailing list
[email protected]
http://lists.openstreetmap.org/listinfo/routing
