Saturday, October 30, 2010

Young OR Conference April 2011 - Consultancy Stream

The OR Society is hosting the biennial Young OR conference in the University of Nottingham, United Kingdom, on 5-7 April 2011. I am organising the Consultancy stream, and I am looking for speakers, presenters and of course audience. If you are disregarding the conference because of the word 'young', think again, because the definition of 'young' in this context is <= 10 years in the field of OR. You can find more information for presenters here. Essentially, this is what you need to do:
  • a 200 word abstract for the conference programme
  • a presentation of max 20 minutes


I described the stream as follows:

The consultancy stream aims to attract speakers and audience interested in sharing their experiences in the practical application of Operational Research in a client-consultant setting. The consultant can be internal or external to an organisation. The problem at hand can be simple or complex, technically or organisationally.

The challenges we face as OR consultants are very similar no matter the industry, the organisation or the problem at hand. There are definite gaps between practical application and academic research in OR, but it is still one of the most rewarding jobs. The recommended format would be a case study presentation covering the entire cycle of the project where possible, but presentation creativity is absolutely encouraged.

  • How did the problem find you or how did you find the problem? i.e. How was it sold?
  • Steps taken to establish your course of action
  • OR and non-OR techniques and methodologies used to structure and solve the problem
  • How were your findings and recommendations communicated to the stakeholders and decision makers in an effective way?
  • How did the client take your recommendations? Did they implement?
  • Finally, what do you enjoy most about your job?

Most of all, have fun and meet some fellow Operational Research practitioners.


Please pass on the message. Better yet, please drop me a line to present! As you can see, the stream description is very wide, encompassing all real life applications of OR. You don't have to have 'consultant' in your title, neither does your company or organisation. Come and share your experience and the fun (or pain?) of applying Operational Research in anything from ordinary day to day life to extraordinary situations of, for instance, life and death and taxes. How have you helped with better and more informed decision making?

Wednesday, October 13, 2010

Oyster Card Optimisation

Transportation is an industry where a lot of Operations Research is practiced. In the following article I would like to share an example of optimisation that I have noticed in the fare pricing system on the London Underground.

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.

Saturday, October 9, 2010

Expedia Revenue Management at Check-out or Rule Compliance

We have all been shopping online for something only to be told after making the purchase decision that it is no longer available or no longer available at that price. This often happens when buying flights, as prices can change minute-to-minute and you can be left with a much higher ticket price which makes you abandon your purchase. Disappointment all around.

However, the opposite happens from time to time as well! The price of a London to Seattle flight, when I found it was £649.07 (including all fees). I clicked to start jumping through all the purchase hoops, but after a couple steps into the check-out process, it flagged up, rather alarmingly, as £616.07. That's a 5% decrease in price. (See, I'm not making it up!)





I was pleasantly surprised, of course. But why would they do that?

I've got 2 suspicions.

1. Revenue Management / Yield Management / Consumer Psychology
In the weeks prior to this screen capture, I've been to the site a few times already looking for the exact same flight. Even though I'm not logged in, I'd venture to guess that the site has looked up my cookies and knew that I've been looking for these flights. Therefore, it should know that I was a likely buyer, rather than a window shopper (pc pun intended). I've been at the check-out stage before, but have abandoned the shopping cart eventually. It would be quite logical for the site to entice me with a lower price as a 'pleasant surprise' to finally get me to spill my moola. Not to mention the positive impression it's left with the shopper (look what I'm doing now - free advertising!).

However, is it worth the 5% price drop? How does Expedia decide 5% was the right balance of customer incentive and revenue loss? I was already a willing customer, ready to bite. Isn't it just giving the 5% away for free? In my case, it's difficult to say whether the move has gained my loyalty to Expedia, because I was already a frequent visitor and buyer there. It may have re-enforced my loyalty though. It would be very interesting to analyse a few year's purchase and cart abandonment data of customers where this has happened to, versus a control group. Would we observe a lower purchase completion rate, which would drive a higher lifetime revenue per customer?

2. Airline price adjustment rule compliance
There could exist such a regulatory rule in the online airline pricing world to protect consumers, such that the vendor must notify the buyer of last minute price changes before the final purchase is completed. Now, I don't know if such a rule exists, but it is possible. However, it sounds extremely difficult for the regulators to enforce and monitor compliance.

I personally think it's more the former than the latter. One way to test the real reason behind the price drop could be to see if it's always a 5% decrease. Time to do some more flights window shopping!



P.S. In a previous article where we observed operational inefficiencies at London's Gatwick Airport, we erroneously stated that the airport operator was BAA (British Airports Authority). In fact, BAA was forced to sell Gatwick to please regulators seeking to break a monopoly on UK's airports. Our apologies to BAA. The current owners are Global Infrastructure Partners, who also owns 75% of the London City Airport.



Update:
Responding to two unconstructive comments, one of which was downright rude and was deleted, we thought we would add to this article.

The commenters suggest that Expedia is not a price setter, but just a re-seller making possibility one above unlikely. That said, the question still stands, "What's going on here?". If the prices that Expedia gives you when you search are cached and not live, that seems to be to be a surprising shortcoming. If they are, why offer a lower price to someone who appears to have already made the decision to purchase?

There are probably a number of factors at play that someone from the online travel community could answer.

If I were reselling through Expedia, I would want my price-updating algorithm to give the higher of the two prices at the point of payment, i.e. more profit. Both Expedia and the vendor are motivated to collect a higher price and therefore a higher commission as a percentage of the selling price.

The commenters may be very correct in saying that Expedia doesn't set the price, but merely re-sells at whatever the price the vendor names. That's why we said there were two possibilities, the second being not revenue management. However, if Expedia is not practicing revenue management in this way, they probably should at least experiment with it. Their commission represents a headroom within which they can optimize and the goal, after all, is not to make the greatest profit on each sale, but instead the greatest profit across all possible sales.