Navigating a road network and avoiding u-turns

Question

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?

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