1

I've implemented a node-based A* search of a road network graph.

I would like to penalize u-turns a places where bi-directional streets join together again, which I identify successfully via a match on turn angle and street name.

Although I can add penalties to u-turns by duplicating nodes and creating distinct, expensive edges for the u-turn paths, these don't have the desired effect when running a node-based search.

The result is an effect that is localized to the immediate region of the u-turn. As the node-based A* walk continues to expand outwards from the region, any inward route evaluation is prevented. The optimum route is not found. The u-turn penalty is eventually overcome and the u-turn is chosen as the best route.

I do not have this problem if I walk edges rather than nodes, as inward routes are evaluated. But edge-based walking is noticeably inefficient.

Is there a known solution to this problem? Can I keep node-based routing and penalise difficult turns?

1

You can run edge based algorithm without slow down if you allow traversal of one edge only once! This could work in your case but could lead to paths not found e.g. for situations of turn restriction detours. So maybe just use the edge based traversal with two directions (~2 time slowdown) without allowing U-turns for every junction (which would lead to a ~4 time slow down), still U-turns would be possible when there are two separate roads for both directions.

In GraphHopper you can transparently switch between those traversal modes.

  • Thank you for the link to your project. Very nice! Indeed, I am talking about avoiding u-turns where the road splits into two separate edges. From your answer I assume this means I would need to eat the 4x slowdown to avoid those. – Synesso Dec 14 '15 at 23:43
  • Sorry, this wasn't that clear. The one or two directional edged based approach (no or 2x slowdown) should be sufficient IMO. Because if there are two separate edges for the road you can avoid searching backwards which is very expensive and gives you not that much more i.e. you do not need EDGE_BASED_2DIR_UTURN – Karussell Dec 15 '15 at 12:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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