1

I've implemented a contraction-hierarchy routing system, which now works well, and I now need to add the stall-on-demand technique to speed it up; as explained here it can reduce the search space dramatically: over 25-fold in the example given.

However, I'm finding it hard to understand the few explanations I have found on the web, and the sample code given in the cited document lacks context. I'd be grateful if anyone can point me to fuller and more carefully explained examples and code.

So far I've found some code which is reasonably easy to understand in Christian Vetter's MoNav project. So that partially answers my own question. But more information, and a step by step explanation, would still be useful.

closed as too broad by PolyGeo Apr 16 '18 at 21:49

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • I believe it is already adequate, and that what I have asked for is perfectly clear. Your intervention after over three years is unhelpful. – Graham Asher Apr 21 '18 at 11:48
  • I've noticed a consistent pattern of perfectly fine and clear questions being closed as 'too broad' on gis.stackexchange.. – Open Door Logistics Mar 16 at 9:45
1

For example, in the forward search v is the current vertex.

For an in-neighbor w of v (w->v) and w>v, such that edge w->v appears in the downward graph. If d(w)+c(w,v) < d(v), then w is a better candidate than v. So we don't have to expand on v in the forward search now.

Such influence can propagate to the neighbors of v in the upward graph, using the same "d(w)+c(w,v)+[c(v,x)] < d(x)" condition. The part in [c(c,x)] can expand to deeper using BFS. However, these propagated stalled vertices can be unstalled if a shorter path to it is found.

When a vertex is stalled, you would not visit its neighbors, so the search space is reduced.

Not the answer you're looking for? Browse other questions tagged or ask your own question.