Negative Durations on Demo Server / Invalid self-loop in CH alternative impl.

[MoKob]

demo-server-frontend demo-server-backend

Currently produces an assertion on the demo server:

[assert]/include/engine/guidance/assemble_steps.hpp:206
in: std::vector<osrm::engine::guidance::RouteStep> osrm::engine::guidance::assembleSteps(const osrm::engine::datafacade::BaseDataFacade&, const std::vector<osrm::engine::PathData>&, const osrm::engine::guidance::LegGeometry&, const osrm::engine::PhantomNode&, const osrm::engine::PhantomNode&, bool, bool): duration >= 0
terminate called without an active exception

The problem is within this alternative route that we find:

Which goes against a oneway (and in total finds a negative duration).

Due to the random nature of alternatives, I've not been able to reproduce this yet. For single paths it seems fine and does not discover the path against the oneway.

[daniel-j-h]

I think I figured it out why this happens.

When the phantom nodes start and end on the same segment we have to force loops in the search. We do this for the shortest path search, but we fail to do this for the alternative search.

• Here we never force loops in the alternatives search
• Here are the checks to tell if we need to force loops based on the phantom nodes

We need to reproduce the issue, though.

[daniel-j-h]

I wasn't able to reproduce this behavior so far. Which makes it a bit hard to fix.

Here's the approach I'm taking for repeatedly generate contraction orders and then see if routed asserts.

#!/usr/bin/env bash

set -o errexit
set -o pipefail
set -o nounset

wget http://download.geofabrik.de/asia/vietnam-latest.osm.pbf
osmium extract --bbox 105.4632568359375,20.684183779352395,106.27349853515625,21.496519114833735 vietnam-latest.osm.pbf -o hanoi.osm.pbf
./osrm-extract -p ../profiles/car.lua hanoi.osm.pbf

while true; do
    ./osrm-contract hanoi.osrm > /dev/null

    ./osrm-routed hanoi.osrm &
    sleep 0.1
    curl 'http://localhost:5000/route/v1/driving/105.86564000000001,21.008730000000003;105.86486518965302,21.008315070735108?overview=false&alternatives=true&steps=true' | jq '.routes'
    pkill osrm-routed

done

[TheMarex]

@daniel-j-h maybe try putting osrm-extract in the loop as well: There might be some non-determinism introduced by the initial parsing/sorting.

[daniel-j-h]

Still can't trigger and reproduce after running it for hours.

(note: osrm-routed needs to be compiled with assertions on)

[miccolis]

Stale ticket. If anyone has seen this recently please re-open.

[daniel-j-h]

Negative durations with loops in the CH alternatives impl. is still an issue.