Am 11.12.2012 um 23:46 schrieb David Piepgrass <dpiepgr...@mentoreng.com>:
>>> 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 do not think this is left out.
>
> Oh? So where in the paper does it mention the number or ratio of shortcuts to
> direct edges?
Most probably Section 8 where the data set is explained if you are talking
about the paper "Efficient Routing in Road Networks with Turn Costs". There is
also a technical report somewhere that explores the impact of edge-expansion by
Lars Volker. Forgot the name of the TR.
>>> 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).
>>
>> It is less than your estimated factor of 10. OSRM uses a so-called edge-
>> expanded representation that handles turn restrictions. It is more like a
>> factor of 2-3.
>
> That's neat... what is the "edge-expanded" representation?
Most probably the the same as what you call edge-based.
> I whipped up a demo to show what I'm talking about... I lost track of the
> original graphs that were giving me 10x ratios, but this one I just made has
> a 7x ratio.
> http://qscribble.blogspot.ca/2012/12/contraction-hierarchies.html
And what's your priority function?
>>> 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.
>>
>> If there is more than two orders of difference in the running time then I
>> suspect something is wrong with the implementation.
>
> Possibly, but other than slow flash memory and a less efficient on-disk
> layout, I couldn't find the problem. The tricky thing about CHs is that they
> can work perfectly in terms of routing, but still have some hidden flaw that
> makes them run more slowly, with no obvious way to track it down.
What is this "hidden" flaw? As Christian pointed out in his reply, the bad
performance is most probably implementation-dependent.
>>> 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.)
>>
>> 10x faster compared to what algorithm? There is also a dynamic CH query
>> that handles a number of blocked/clogged roads easily.
>
> 10x faster compared to my own CH implementation (which in turn was over 100x
> slower than the implementation made by the team that invented them.) I had
> trouble understanding how the dynamic version of CHs worked, but it appeared
> to me that there would be a substantial performance impact that I obviously
> couldn't afford, given that my implementation was already too slow (no
> performance figures had been published at the time though.)
Very unlikely that A* beats CH in general.
_______________________________________________
Routing mailing list
Routing@openstreetmap.org
http://lists.openstreetmap.org/listinfo/routing
