"Reverse optimization"

[mattwigway]

We are seeing a lot of trips that optimal in the earliest arrival sense for a particular minute, but we really want to minimize in-vehicle travel time given that we have already minimized arrival time. In OTP we used to do this via so-called "reverse optimization", which was a hack wherein we would search backwards along the same transit lines to find if we could compress transfers. @abyrd points out that for this to work correctly you then have to repeat a forward search (assuming you want to transfer greedily, which most people do). This was difficult (but not impossible) to do in the context of an analyst search (where you want a full tree rather than a single origin/destination pair).

The problem this is intended to solve is illustrated by this Marey graph:

Note that there are multiple trips that arrive at the same time (indicated by the blue arrow). If we did proper reverse optimization here, we'd only see the latest-departing one, which would eliminate a lot of the weird paths we're seeing.

Fortunately, it's not hard to do proper reverse-optimization, since we have already done forward searches at future minutes. We just need to step through the arrival times array, and when later minutes have the same arrival time as earlier minutes we just swap out the paths for the path of the later departure.

[mattwigway]

We need to do this on the client, because it's possible that the codominant states would reach the destination via different destination stops (although frankly it's pretty unlikely, since identical arrival times are likely caused by transferring to the same vehicle).

[mattwigway]

Although it also looks like the code that tries to minimize transfers is broken, because that three transfer trip should be dominated by the two-transfer trip.

[mattwigway]

Hmm, this will turn into a mess though when frequency-based routes are involved. Because then the assumption of a trip at minute n + 1 upper-bounding the trip at minute n is invalid (because the two minutes use different random draws of the frequency trips). We might need to do this on the r5 side while we still have separate frequency and schedule routes.

[mattwigway]

Actually, it seems r5 should already be doing this with the scheduled search, because we're using range-RAPTOR for the scheduled search, and it shouldn't be replacing times at the destination with identical times on trips that leave earlier, unless the earlier trip has fewer transfers (which is fine, we want to show trips that take 3 minutes longer but only have one transfer).

[mattwigway]

Another example. All these trips have one transfer, the trip highlighted in blue should dominate all of them: