[Routing] OSRM Flapping routes / non deterministic

[Dennis Luxen]

I think Christian has a real good point here. Barring any bugs in the
implementation, there are some inherent tie-breaking issues in routing.

Also, a route may flip if going ‘left’ or ‘right’ has about equal cost and
one wiggles an endpoint of the route a bit: just by moving an endpoint a
millimeter a distinct, yet almost equal-cost route may become the best.

Hope that helps,
Dennis

Christian Vetter <veaac.fdirct at gmail.com> schrieb am Di. 15. Feb. 2022 um
22:58:

> Hi,
>
> That sounds like a bug, though: Both MLD and CH are a bit
> non-deterministic, but they both should always find the "best" route, aka
> the one with the least cost (e.g. least time if you are optimizing for
> time). So it should only fluctuate from one route to the other if both are
> identical in terms of cost.
>
> Best regards,
> Christian
>
> On Tue, Feb 15, 2022 at 8:24 PM Florian Lohoff <f at zz.de> wrote:
>
>>
>> Hi,
>>
>> On Mon, Feb 07, 2022 at 11:49:04AM +0100, Florian Lohoff wrote:
>> > Hi,
>> > i am monitoring routes by calculating the very same route over and over
>> > again with newer data (OSRM). Whenever something changes i get a mail.
>> >
>> > I am currently using osrm v5.25.0-22-g73a2b9125 (Stretch does not have
>> > newer boost)
>> >
>> > Now - I have some routes which flap - Every now and then (Sometimes
>> > multiple times a day). I am experiencing this for a long time also
>> > with OSRM v5.10.0-rc.2-739-ga53da9095 which i used before.
>>
>> Okay - I think i found the issue. Using Contracted Hierarchies is non
>> deterministic. I switched to MLD and the flapping of the routes
>> disappeared.
>>
>> Flo
>> --
>> Florian Lohoff
>> f at zz.de
>>   Any sufficiently advanced technology is indistinguishable from magic.
>> _______________________________________________
>> Routing mailing list
>> Routing at openstreetmap.org
>> https://lists.openstreetmap.org/listinfo/routing
>>
> _______________________________________________
> Routing mailing list
> Routing at openstreetmap.org
> https://lists.openstreetmap.org/listinfo/routing
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/routing/attachments/20220216/2eb73fb9/attachment.htm>