Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Comparability of transfer allowances #349

Open
mattwigway opened this issue Sep 13, 2023 · 13 comments
Open

Comparability of transfer allowances #349

mattwigway opened this issue Sep 13, 2023 · 13 comments

Comments

@mattwigway
Copy link
Contributor

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:

drawing

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
Copy link
Contributor Author

@rafapereirabr

@mattwigway
Copy link
Contributor Author

@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
Copy link
Collaborator

dhersz commented Sep 28, 2023

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
Copy link
Contributor Author

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 added a commit that referenced this issue Jan 11, 2024
@mvpsaraiva
Working on comparability of transfer allowances (issue #349)
5884864
@mvpsaraiva
Copy link
Collaborator

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
Copy link
Contributor Author

mattwigway commented Jan 12, 2024 via email

@mattwigway
Copy link
Contributor Author

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.

image

@mattwigway
Copy link
Contributor Author

mattwigway commented Jan 19, 2024 •
edited

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 rides1. 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:
image

Footnotes

  1. 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
Copy link
Contributor Author

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
Copy link
Member

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
Copy link
Collaborator

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
Copy link
Contributor Author

mattwigway commented Jan 30, 2024 via email

@rafapereirabr
Copy link
Member

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
4 participants
@mattwigway @dhersz @mvpsaraiva @rafapereirabr