Arrive-by search returns no results when we know there are valid ones

[demory]

The following arrive-by search from Portland works as expected, returning a valid transit itinerary whose last leg arrives exactly 30 minutes ahead of the specified arrival time of 11:14pm:

http://maps7.trimet.org/ui_prod/?module=planner&fromPlace=2705+NE+ARGYLE+ST%2C+PORTLAND%3A%3A45.576992%2C-122.63753&toPlace=SE+Powell+Blvd+%26+SE+136th+Ave%2C+Portland%3A%3A45.497856%2C-122.523544&time=11:14pm&date=02-16-2017&mode=TRANSIT%2CWALK&maxWalkDistance=804.672&arriveBy=true&wheelchair=false&locale=en

However, if you bump the arrival time from 11:14 to 11:15pm, no results are found. This makes no sense; at minimum the same itinerary from the 11:14 search should be valid here, just with 31 idle minutes at the end instead of 30. (Note that results are returned, with a different itinerary, if the walk limit is increased.)

When we discussed last week, @mattwigway wondered if a 30 minute cutoff was being applied to to the "wait" time for the first vehicle (this is a reverse search, so that wait is after the vehicle drops the rider off). This would explain the above behavior, but I haven't been able to locate any such cutoff in the code. @abyrd curious if you have any insight.

[abyrd]

I tried @hannesj's patch from #2411 in case these are related but no luck, after deleting all the turn cost code the routing still fails at 11:15pm. It is noticeable though that this problem is very sensitive to the walk distance limit (which is set to 0.5mi). The search fails at 11:15pm with walk limits of 0.50, 0.51, 0.52, 0.53, 0.54, but starts working at 0.55. With this higher walk limit, it is noticeable that the router finds a solution at 11:14pm whose first step is walking south to stop 8499 (NE Columbia Blvd & 29th) but one minute later at 11:15pm, the router finds a solution whose first step is walking west to stop 118 (NE 21st & Argyle). Other than this first walking step, and the fact that one uses an earlier bus, the two itineraries are identical. Why would the router walk over 0.5 miles to reach stop 118? It takes less walking (under 0.5 miles) to reach stop 8499 which is farther along the route (closer to the destination).

[abyrd]

This is (no surprise) related to the bidirectional remaining weight heuristic. If I disable the heuristic the results look correct. With the heuristic enabled, the search never even reaches the origin point.

[abyrd]

In fact it's only related to the heuristic because the heuristic imposes the walk limit.

I think I've got the real source of the problem narrowed down to StreetTransitLink L91/L92:

// Do not re-enter the street network following a transfer.
// FIXME this is a serious problem: transfer result state can dominate arrivals at a stop on a vehicle and prune the tree!

The search transfers from stop 1290 (NE Dekum & 33rd) to stop 8499 (NE Columbia Blvd & 29th, the best stop from which to walk to the destination) and the result of that transfer remains the dominant state at this transit stop. But re-entering the street network after a transfer is not allowed.

This kind of traversal-cancellation based on the type of a backEdge is algorithmically invalid and must be removed anywhere it occurs in OTP.

In this case, the result of state a SimpleTransfer must not be saved at the TransitStop vertex (since that vertex must be passed through when exiting transit). We must take the next step of traversing the PreBoardEdge without saving the intermediate state in the tree. Another way to say this is that a SimpleTransfer should lead directly to a _depart vertex rather than the stop vertex associated with the _depart vertex. But how can this be made to work in both directions? Another solution is to make states that are the results of traversing a SimpleTransfer incomparable with other states.

SimpleTransfer L58 has a comment that claims to be another manifestation of the same problem, but I think that there, it's OK for arrival at a stop by walking to dominate transfer results.