The coin machine problem

Yesterday I saw inside a new machine and realised that its designers had solved an interesting multicriteria problem.

Many British supermarkets have introduced self-service checkouts; the shopper brings their basket to the machine, scans the items one by one without the need for a cashier, and pays by card or by cash at the end. I use one such supermarket regularly when buying a few items, because it is generally quicker than queueing for a cashier. As I have used it, I have been interested in the algorithm it follows for giving change for cash purchases. The first part of the algorithm is straightforward; if your bill is for P pence, then as soon as you have inserted any sum greater than P, the machine gives change. (So if you want to get rid of small change, then you must put that small change in before the larger coins.) But the second part concerns the coins that are dispensed as change.

British coins have values 1, 2, 5, 10, 20, 50, 100 and 200 (pence). My change has never included coins of value 2, 50 or 200. 9 pence in change is dispensed as four 1s and one 5. 90 pence in change is dispensed as one 10 and four 20s. So when I found staff maintaining one of the machines, I stopped to look (probably being labelled by the CCTV operators as a suspicious character). There were six storage receptacles for coins to be given as change, labelled 1, 5, 10, 20, 100, 100. So there is no way that I could be given a 2, a 50 or a 200.

The designers needed a design that worked with an algorithm. Have a stock of coins to give change in a logical way, and keep that stock inside a small volume. So they eliminated three coins from inclusion. So, objective 1: Be able to give change; objective 2: keep the number of storage bins to a logical minimum. But there was a subtle objective 3: use coins of small volume, to maximise the number of coins in the machine.

2 pence coins are larger in volume than those of value 1, 5, 10 and 20. 50 pence coins are larger than 2 pence. 200 pence (2 pound) coins are very large. So these were the coins to remove from the machine's design.

Now, was this design a multicriteria O.R. problem, or not? I think it was -- even if it has a solution that will not shake the world! But it does make the world a little better.

Multicriteria Decision Making

A great deal is being written in O.R. journals and related publications about the science of multiple criteria decision making (MCDM). A few days ago I experienced one of the ways that MCDM can be especially complex.

I regularly visit a university to examine the undergraduate scripts and attend meetings as part of my duties as external examiner. My hosts book me a hotel for my overnight stay. Up to now, they have booked me into one of two hotels, E and I. I have been indifferent between them.

Both are a few minutes' walk from a railway station. Both are a few minutes' walk from the offices where we meet. Both have all the facilities of a modern impersonal hotel. Both have a good breakfast bar. E is close to a nice place to eat in the evening. I has its own in-house restaurant. I have been content in each one.

But earlier this month, I was booked into a third hotel, H. H is much further from the station and the office. Being concerned for the planet, I don't want to take a taxi for a journey that takes 20 to 25 minutes on foot, so I walk. H has all the facilities of E and I, and there was a very pleasant place for an evening meal close by.

But on the criteria that I had judged E and I by, H would be less attractive. But H has a swimming pool that is large enough to have a "decent" swim. E and I do not. A new dimension has been added to the MCDM problem. And that makes the choice for me more complex. Where shall I ask to stay next time?

Of course, if I took taxis everywhere, there would be no problem. But I do not. And there's the problem of weighing the advantages of convenience against the joy of a swimming pool. No wonder MCDM is challenging!