Public transportation in London, England has a convenient and efficient means of collecting fares from travellers. Introduced back in 2003, the Oyster Card is the size of a credit card and is pre-loaded with money by the traveller. On each trip they take, the traveller touches the oyster card to a reader, registering their journey with the system which deducts payment from their balance. Each single journey is charged at a different rate depending on the origin zone, destination zone, and time of day.
A daily capping system is in place such that you will never pay, in a day, more than the price of a day-pass covering all of your journeys for the day. For example, in a day where you only travel in zone 1 off-peak your journeys will cost £1.80, £1.80, £1.80, £0.20, £0, £0 and each journey after that is free, as you essentially now have a day-pass on your card when your daily cap has reach at £1.80*3 + £0.20 = £5.60.
A Canadian friend of mine, currently residing in Australia, visited me here in London the other weekend. Knowing the ease, convenience, and price-capping guarantee, I recommended that he get an Oyster Card. He loaded it up with £10 at Heathrow and came into town to drop his bags at my place. After a short jet-lag nap he headed out into the core to see the tourist sights, travelling frequently on the underground. At the end of the day he reported that his Oyster Card credit had run out and that he had needed to top up the balance. This surprised me, so we worked out his journeys and payments:
- Zone 6 (Heathrow) to Zone 1 at Peak - £4.20
- 6 x Zone 1 Off-Peak - £1.80 each
Because he travelled from Zone 6 to Zone 1 at peak, his cap for the day was £14.80 even though had he bought a Zone 1 day-pass at Heathrow he would have only paid £5.60 + £4.20 = £9.80. So the Oyster Card is convenient and comes with a price capping system, but there are holes in that system. In this case it cost him £5.00 which is about an hours work at minimum wage in the UK, so not trivial.
Any individual travelling on a public transportation network wants to perform an optimisation. In this case, they want to minimize their total cost by selecting the most efficient combination of fares to cover all of their journeys. This problem presents itself as a classic optimization problem; Subject to constraints, like the requirement to purchase tickets to cover all journeys, the goal is to minimize total cost, a function of the decisions to buy tickets. An optimisation problem like this can be formulated mathematically and solved by computers using a discipline called integer programming, one of the tools in the Operations Research practitioner's toolbox.
If this problem can be solved by computers, why doesn't the Oyster Card system provide a lowest price guarantee rather than the evidently imperfect price-capping system? Consider for a moment the requirements of the system:
- Daily ridership of around 3 million
- At the end of their journey, users must be told almost instantaneously what the cost was and what their remaining balance is
Optimisation problems of this nature are not always fast, easy, or even possible to solve optimally. The computers of today are fast, but there's plenty still beyond them. The tube system isn't even using the latest technology. I've been told that some Underground components still use punch cards! Every time a customer makes a journey this optimisation must be calculated and that must be done 3 million times a day and that is unfortunately too much.
When an optimisation problem is too big or too complex to solve directly and perfectly, analysts use something called heuristics to come up with near-optimal solutions. There are commonly used methods, but depending on the problem, customised heuristics can be developed, using the unique structure of the problem in question to produce a near-optimal result. That is exactly what the price capping system is; It is a heuristic used to make a good approximation of the lowest price.
There are effectively only two types of tickets in the system: single tickets and day passes. Day passes are the only way to save money. It is rarely worthwhile buying two separate day passes. It follows naturally that a simple rule of thumb for cost optimisation is to compare your daily total of single trips to the price of a day pass covering all those journeys and choose the lower option. The conditions that I list at the start of this paragraph are essential consequences of the structure of the problem, and we can exploit them to arrive at our simple heuristic, the same one that the oyster cards use.
In a future article I hope to look into formulating the optimisation problem of the London Underground and consider alternative heuristics.
Posts
No comments:
Post a Comment