[Routing] How to Establish Road Hierarchy

[David Piepgrass]

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

That's the one. I don't see anything about the number of shortcuts in edge-based vs node-based graphs, in section 8 or elsewhere.

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

It's been awhile now... hmm. Okay, the overall formula was

Order = (Shortcuts - BackLinks) * EdgeDifferenceCoeff
       + DeletedNeighbors * DeletedNeighborsCoeff
       + DepthUpperBound  * SearchSpaceDepthCoeff

with

EdgeDifferenceCoeff = 10; // but each shortcut counts as 4 because 
                           // shortcuts use more space in the file
SearchSpaceDepthCoeff = 20; // "Q"
DeletedNeighborsCoeff = 20; // "D"
HopLimit = 2; // The limit is tripled for the actual contraction process
SettledNodesLimit = 200; // The limit is eliminated for the actual contraction process.

But now the code reminds me that it always contracts nodes in groups--full node groups at once. A node group is the set of nodes that exit a given intersection, and its priority is the average among the nodes of the group. It's possible this was the problem, but a demo app I wrote was not limited by this constraint and it still produced a 10:1 shortcut ratio between complex edge-based graphs and simple graphs.

I tried tweaking the parameters of the priority function of course, and I never got significantly better results than with the parameters above. The HopLimit is quite low because the simulated Dijkstra searches were very expensive; decreasing from the original value of 5 only made the CH moderately bigger, though I noted that "a hop limit of 3 produces a smaller CH though, and may be advisable for large maps (more testing is needed)."

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

How can I answer your question? Assuming my code was flawed, if I knew what the flaw was, I would have fixed it. I never found the exact reasons why my implementation was slower than the one described in the paper (of course, I didn't have their implementation to compare with.) A lot of nodes are settled in my implementation, but Volker's paper doesn't say how many nodes are settled on average in their testing of edge-based graphs, so I couldn't be sure whether I was settling too many or whether it was "par" for edge-based graphs.

My point, based on personal experience, is that a CH implementation could have some flaw that is very hard to track down. I got my algorithm to work perfectly (i.e. optimal routes), and I implemented stall-on-demand, topological sorting and other optimizations, but still it was too slow.
 
> Very unlikely that A* beats CH in general.
It certainly doesn't.