Too strict requirements on u-turns

[purew]

In the linked route below, Valhalla fails in providing a route due to not adequately allowing for a u-turn on Quay St.
http://valhalla.github.io/demos/routing/index-internal.html#loc=19,51.455433,-2.595520&locations=[{%22lat%22:51.45552952902732,%22lon%22:-2.594244182055263},{%22lat%22:51.455145118493185,%22lon%22:-2.5958588718822284}]&costing=%22auto%22&directionsoptions={%22language%22:%22en-US%22}

Quay St, Bristol UK, converts into an outward flowing one-way street. In order to arrive at the destination, a U-turn is required on Quay st. Valhalla does not do a u-turn since that's only allowed when at a complete dead-end today.

A solution might be to allow for u-turns in more locations by relaxing the requirements in the Allowed/AllowedReverse function in sif/autocost.cc. In the case of the reverse route expansion of Quay st, in reality it actually is a dead-end due to the conversion into a one-way street.

To resolve this, the deadend flag could be expanded to differentiate between outgoing deadend via “is this node able to enter more than one outgoing edge” as well as an incoming reverse_deadend meaning “Is more than one opposing node able to enter this node”.

Another solution would be to calculate the concept of deadend and reverse_deadend at runtime which would allow for a more dynamic notion of what a deadend is. Time of day and routing profile may influence this, for example.

In the case of the Whitelion route failure, a correct reverse_deadend would mean that the reverse expanding A* would detect a deadend and make a u-turn, resulting in a route found.