Penalty for uturns

[M393]

Would it be possible to add a penalty to stops where the vehicle has to turn around instead of continuing straight?
When the addresses are spread out very far it doesn't matter much, but if addresses are close by this could result in much better solutions.
See also valhalla/valhalla#5072

[jcoupey]

Currently we have no way to know whether a u-turn is happening at a given location while optimizing. Looking at the matrices we only have pair-wise costs, but deciding on whether a u-turn happens is not a pair-wise thing as it's depending on previous and next location.

For example A->B->C may result in a u-turn at B while A->B->D means continuing straight at B, all depending on location display and shortest path selection at routing level. To address that, we'd have to know that B->C has a different cost (more expensive) if coming from A.

An alternative would be to make sure matrix values are consistent with having no u-turns at waypoints by forcing the vehicle approach (approach=curb with OSRM), but that is a bit extreme as in some situations having no u-turn at all could mean very long detours.

[M393]

My thought was to provide the necessary information to VROOM with two new matrices for the start and end direction.
Though I wasn't too sure on whether it is feasible to implement this at all.

[jcoupey]

Currently whenever we need to evaluate an edge cost, we directly reach to the relevant value in the matrix. Changing this would add quite some boilerplate because you'd have to add a whole new logic to pick the "right" values depending on the context. And this kind of call is all over the place in many different contexts: building heuristic routes, evaluating gain and validity for local search moves etc.

Not saying it is not feasible, just that that would be a significant change to the codebase.