6 ms·

My company did some work with TfL when Oystercards were being rolled out. A very clever bloke at work was tasked with working out an algorithm that would retros

My company did some work with TfL when Oystercards were being rolled out. A very clever bloke at work was tasked with working out an algorithm that would retrospectively minimise a passenger's spend based on their journey history - so e.g. If they'd done 9 single journeys in a week it might decide they'd have been better off buying a weekly pass, and adjust their balance accordingly. You have monthly and even annual passes to factor in as well of course. He spent about 20 minutes one lunchtime trying to explain it to me, but it went straight over my head (I think 'alpha-beta pruning' was in there somewhere), but anyway it was all for naught as - hardly surprisingly - TfL had little appetite for software that would actually reduce their revenue.

shawabawa3 5y ago
It wasn't all for naught. That's how oyster (and now contactless payments) work
- OJFord 5y ago
  I don't think it is? They're capped, but afaik it doesn't work out if you'd have been better off with some specific combination of prepaid travelcards and charge you that instead (which could be less than the caps in total)?
  - tialaramex 5y ago
    I don't think it can ever make sense to have a "combination of prepaid travelcards". A human that is guessing what to buy in advance might rationally choose to do this, but the machine knows the journeys you actually took. They're priced such that it's not going to make sense to buy more than one if you could figure out the correct one to buy (which the algorithm can), and the cap is always cheaper or the same price than an equivalent travelcard if one exists. Suppose I make one journey from Amersham to Chalfont, it's £1.60 off peak, if I make this journey over and over I hit the cap (for off peak travel more or less anywhere) at £13.60. Now suppose that randomly during the rush hour, I make one other journey, from Waterloo to Victoria, in Zone 1. That costs £2.40 and being peak travel it isn't included in my cap, so my total is now £16.00 I can do that twice, maybe it happens in the morning rush hour, and again in the evening, and between then I run back and forth between Amersham and Chalfont, in this case my total is £18.40. But if I did the Zone 1 peak journey a third time, a new cap kicks in, for zones 1-9 any time, at £19.30 and neither kind of journey costs any further money, nor do most journeys anywhere in the network since that's all the numbered zones and any time.
    - OJFord 5y ago
      If the period and zone coverage were different it could couldn't it? A longer travelcard covering zones 2-3, (for work say) but then a much shorter period where you have a lot of travel in zone 1 (friend visiting so doing touristy things for a weekend say)?
      - tialaramex 5y ago
        Not really. Oyster's PAYG pricing only covers daily travel (either the whole day or the off peak). For a week or longer yes you should buy (on Oyster) a fixed duration travelcard in advance. But let's continue the thought experiment. If you travel in zones 2-3 for work you would want a Travelcard for those journeys, indeed, and you'd likely buy that for an Oyster (I believe paper tickets for this still exist, but they might not) which is £27.70 per week, or maybe you do this constantly that's £1108 for the whole year. However that work travelcard covers zone 1 anyway, so the tourist trips into zone 1 are free for you. Suppose the tourist trips are instead outward, and you're entering zone 4. Now these trips aren't free, but the day travelcard that includes zone 4 is £13.90 and the Oyster cap to zone 4 is £10.60 so you won't save money by buying another travelcard for the tourist trips, using PAYG with the cap is significantly cheaper and easier. One thing a careful Londoner might do if the tourist friend is visiting for a bit longer and they (for some reason) don't carry a very long period travelcard or it was due to expire anyway, is choose to "upgrade" to more zones for say one week and then buy their usual card again. Suppose your card runs out on Friday, your friend lands Saturday morning and you're taking a week off exploring Greater London with them. You could buy a zone 1-9 weekly card from Saturday to Friday, just under £100 for all trips almost anywhere in the network for that week. However, the tourist gets almost as good a deal on their foreign credit card because it has a weekly cap, the TFL credit card system thinks only in Monday-Sunday weeks, so their maximum cost is £135.10 for the same trips (two days, plus one week) but if they sometimes don't hit the daily caps it'll be far lower, so even just two "quiet" days with fewer journeys or staying in central London would demolish the price difference.
        OJFord 5y ago
        > However that work travelcard covers zone 1 anyway, Oh, you're right, that's what I was missing; I could've sworn you could get 2&3-only travelcards.
