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?
أكثر...
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?
أكثر...