Usage of negative turn penalties

[oxidase]

Some tests in OSRM make turn penalties updates with negative value. This introduces incorrect behavior in snapping start points and may lead to quite non-obvious problems like #3647 and #3641.
Practically, negative turn penalties would make turns more preferable instead of going straight with 0 turn penalty. This can be achieved also by using a positive bias value and making all turn weight penalties positive. Duration values are not used as key values in heaps and can be negative.

• clarify domain of turn penalties
• review tests features/car/traffic_turn_penalties.feature and features/testbot/traffic_turn_penalties.feature
• adjust updates

  osrm-backend/src/contractor/contractor.cpp

  Lines 832 to 841 in 005124f

  	if (turn_weight_penalty + new_weight < weight_min_value)
  	{
  	util::Log(logWARNING) << "turn penalty " << turn_weight_penalty << " for turn "
  	<< turn_index.from_id << ", " << turn_index.via_id << ", "
  	<< turn_index.to_id
  	<< " is too negative: clamping turn weight to "
  	<< weight_min_value;
  	turn_weight_penalty = weight_min_value - new_weight;
  	}

• add non-negativity check of weights at

  osrm-backend/src/contractor/contractor.cpp

  Lines 460 to 467 in 005124f

  	auto segment_speed_lookup = CSVFilesParser<Segment, SpeedSource>(
  	1, qi::ulong_long >> ',' >> qi::ulong_long, qi::uint_ >> -(',' >> qi::double_))(
  	config.segment_speed_lookup_paths);
  	auto turn_penalty_lookup = CSVFilesParser<Turn, PenaltySource>(
  	1 + config.segment_speed_lookup_paths.size(),
  	qi::ulong_long >> ',' >> qi::ulong_long >> ',' >> qi::ulong_long,
  	qi::double_ >> -(',' >> qi::double_))(config.turn_penalty_lookup_paths);

• add at

  osrm-backend/src/engine/routing_algorithms/routing_base.cpp

  Line 112 in 005124f

  const EdgeWeight to_weight = weight + edge_weight;

  assertion that to_weight >= 0

/cc @danpat

[danpat]

I think that we should allow for negative turn penalty values.

Consider a simple intersection where most of the traffic is not taking the straight maneuver - 25% of the traffic volume goes straight, 75% makes the right-hand turn:

Let's say we have samples of all cars passing the "Average speed" measurement point. It's likely that the average speed is biased towards cars making the turning maneuver.

In this case, it would make sense for the 25% straight through traffic to receive a "negative turn penalty" - it's faster than average to proceed straight.

Of course, the validity of this idea depends on these biases existing. If the speed approaching the intersection is the average of the vehicles making the fastest maneuver, then all penalties can be positive for the same effect, and the fastest maneuver would have a penalty of 0.

[github-actions]

This issue seems to be stale. It will be closed in 30 days if no further activity occurs.