OTP unable to utilize some stops for boarding or alighting

[grant-humphries]

This issue was detected through testing suite that we run at TriMet each time we rebuild our graph (the suite runs a few hundred trips automatically and expects certain stops, ways, etc. to be a part of each trip, if those features aren't along a trip's route it is flagged). The problem that is occurring is that the router is unable to use some stops for either boarding or alighting (but not both in any of the examples I've found). This is leading to weird behavior such as passing a west bound stop near the destination, getting off at the next stop, heading back the other way and alighting at the east bound stop

Here are links to trips I've found that seem to be experiencing this bug:

Sunset Transit Center 1

Sunset Transit Center 2

Rose Quarter MAX (And here's what the Rose Quarter MAX trip should look like)

The Zoo

An optimal trip with these end points would alight the MAX at stop 8346

[abyrd]

Now looking into errors at http://maps5.trimet.org/otp_osm_report.html

I can reproduce these problems, but all seem to be cases where the "correct" route includes more than the requested amount of walking, and the "weird" route is produced due to walk limiting.

It is possible in all cases to get the expected/"good" route by increasing the walk distance parameter. This implies a problem with state dominance calculations or walk limit raising.

[abyrd]

I have tried again to reproduce these with maps5 and locally. Update: Both locally and on maps5, I don't see any problem with searches 1-3. The last example says that the correct result should alight the MAX at stop 8346, and both maps5 and my local instance do alight at that stop. Any chance this behavior is due to the aforementioned April 5 pull?

Trip 4 "the Zoo" is indeed an insane route related to walk limiting. There is another problem where the start point in the final result seems to have teleported to the location of the first stop (possible reverse optimization bug). Studying this one more.

@fpurcell, what would you think of replacing distance-based walk limiting with a simple switch that makes walking "cost" much more, maybe in 3 increments (I like walking, normal, avoid walking)?

[fpurcell]

Hey Andrew...I don't want to change to 3 increments as a workaround (I can't make such a change to the user experience w/out involving others, etc...). I might bump the default walk to 3/4 or 1 mile, but that's a band-aide.

[fpurcell]

BTW, the Zoo trip is indeed a very strange result (w/the 1/2 mile walk setting), and the teleportation we're seeing here has me convinced it is a bug in OTP (those other trips used to do the same thing, but not anymore -- good to know we have self-healing code).

I'm interested to learn from you why OTP is doing the teleporting. BTW, if you move the start point slightly, the trip works fine. The symtoms are similar to problems I'm seeing with bugs #1043 and #1044 (i.e., both those bugs have problematic routing that goes away when you move the points ... and just like in the case of #1043, move the point slightly and the trip works).

[abyrd]

Hi @fpurcell, I didn't suggest the three increments as a work-around, I suggested it because walk limiting is algorithmically problematic, and this issue got me thinking about it again. I have long considered eliminating it entirely and was curious about your position. Expressing preferences/needs for less walking as a higher (even extremely high) cost per meter is fundamentally different than limiting walking.

I absolutely agree that the teleporting is a bug, but one that seems to be interconnected with walk limiting.

[fpurcell]

Hey Andrew...I like the idea of revisiting how max walk is handled in the routing engine. If the algorithm can change to incorporate what a customer is really asking for from the planner, that would be great. I think the API needs to continue to incorporate the old max walk stuff ... but am open to the addition of your walk choice (as long as the walk distance parameter is a companion option). I don't think a hard & fast 'max walk' should ever be adhered to (so maxWalk is a bit of a misnomer), and that a trip option always given when more walking is the only way a trip can be planned (and maybe the customer told "I had to exceed your walking threshold to get you on a trip")...

On customer intent, I believe when a customer asks for a trip with say 1/4th or 1/10th of a mile max walking, they're expressing their "avoid walking" preference (loudly) ... from feedback, it's people with limited mobility that choose these options, and they are willing to ride transit longer to avoid walking. So with the 1/10, 1/4 max walk trips, the routing engine should work harder to find trips that avoid / embrace walking (even if that means more roundabout transit trips ... I have an expectation when using small walk limits that I'll get weird trips). From there, the 1/2 to 1 mile max walk is the normal range, where you route based mostly on quick / fewest transfers, and try to limit walk, but you don't send someone in the opposite direction on another bus line to avoid walking 1/3 mile to a stop that is a direct path. And with larger walk distances, you're saying "yah, 'I like walking', and I'm willing to walk 1 mile (or more) to a stop if that leads to a fast transit mode with few/no transfers" -- so you route them accordingly, and try to find direct transit routes, and see worry about limiting walking distance as a secondary concern.

So algorithmically, I think these options are a good idea as they express the intent of the user. Now for me (with other cooks in the kitchen), changing the interface is right now a non-starter to abandon the "Maximum walk: " messaging, etc... But maybe over time...

[abyrd]

You mention that people who choose small distances "are willing to ride transit longer to avoid walking." It just so happens that this concept is much easier for shortest path algorithms to understand than "throw away any path over x length"... besides being closer usual human decision making. Already, we never really optimize for fewest transfers. We just increase the cost of transferring, because no one really wants the absolute lowest possible number transfers, they just are willing to trade off more riding against less transfers. It makes sense to do the same thing for walking.

I've been examining the zoo trip some more, and this at first looks like a manifestation of the problems with truly minimizing / limiting walking. The westbound MAX stop is slightly closer to the destination (accounting for where the stop point was placed, and exactly where it happens to be linked on the roads) than the eastbound one, so it's not surprising to see the router find a crazy path that ends on the eastbound platform and takes less walking.

When we limit the walk distance to 1/2 mile, the "correct" itinerary alighting at the Eastbound zoo platform apparently fails due to too much walking, but the insane path via the airport does actually manage to reach the destination with less than 1/2 mile of walking. However, upon closer inspection we see that the crazy path uses 488m/0.3 miles of walking and the failed correct path uses 626m/0.4 miles. So it's not obvious why that path did not reach the destination. Also, there are much lower time/cost paths that would accomplish the same thing, doing a U-turn closer to the destination.

After spotting several potential bugs in the remaining weight heuristic earlier today, I replaced it with the trivial heuristic (which should have no effect on results) and suddenly the expected path is found.

I also tried replacing the epsilon dominance function in State with plain old multi-criteria <= dominance, to no effect.

So there is something wrong with the remaining weight heuristic.

[abyrd]

The core problem seems resolved with c45af8a5dab. @fpurcell please verify and close if the bug is resolved on your end. Additional problems explained in #1074.

Working with a rebuilt graph exactly like maps5, the only residual problems I see are clearly due to walk limiting and OSM tags. A search with 1/2 mile of walk limiting goes like this:

1. The desired path (alighting eastbound at the Zoo) involves 886 meters / 0.55 miles of walking. It is not found.
2. The next best thing is reversing directions at Salmon street and getting off at the Westbound platform (which is one of two start points selected, see #1074) avoiding some walking. This clocks in at 456 meters / 0.3 miles, under the limit of 1/2.
3. The retrying path service then attempts to find an alternative itinerary. None exists, so the search fails and the walk limit is raised.
4. Two variants of the expected path (only one transit leg, alight eastbound) are immediately found and returned. These arrive sooner, so they are placed higher on the list in the client.

Steps 2-3 are time consuming, so with low multiple-path timeouts in place the search is aborted and only the U-turn at Salmon is reported. So this is a good example of one reason why walk limiting is inherently flawed: you don't know there's something vastly better with only a little more walking until you decide you have failed and retry.

[abyrd]

@fpurcell is this one resolved based on your tests?

[abyrd]

Much of this discussion revolves around walk limiting, which will be covered by #570. The problematic searches mentioned in the original ticket now all look OK on maps5.