Unusual routing decision

[scaidermern]

Issue forwarded from https://help.openstreetmap.org/questions/61189/unusual-routing-decision

Expected behavior:
https://www.openstreetmap.org/directions?engine=osrm_car&route=50.85216%2C-1.16498%3B50.85311%2C-1.16852#map=18/50.85265/-1.16674

Unexpected behavior:
https://www.openstreetmap.org/directions?engine=osrm_car&route=50.85217%2C-1.16484%3B50.85311%2C-1.16852#map=18/50.85265/-1.16674

The starting position in the second case is only slightly altered and includes an additional traffic signal. It leads however to a completely different route which is 6.9km long (time: 0:11) instead of only 276m (time: 0:03).

Other routing engines (GraphHopper, Mapzen) don't show this behavior.

The map data seems to be fine. Routing across the traffic signal is not an option and works perfectly:
https://www.openstreetmap.org/directions?engine=osrm_car&route=50.85217%2C-1.16484%3B50.85232%2C-1.16560#map=18/50.85265/-1.16674

[daniel-j-h]

Here's the router's response for the first request:

curl 'https://router.project-osrm.org/route/v1/driving/-1.16498,50.85216;-1.16852,50.85311' | jq '.routes[0] | {weight: .weight, duration: .duration, distance: .distance}'

{
  "weight": 912.2,
  "duration": 178.5,
  "distance": 275.5
}

And here is the response for the second query

curl 'https://router.project-osrm.org/route/v1/driving/-1.16484,50.85217;-1.16852,50.85311' | jq '.routes[0] | {weight: .weight, duration: .duration, distance: .distance}'

{
  "weight": 886.3,
  "duration": 638.2,
  "distance": 6862.3
}

For some reason the route's weight we optimize for is smaller for the second route, even though duration and distance are higher. I quickly skimmed the data but couldn't find anything suspicious.

Traffic signals change duration here:

osrm-backend/src/extractor/edge_based_graph_factory.cpp

Lines 578 to 597 in 84b6ef4

	// compute weight and duration penalties
	auto is_traffic_light = m_traffic_lights.count(node_at_center_of_intersection);
	ExtractionTurn extracted_turn(
	turn.angle,
	m_node_based_graph.GetOutDegree(node_at_center_of_intersection),
	turn.instruction.direction_modifier == guidance::DirectionModifier::UTurn,
	is_traffic_light,
	edge_data1.flags.restricted,
	edge_data2.flags.restricted,
	m_edge_based_node_container.GetAnnotation(edge_data1.annotation_data)
	.is_left_hand_driving,
	m_edge_based_node_container.GetAnnotation(edge_data1.annotation_data).travel_mode,
	m_edge_based_node_container.GetAnnotation(edge_data2.annotation_data).travel_mode);
	scripting_environment.ProcessTurn(extracted_turn);
	// turn penalties are limited to [-2^15, 2^15) which roughly
	// translates to 54 minutes and fits signed 16bit deci-seconds
	auto weight_penalty =
	boost::numeric_cast<TurnPenalty>(extracted_turn.weight * weight_multiplier);
	auto duration_penalty = boost::numeric_cast<TurnPenalty>(extracted_turn.duration * 10.);

osrm-backend/profiles/car.lua

Lines 426 to 428 in 84b6ef4

	if turn.has_traffic_light then
	turn.duration = profile.properties.traffic_light_penalty
	end

[scaidermern]

Shouldn't a traffic light penalty lead to a higher duration? The duration of the second query is higher than the first one. So this can't be caused by traffic light penalties, can it?

Nah, this didn't make any sense. The higher duration is mainly caused by a longer route.

However even though the second case avoids this particular traffic light it has to pass another one at https://www.openstreetmap.org/?mlat=50.85119&mlon=-1.15675#map=18/50.85119/-1.15675 Still it results in a lowered weight.

[TheMarex]

I found the origin of this problem that is the result of an invalidly applied U-Turn penalty. This is amplified by the fact that the demo sever uses 60 seconds for the U-Turn penalty, as opposed to 20 seconds like the stock profile. A fix for this is in #4755 and will be shipped with the next bug fix release.

[oxidase]

Fixed in v5.14.3