- tialaramex 5y ago
  Yes, although it's not exactly retrospective. The trick is, each time it sees your card the system is trying to figure out what the minimum price it could charge is for everything that happened so far. The fares are designed such that it can't ever be cheaper to do more journeys†, however it might not be more expensive, so the extra cost of any completed journey is always going to be somewhere between £0 and the maximum peak single fare. This happens live because you are shown the current balance (which needs this calculation) when completing journeys in some places, and can also check it from outside the system. So you can see that a journey you just made cost say 10p even though obviously there are no fares that low, because 10p was the difference between the cheapest way to do your previous set of journeys, and the cheapest way to do all those journeys plus the new one. † There are sometimes weird corner cases where e.g. travelling one extra stop and walking back is slightly cheaper but that's a different journey not an extra one.
pertymcpert 5y ago
I don't understand how they could implement the savings / spending caps for contactless cards but couldn't do it at the same time for Oyster cards. It's insanity.
- lmz 5y ago
  The contactless cards are logged then charged centrally. Stored value cards are charged at the gate. Central charging allows more flexibility as you have more data to work with.
- blibble 5y ago
  oyster does have spending caps, but not the more complicated calcuations why? oyster is a stored value card the barrier where you tap-out calculates and takes the money off the card instantly, and given the interaction time to get you through the barrier the computation is necessarily limited whereas a contactless card is effectively being a pointer to a bank account that can be charged at a later date for TfL there is a batch process at the end of the day which does that
  - zimpenfish 5y ago
    > for TfL there is a batch process at the end of the day which does that Which can lead to some perplexing notifications from your bank at 0400 when it says you've just charged £N at A.N.Tube and it takes you a good three minutes before you realise it's not someone cloning your card but the journey you made 18 hours ago.
Foobar8568 5y ago
The fun was for calculating the bonus payment on the Denmark transit system, I don't know how many man-years was saved once it was automatized.
leonk 5y ago
That’s what contactless cards do now, there’s a PAYG cap. When you read about it doesn’t really sound that complex (not sure if it needed a clever bloke with an algorithm, but then what do I know?) I guess because they couldn’t work out a way for you to purchase a travel card on your contactless card, so this was the only way to allow regular commuters to use their contactless. Anyway it was the reason I switched over from oyster to contactless. I realised I was getting ripped off as I would always use PAYG and _sometimes_ went over the caps.
- OJFord 5y ago
  There's some complexity arising from zones, and travelcards being based on zonal travel. So it's more complex than just capping it, or comparing it to the price of a travelcard, because you have to consider different combinations of travelcard (period and zone) and which journeys to ignore, leaving at PAYG rate. I don't know what alpha-beta pruning is, and I'm not necessarily asserting it's massively complex, and I don't know anything about/haven't worked in the area beyond as a user - just pointing out it's not as simple as it might at first seem.
  - TylerE 5y ago
    A-B pruning is a technique from chess engines. Basically, you do a breadth-first full recursive solve, but bail out of any branch that is clearly worse than other candidates.
lapetitejort 5y ago
Last time I used digikey, they would notify me that if I bought a few more widgets I'd be eligible for bulk pricing, which would lower my bill. Sure, they would move more widgets, but would receive less money. I was a little shocked and impressed. I did buy more widgets, and did indeed lower my bill.
- sokoloff 5y ago
  I find Amazon’s functionality of “you bought this item on March Xx, 20YY” to be similar. Sometimes I’m buying more dishwasher tablets (and the notice serves only to tell me that I’m buying the same thing), but it’s definitely caused me to not re-buy a book I already owned a few times and that left me with a very positive impression of Amazon.
  - singingboyo 5y ago
    There's a flip side to this that benefits amazon, though still very useful for the customer. If I'm poking through something I maybe want but might get in person, and I find something I've already bought that fits my need again... I'm more likely to buy again than to wander over to a physical store. Especially true for things I don't buy often and then need suddenly, like casual clothing (oops, ripped it) or random felt pads for furniture (oh dear, that's going to scratch things up quick). I'm also less likely to hem and haw about it until I just buy from a physical store. (For example, "these paper towels or those? idk, decide tomorrow" and then buy with groceries the next day.) Besides, if you rebuy, then return, that's worse for them than if you just never rebought. Sure, they'll probably charge you a restock fee, but I'm not entirely convinced it covers the full cost to Amazon.
    - sokoloff 5y ago
      That’s another policy genius: almost nothing they sell has a return cost or restocking fee to the consumer (other than me having to drive it to a drop off point, of which there are many within 1.5 miles). That’s for a US Prime member anyway. I return very few things, but I’ve never been charged a penny for them. That makes me way more likely to just buy from Amazon, even if another merchant is slightly cheaper.
