Comparability of transfer allowances

[mattwigway]

It looks like the rule-based fare calculator is not properly accounting for the incomparability of transfer allowances to different routes. It is using base R5 transfer allowances, which track number of remaining transfers, but not what those transfers are to (see also conveyal/r5#889).

For example, consider a city with two competing bus systems, the red bus and the blue bus. Both have the same transfer policy: paying the fare on the first bus affords one free transfer to another bus on the same system; there are no discounted transfers between the red and the blue bus. Both buses cost $2. Now consider a subset of the network that looks like this:

Consider a trip from A to B, with a transfer in the middle. To get to the transfer point, you can take either the red bus or the blue bus. At the transfer point, the blue bus is strictly better based on travel time (earlier arrival), fare (same, $2), and number of remaining transfers. The route using the red bus will be discarded. But to get to B, you need to take a red bus. The route that will be found will be the blue bus to the red bus, costing $4.

The transfer allowance also need to keep track of what the transfers are to. The easiest way to do this is to just define "classes" of transfer allowance (in this case, the red bus has one class, and the blue bus has another), and consider them incomparable. This works even if they overlap (for instance, if both the red and blue buses also provided a discounted transfer to a train). In this case, you may retain more path options than needed during routing, but filtering when creating the Pareto frontier can remove any spurious routes.

[mattwigway]

@rafapereirabr

[mattwigway]

@rafapereirabr @dhersz how does the router handle transfers on a three-leg trip—for instance, in a BUS-RAIL-BUS trip, will you get the discounted transfer from BUS->RAIL, and then also get the RAIL->BUS discounted transfer?

[dhersz]

It depends. The fare_structure object that should be passed to the routing function contains an element called max_discounted_transfers, which I think defaults to 1 in setup_fare_structure(). If 1, you'd only get the discount in BUS->RAIL, even if a potential discount exists with RAIL->BUS. If 2, you'd get the discount both in BUS->RAIL and RAIL->BUS.

[mattwigway]

Okay, let's see if I have this right. It seems like the fare you pay on ride x is determined only by the fare type of ride x-1 and whether there is at least one remaining transfer in max_discounted_transfers. In that case, I think all the transfer allowance needs to track is the number of remaining transfers and the mode of the previous ride. Any two routes that arrive at an intermediate location by the same mode and with the same number of remaining transfers will produce exactly the same additional fare to the destination.

[mvpsaraiva]

Hi guys. Sorry about the delay, I've finally got back to my personal computer and was able to implement the change we talked about in December. I've created a new R5RTransferAllowance class with a new test... @mattwigway can you take a look? I think that's what we discussed in the meeting. I didn't see any difference in the results in a quick test, which I think it's a good thing haha.

[mattwigway]

Thanks! I'll take a look next week.

Matt

On Thu, Jan 11, 2024, 6:59 PM Marcus Saraiva @.***> wrote:

Hi guys. Sorry about the delay, I've finally got back to my personal computer and was able to implement the change we talked about in December. I've created a new R5RTransferAllowance http://java-r5rcore/src/org/ipea/r5r/Fares/R5RTransferAllowance.java class with a new test... @mattwigway https://github.com/mattwigway can you take a look? I think that's what we discussed in the meeting. I didn't see any difference in the results in a quick test, which I think it's a good thing haha.

— Reply to this email directly, view it on GitHub https://github.com/ipeaGIT/r5r/issues/349#issuecomment-1888158798, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAEKNLT6LIDDQSA4ZZQVSX3YOB4H7AVCNFSM6AAAAAA4WZADQKVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMYTQOBYGE2TQNZZHA . You are receiving this because you were mentioned.Message ID: @.***>

[mattwigway]

I've looked at this a bit and it looks mostly correct - I have a few comments but I want to make sure they're complete before I write something up. That said, I find the fare calculators really difficult to debug without a visualizer, so I created a quick and dirty R package rfareto that allows looking at r5r results in the Conveyal Fareto visualizer. It needs the fareto branch of r5r from my fork for now. Happy to see this integrated into r5r if desired, but wasn't sure if it would overcomplicate things.

[mattwigway]

I'm going to look at this a bit more thoroughly, but this seems to be on the right track. As I understand it, the marginal fare for a ride is based only on (a) the fare type of the ride, (b) the fare type of the previous ride, (c) the number of remaining discounted transfers, and (d) the previous route in some edge cases (see note below about this). There's never a case where the fare type of a ride other than the most recent one can affect the fare (e.g. in New York, bus -> Staten Island Ferry results in a different incremental fare than walk to staten island ferry—and that whole document is an interesting read for the implementation details of a needlessly complex fare system). Is that correct?

If that is true, then tracking the previous leg type and the number of remaining transfers is all that is needed, since those are the only things that can affect future fares. Treating different leg types as incomparable is the right approach, as we don't know which leg types provide the best transfers for future rides[^strictly]. A transfer allowance of the same fare type is the same or better if it has the same or greater number of remaining transfers (assuming transfer discounts are always positive). This is how the transfer allowance is currently implemented.

A few initial comments:

• I don't think it's a good idea to mix R5RTransferAllowances and regular TransferAllowances; then there will be two different codepaths for comparing them and this could lead to confusions. I think everything should use an R5RTransferAllowance, and we can add special logic for an "empty" transfer allowance (it could just be if (other.number == 0) return true;).
• It looks like the fareType is not getting set on the first leg:

[^strictly]: If some leg types provide strictly better transfer discounts to all rides, it would be possible to use this information to speed up the algorithm. But it's probably not worth the trouble, and this is the kind of thing where you could get nasty correctness bugs as well.

[mattwigway]

Oh, and I forgot the note about the routes. The fare for the next ride technically depends on the previous route as well, since it is possible to say that discounted transfers can't be between the same route. Adding this constraint though will probably make the algorithm intractable, as every state from a different route would have to be treated as incomparable. I'd advise just noting this as a limitation (we might miss a cheaper trip when transferring to the same route is optimal); I think this is rare as these rules are usually intended to prevent people from making stops during their trip which isn't what we're modeling.

[rafapereirabr]

Thanks @mattwigway . You understanding of the rules of the transit fare system seems to correct to me, but I'll leave it to @mvpsaraiva to comment / respond on the code side of things.

[mvpsaraiva]

Thanks @mattwigway. I've made some changes based on your suggestions. I'm no longer mixing R5RTransferAllowances and regular TransferAllowances, and added some tests to represent an empty transfer allowance. I'm also setting fare type for the first leg of the trip.

I've also managed to run the fareto debugger locally, and it's quite useful. It maybe a good idea to make it an official part of r5r... or maybe build a simpler version. But that's something for the future.

Apparently, everything is ok, at least for our use cases. Perhaps now we can try that comprehensive test that we discussed in December? That idea of randomizing some routes into different fare groups and check if any bug emerges.

[mattwigway]

Yes, let's try the test.

On Mon, Jan 29, 2024, 3:11 PM Marcus Saraiva @.***> wrote:

Thanks @mattwigway https://github.com/mattwigway. I've made some changes based on your suggestions. I'm no longer mixing R5RTransferAllowances and regular TransferAllowances, and added some tests to represent an empty transfer allowance. I'm also setting fare type for the first leg of the trip.

I've also managed to run the fareto debugger locally, and it's quite useful. It maybe a good idea to make it an official part of r5r... or maybe build a simpler version. But that's something for the future.

Apparently, everything is ok, at least for our use cases. Perhaps now we can try that comprehensive test that we discussed in December? That idea of randomizing some routes into different fare groups and check if any bug emerges.

— Reply to this email directly, view it on GitHub https://github.com/ipeaGIT/r5r/issues/349#issuecomment-1915478119, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAEKNLRNFJICORCPYYSPOXTYQ766BAVCNFSM6AAAAAA4WZADQKVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMYTSMJVGQ3TQMJRHE . You are receiving this because you were mentioned.Message ID: @.***>

[rafapereirabr]

@dhersz is currently working on the tests and will report soon