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.

Precisely how do you measure?

I am reading a book with an intriguing title. "How round is your circle?" which discusses measurement and engineering mathematics (among much else). The authors point out that experimental science progressed in step with the ability to make accurate measurements. This was especially the case in astronomy, which in turn led to Newton's laws and the law of gravity being demonstrated.

I have mentioned my concern about over-precision in measurement in other blogs. Recently, Exeter, where I live, has erected signposts for the benefit of pedestrians. Distances are measured in time. This is a method often used, but is prone to abuse and error. Jokes abound about the hotel that is "two minutes from the beach" (provided you are an Olympic runner and there is no traffic in the streets), or the house for sale that is "ten minutes drive from the city centre" (when there is no other traffic, you ignore speed limits and stop signs). The problem with some of Exeter's distances is that they are too precise. One reads 19 minutes to the university campus, which is so large that it takes over 20 to cross it. There is a case for defining a set of walking times that can be used, to allow for the variation in pace, and the problem of where do you measure to. What do you think the set should be: 1,2,3,4,5,8,10,15,20,25,30,40?

How did you get started in O.R.?

For many O.R. scientists in the U.K., the route to that career was a simple one. After a first degree (3 years) with a BSc (Bachelor of Science) or BA (Bachelor of Arts) one took a one year Master's degree as a conversion course. That one year led to an MSc or MA (abbreviations as above). There were several universities offering such conversion courses. Funds for the twelve months often came from a government body, a grant-giving research council. They did for me.

Over the last few years, this funding has declined. And now it is to cease altogether. The research council argues that it should fund research, not training. But the O.R. profession has depended on the conversion courses. What will happen?

It looks as if, in the short term, the courses will continue. There are overseas students who want the British training programmes. There are a few students who will borrow money to follow the course. There may be businesses who will sponsor a recent graduate through the degree, but possibly as a part-time programme.

All in all, the route that I and thousands of other U.K. O.R. profssionals have followed is about to die.

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!

Mobile telephones and development

The Independent, the national newspaper that I read daily, had an article yesterday in which Clare Rudebeck explained how the spread of ICT (and especially mobile phones) is improving the quality of life for many people in the Third World.

If you have travelled in a developing country in the last few years, and especially if you have moved from the comfort zone of a hotel, you will have seen vendors of mobile phones and SIM cards. Looking more closely, you may have seen booths where the owner of a phone rents out his phone to members of the public. The article discusses this phenomenon, and quotes Richard Heeks, Professor of Development Informatics at the University of Manchester (UK). Following that lead, I found several items in a newsletter. Operational Research contributes to these, with models of the uncertain future. But had you been forecasting development of telecommunications in sub-Saharan Africa 20 years ago, would you have believed that there would be no need for an infrastructure of fixed telephone lines? I doubt it!

Spot the yield/revenue management! (2)

Another area of yield/revenue management that wasn't mentioned before is that of green fees at a golf club. High at weekends and holidays, low during the week.

Measuring the difficult

Sometimes in operational research it becomes necessary to measure something which is difficult. From time to time, the O.R. literature reports on studies which fall in this category, and it is fascinating to see how the profession tackles the problem of measuring the difficult. Statisticians have techniques for surveys which ask extremely sensitive questions.

I have just come across a paper which falls in this "Fascinating how the research measured the difficult". How do you measure people's journeys in an elevator? Here's the citation:

@ARTICLE{Fascinating,
AUTHOR ="Kiyoshi Yoneda",
TITLE ="Elevator Trip Distribution for Inconsistent Passenger Input-Output Data",
JOURNAL ="Decision Making in Manufacturing and Services",
YEAR = "2007",
volume = "1",
number = "1/2",
pages = "175--190",
note = "Fukuoka University, Fukuoka, 814-0180 JAPAN",
abstract = "Accurate traffic data are the basis for group control of elevators and its performance evaluation by trace driven simulation. The present practice estimates a time series of inter-floor passenger traffic based on commonly available elevator sensor data. The method demands that the sensor data be transformed into sets of passenger input-output data which are consistent in the sense that the transportation preserves the number of passengers. Since observation involves various behavioral assumptions, which may actually be violated, as well as measurement errors, it has been necessary to apply data adjustment procedures to secure the consistency. This paper proposes an alternative algorithm which reconstructs elevator passenger origin-destination tables from inconsistent passenger input-output data sets, thus eliminating the ad hoc data adjustment.",
file = F
}

One of my colleagues was involved in a study of what coins people would put into a slot machine that gave change, in order to determine what mix of change the machine should have. He started with a survey of the students we teach, and then asked them to repeat the survey with ten friends.

On the subject of elevators, I liked "10 Clever Elevator Ads".

The curse of the sat-nav system

In the UK, and I guess in most other countries, satellite navigation systems (sat-navs) are a blessing and a curse. Surprisingly little has been published about the design of the algorithms used in them, though essentially they use modified forms of Dijkstra's method, which is also the dynamic programming approach. A fellow blogger has commented on some of the stories from the UK, Belgium and the Netherlands.

Over a meal on Friday evening, friends were talking about stories which don't reach the national papers. They mentioned the large number of small sites for caravans (there is a club which has private use of fields in many farms) which have the warning "Do not use sat nav" in their guide-book. Another friend mentioned that a passenger ferry across a river, at the end of a lane, is marked as accessible to vehicles.

There are several problems with sat-navs that these stories highlight. Most obvious is that data can be incorrect, and once published, is hard to retract. Next is that data may change; roads can be closed for repair, and even online updates may not help, even if the user chooses to subscribe to such a facility. But from an O.R. point of view, there is the question of the wrong algorithm. Many of the problems could be dealt with if the algorithm took into account the kind of vehicle, which would mean solving a constrained shortest path problem ... and for nearly all cases, that would mean using the normal algorithm on a modified dataset. But that would increase the price of the system.

So we end up with people cursing the system, damage to property thanks to incorrectly routed vehicles, a cost to society with special road signs trying to stop vehicles routed with sat-nav ....

Designing road markings

I am someone who frequently asks the question "Why?" about the design of everyday objects, because of the interplay between design and operational research. On my way to the office today, I noticed that one of the advanced stop lines for cyclists seemed much larger than others that I encounter. So I asked myself "Why is it that size?" and then speculated about the optimal size for such a road marking.

The wonders of Google led me to a website from the UK Department for Transport, which says that the "cycle reservoir should be between 4m and 5m in depth. If the reservoir is shallower than this cyclists can feel intimidated by the close proximity of the vehicles queuing behind them. If the reservoir is deeper than this, motorists may feel encouraged to encroach into it." So the design is based on psychology, which links to some of my earlier blogs here. It is reassuring that someone has thought about the design and suggested guideline measurements.

So if you see me around Exeter with a 4metre tape measure, you will know that I am checking the roads!