pharmakom 5y ago
I think you could encode the journey data into any open cost-minimisation engine tbh.
el_oni 5y ago
My local bus company did this. 3 trips in a day? Price caps out at a day ticket. 14 trips in a week? Price caps out at a weekly ticket. Same for the month. It has a weird effect where I would take a couple of extra journeys just to whack it into the next tier. Like head into Leeds on the bus to browse the shops and get lunch.

shawabawa3 5y ago

It wasn't all for naught. That's how oyster (and now contactless payments) work

OJFord 5y ago
I don't think it is? They're capped, but afaik it doesn't work out if you'd have been better off with some specific combination of prepaid travelcards and charge you that instead (which could be less than the caps in total)?
- tialaramex 5y ago
  I don't think it can ever make sense to have a "combination of prepaid travelcards". A human that is guessing what to buy in advance might rationally choose to do this, but the machine knows the journeys you actually took. They're priced such that it's not going to make sense to buy more than one if you could figure out the correct one to buy (which the algorithm can), and the cap is always cheaper or the same price than an equivalent travelcard if one exists. Suppose I make one journey from Amersham to Chalfont, it's £1.60 off peak, if I make this journey over and over I hit the cap (for off peak travel more or less anywhere) at £13.60. Now suppose that randomly during the rush hour, I make one other journey, from Waterloo to Victoria, in Zone 1. That costs £2.40 and being peak travel it isn't included in my cap, so my total is now £16.00 I can do that twice, maybe it happens in the morning rush hour, and again in the evening, and between then I run back and forth between Amersham and Chalfont, in this case my total is £18.40. But if I did the Zone 1 peak journey a third time, a new cap kicks in, for zones 1-9 any time, at £19.30 and neither kind of journey costs any further money, nor do most journeys anywhere in the network since that's all the numbered zones and any time.
  - OJFord 5y ago
    If the period and zone coverage were different it could couldn't it? A longer travelcard covering zones 2-3, (for work say) but then a much shorter period where you have a lot of travel in zone 1 (friend visiting so doing touristy things for a weekend say)?
    - tialaramex 5y ago
      Not really. Oyster's PAYG pricing only covers daily travel (either the whole day or the off peak). For a week or longer yes you should buy (on Oyster) a fixed duration travelcard in advance. But let's continue the thought experiment. If you travel in zones 2-3 for work you would want a Travelcard for those journeys, indeed, and you'd likely buy that for an Oyster (I believe paper tickets for this still exist, but they might not) which is £27.70 per week, or maybe you do this constantly that's £1108 for the whole year. However that work travelcard covers zone 1 anyway, so the tourist trips into zone 1 are free for you. Suppose the tourist trips are instead outward, and you're entering zone 4. Now these trips aren't free, but the day travelcard that includes zone 4 is £13.90 and the Oyster cap to zone 4 is £10.60 so you won't save money by buying another travelcard for the tourist trips, using PAYG with the cap is significantly cheaper and easier. One thing a careful Londoner might do if the tourist friend is visiting for a bit longer and they (for some reason) don't carry a very long period travelcard or it was due to expire anyway, is choose to "upgrade" to more zones for say one week and then buy their usual card again. Suppose your card runs out on Friday, your friend lands Saturday morning and you're taking a week off exploring Greater London with them. You could buy a zone 1-9 weekly card from Saturday to Friday, just under £100 for all trips almost anywhere in the network for that week. However, the tourist gets almost as good a deal on their foreign credit card because it has a weekly cap, the TFL credit card system thinks only in Monday-Sunday weeks, so their maximum cost is £135.10 for the same trips (two days, plus one week) but if they sometimes don't hit the daily caps it'll be far lower, so even just two "quiet" days with fewer journeys or staying in central London would demolish the price difference.
      - OJFord 5y ago
        > However that work travelcard covers zone 1 anyway, Oh, you're right, that's what I was missing; I could've sworn you could get 2&3-only travelcards.
tialaramex 5y ago
Yes, although it's not exactly retrospective. The trick is, each time it sees your card the system is trying to figure out what the minimum price it could charge is for everything that happened so far. The fares are designed such that it can't ever be cheaper to do more journeys†, however it might not be more expensive, so the extra cost of any completed journey is always going to be somewhere between £0 and the maximum peak single fare. This happens live because you are shown the current balance (which needs this calculation) when completing journeys in some places, and can also check it from outside the system. So you can see that a journey you just made cost say 10p even though obviously there are no fares that low, because 10p was the difference between the cheapest way to do your previous set of journeys, and the cheapest way to do all those journeys plus the new one. † There are sometimes weird corner cases where e.g. travelling one extra stop and walking back is slightly cheaper but that's a different journey not an extra one.

