Contraction hierarchies

A "normal" or "simple" graph: each edge is a road, each node is an intersection.

"

A "edge-based" (road-centric) graph: each node represents one direction of travel on a road, each edge is a transition between roads. (Here, U-turns are permitted with a large cost penalty).

The advantage of this representation is that turn costs and turn restrictions can be represented in the graph.

An edge-based graph, by itself, typically has about 2.5 times as many nodes, and 3 times as many edges as a simple graph (according to the paper "Route Planning in Road Networks with Turn Costs" by Lars Volker.) In this particular graph there are 2.59 times as many nodes and 3.5 times as many edges in the turn-based graph. Which is all fine and expected.

When contracted, the CH for a normal graph has about the same number of shortcuts as edges (353 shortcuts to 378 edges):

However, when the turn-based version of this particular graph is contracted, it has 2548 shortcuts, which is 7.2 times as many shortcuts as the normal CH had; so overall there are 5.3 times as many edges, but the 7.2 figure is more important because the routing algorithm spends most of its time following shortcuts, not direct edges:
This graph is just a demo; in large-scale road networks, my algorithm produced about 10 times as many shortcuts in the complex graph as the same algorithm would have produced in the simple graph.

It's possible that there was something wrong with my algorithm. But I was not able to track down what, if anything, was the flaw in my implementation, because as you can see, the contracted form of an edge-based graph is rather hard to follow. My contraction algorithm appeared to work well in the simple graph, so there is no apparent reason why the same algorithm would work poorly in the complex graph.

Another cautionary note for interpreting CH performance: the number of nodes settled in a CH cannot be used directly as a performance metric to compare with a Dijkstra search in a normal road network. The reason is that the cost of settling a single node is variable and depends on the fan-out of the node. CH nodes can have very large fan-outs in high levels of the hierarchy; therefore, settling a single node in a CH is vastly more costly than settling a single node in a normal road network (I don't have numbers handy tho, sorry.)

EDIT: Here's another graph in which the phenomenon is much worse. The simple graph requires 219 direct edges and 140 shortcuts, while the edge-based graph has 1323 direct edges and 1756 shortcuts (12.5x as many). An example route is shown in both graphs (from the bright green dot to the bright red dot).




Why is the difference so large? I think it's because I enabled U-turn edges for this second graph. Note that in the simple graph, it's impossible to eliminate U-turns or increase the penalty for taking them, but in the edge-based graph there is a significant cost for including the ability to U-turn, even if the cost is high. I went back and enabled U-turns on the first graph and my demo program crashed--oops, no time to debug it now.

Coefficients used for these CHs: Edge difference 10, S.S. Depth upper bound 6, Deleted neigbors 3, Shortcut cost multiplier 1, Hop limit 5.