mraross
commented
4 years ago From email received from Chris hodgson on Tuesday, April 28, 2020 at 3:40 PM :
The problem was caused by a single destination point - Stikine Health Center, which is on "Stikine Health Ctr Road" which is a small lollipop of the side of Cassiar Hwy (#37). The logic that stops the router from revisiting segments it has already visited specifically allowed for re-visiting end edges, because it may be possible to visit them from opposite ends. Also, after you reach an end edge, the router keeps walking (because there might be another end edge further along the same path - because we are doing multi-destination routing). But because this end edge is a loop, it is able to keep walking around and revisiting the same edge. Normally the router would stop after it reached the destination, however in the same multi-destination query is also one more unreachable destinations. So the router keeps looping around the stikine health center rd hoping to find the way to the as yet unreached destination(s).
However, since we switched to directed edges, it is no longer necessary to allow for revisiting end edges, which easily solves this problem. I have also added a loop limit to prevent infinite loops in case there is some other special case that can somehow cause this. It will now log an error instead of looping more than twice the number of edges in the graph, and it takes less than 2 seconds to reach this limit. We have to allow for visiting more edges than are in the graph because segments internal to turn restrictions need to be revisitable (until we change the intersection routing logic)
Surfaced by ACDF (see https://github.com/bcgov/ols-router/issues/277 )
Caused by router unable to handle a single edge loop like Stikine Health Ctr Road.
https://router-dev.pathfinder.gov.bc.ca/distance/betweenPairs.html?criteria=shortest&fromPoints=-130.028686,57.873974&toPoints=-129.991822,58.44173,-122.94362,49.14599