pertymcpert 5y ago

I don't understand how they could implement the savings / spending caps for contactless cards but couldn't do it at the same time for Oyster cards. It's insanity.

lmz 5y ago
The contactless cards are logged then charged centrally. Stored value cards are charged at the gate. Central charging allows more flexibility as you have more data to work with.
blibble 5y ago
oyster does have spending caps, but not the more complicated calcuations why? oyster is a stored value card the barrier where you tap-out calculates and takes the money off the card instantly, and given the interaction time to get you through the barrier the computation is necessarily limited whereas a contactless card is effectively being a pointer to a bank account that can be charged at a later date for TfL there is a batch process at the end of the day which does that
- zimpenfish 5y ago
  > for TfL there is a batch process at the end of the day which does that Which can lead to some perplexing notifications from your bank at 0400 when it says you've just charged £N at A.N.Tube and it takes you a good three minutes before you realise it's not someone cloning your card but the journey you made 18 hours ago.

Foobar8568 5y ago

The fun was for calculating the bonus payment on the Denmark transit system, I don't know how many man-years was saved once it was automatized.

leonk 5y ago

That’s what contactless cards do now, there’s a PAYG cap. When you read about it doesn’t really sound that complex (not sure if it needed a clever bloke with an algorithm, but then what do I know?) I guess because they couldn’t work out a way for you to purchase a travel card on your contactless card, so this was the only way to allow regular commuters to use their contactless. Anyway it was the reason I switched over from oyster to contactless. I realised I was getting ripped off as I would always use PAYG and _sometimes_ went over the caps.

OJFord 5y ago
There's some complexity arising from zones, and travelcards being based on zonal travel. So it's more complex than just capping it, or comparing it to the price of a travelcard, because you have to consider different combinations of travelcard (period and zone) and which journeys to ignore, leaving at PAYG rate. I don't know what alpha-beta pruning is, and I'm not necessarily asserting it's massively complex, and I don't know anything about/haven't worked in the area beyond as a user - just pointing out it's not as simple as it might at first seem.
- TylerE 5y ago
  A-B pruning is a technique from chess engines. Basically, you do a breadth-first full recursive solve, but bail out of any branch that is clearly worse than other candidates.

lapetitejort 5y ago

Last time I used digikey, they would notify me that if I bought a few more widgets I'd be eligible for bulk pricing, which would lower my bill. Sure, they would move more widgets, but would receive less money. I was a little shocked and impressed. I did buy more widgets, and did indeed lower my bill.

sokoloff 5y ago
I find Amazon’s functionality of “you bought this item on March Xx, 20YY” to be similar. Sometimes I’m buying more dishwasher tablets (and the notice serves only to tell me that I’m buying the same thing), but it’s definitely caused me to not re-buy a book I already owned a few times and that left me with a very positive impression of Amazon.
- singingboyo 5y ago
  There's a flip side to this that benefits amazon, though still very useful for the customer. If I'm poking through something I maybe want but might get in person, and I find something I've already bought that fits my need again... I'm more likely to buy again than to wander over to a physical store. Especially true for things I don't buy often and then need suddenly, like casual clothing (oops, ripped it) or random felt pads for furniture (oh dear, that's going to scratch things up quick). I'm also less likely to hem and haw about it until I just buy from a physical store. (For example, "these paper towels or those? idk, decide tomorrow" and then buy with groceries the next day.) Besides, if you rebuy, then return, that's worse for them than if you just never rebought. Sure, they'll probably charge you a restock fee, but I'm not entirely convinced it covers the full cost to Amazon.
  - sokoloff 5y ago
    That’s another policy genius: almost nothing they sell has a return cost or restocking fee to the consumer (other than me having to drive it to a drop off point, of which there are many within 1.5 miles). That’s for a US Prime member anyway. I return very few things, but I’ve never been charged a penny for them. That makes me way more likely to just buy from Amazon, even if another merchant is slightly cheaper.

pharmakom 5y ago

I think you could encode the journey data into any open cost-minimisation engine tbh.

el_oni 5y ago

My local bus company did this. 3 trips in a day? Price caps out at a day ticket. 14 trips in a week? Price caps out at a weekly ticket. Same for the month. It has a weird effect where I would take a couple of extra journeys just to whack it into the next tier. Like head into Leeds on the bus to browse the shops and get lunch.