Wednesday, 23 January 2013

Father Geoffrey's journey

Once upon a time, five hundred years ago, there was a clergyman in a village church in Devon who had a problem.  As part of his duties as priest, he needed to hear the confessions of his parishioners, when he would hear their sins and grant them forgiveness.  In other village churches, the people would come to the church and make their confessions there.  But in the parish of Bere Ferrers, on a peninsula between the rivers Tavy and Tamar in south-west Devon, the parishioners were scattered in their farms and there were several silver mines.  How could he plan to hear confessions?  Farming went alongside mining; some people did both.  As he considered his parish, this priest (let's call him Father Geoffrey because that sounds suitably medieval) had two thoughts about his problem.

First, if he told the miners to come to the church for confession, they would lose at least a day's production at the mine - one day for the return trip to the church and a little more time to catch up on the effects of a day away from the mine.  And the king needed the silver.  So did the church, which derived part of its income from the mines.

Second, if he went to the miners (against the well-established customs in other parishes) he could visit all the outlying farms, visit the sick, and enjoy the hospitality of some of the farmers.  This might be pleasant.  He could have a tour of the parish as well as doing his church duty.

Father Geoffrey was not only thoughtful, he was educated; in fifteenth century Devon, there were not many people who could read and write.   He wrote down in a list the names of the forty-eight households or mines in the parish.  And he drew a simple map of these forty-eight.  And one day, he rearranged his list to make a route around those places, making sure that he never doubled-back on himself.  Then he divided the list into a succession of days, to balance the number of confessions to be heard each day and (privately) to give himself a nice place to stay overnight.  His choice of visiting would have more benefits than summoning his parishioners to the church.

So, one day, a fortnight before Easter, Father Geoffrey made his tour of the parish.  It was a great success.  His parishioners enjoyed seeing him.  Bere Ferrers in spring is a beautiful place.  He returned to his home tired, well-fed and happy, ready for the celebration of Easter.

So successful was his trip, that he repeated it the next year.  And, to remind himself of the route, he wrote it down.  His church owned several manuscripts (this was, of course, before the first printed books).  He recorded his journey on the back of one of the church manuscripts, so he could do the tour again, and perhaps his successor in the parish could do it as well.  Amazingly, the manuscript survived the centuries and is kept in the library of Exeter Cathedral, with that sequential list on the back in Father Geoffrey's scrawling handwriting.

Five hundred years later, a medievalist in Exeter, Professor Avril Henry, discovered that the handwritten notes on the back of this manuscript formed Father Geoffrey's carefully ordered list of the households of his parish, divided into fourteen groups.  Some of those groups were identified alongside days of the week.  Professor Henry interpreted the list as a tour of the parish.  But, to interpret it as instructions for hearing confessions went against other evidence from medieval church records.  So Professor Henry was suggesting something new.

A few years further on, I came across Professor Henry's paper, and read about the controversy it had caused.  Her paper included a map of the parish, and the route that corresponded to those fourteen days and forty-eight places.  And I thought "travelling salesperson".  Could I prove that this was a systematic tour?  Statistical analysis, and aspects of the travelling salesperson problem with constraints in a two-dimensional plane seemed to say yes.  I drafted a paper based on my analysis.  Avril Henry and I discussed it.  She made some helpful comments about the historical context and my analysis.  I revised the draft and submitted it for publication.

Today, the resulting paper is available online.  I cannot prove that Father Geoffrey did what I have described.  The story above is speculation based on the handwritten notes, and an attempt to make sense of them using medieval history, operational research and statistics.  But the paper gives the evidence to support the story.  If you have access to the journal OR Insight, you can read it for yourself.  If not, here is the abstract.  (And I am allowed to send you a copy if you ask!)

For more information about this beautiful, and secluded part of Devon, go to the Tamar Valley AONB site.

So, let us raise a toast to the memory of Father Geoffrey of Bere Ferrers, pioneer of systematic route planning, and - perhaps - cost-benefit analysis!




Monday, 14 January 2013

Could OR help? Did OR help?

Academics in OR, and those who hold office in the various national societies for Operational Research, often ask why OR is not used more widely.  I asked this myself in an earlier blog.  There are numerous reasons why not, which are reiterated every time someone asks the question.

Every so often, I look at the news pages of both our local weekly paper in Exeter and the daily national newspaper and wonder whether any of the news stories relates to our discipline.  Last week the local paper (Express and Echo) had three headlines over such stories. 

Number one read "Advice leads to improved efficiency" and was about a scheme to advise companies about reducing their costs and carbon footprint.  The story dealt with a marketing advice company which had received such advice - resulting in a reduction in carbon footprint of 4tonnes per year and cost savings of £600 per year.  Obviously, financial and energy models had been constructed, and someone had identified areas for decision and choice - ideal for OR. 

Number two read "Flybe call centre jobs outsourced" describing how the airline Flybe, whose HQ is in Exeter, had decided to outsource its call centre.  There's a wealth of research in the OR literature about call centre modelling, and I suspect that the company which now handles the airline's calls uses some OR in its operation.  But, once again, the management of Flybe had faced a choice: outsource (and to whom?) or keep in house.  A financial model would link to queue models for the systems.  But there would also be the psychology of keeping a personal link between the telephone operators who had formerly been company employees, and the new, slightly remote, association between the call centre and the company. 

Number three read "Mole Valley's robust year", describing a successful year for Mole Valley, a local agricultural supplies business, which is run as a co-operative.  The business had been profitable, and the short report mentioned "improved processes" and "efficiencies" achieved during the year.  How much were these a result of detailed modelling?  Or suggestions from staff, even those who know nothing about the technicalities of OR can see opportunities for beneficial changes.

It would be an interesting exercise for an educator in OR to take a similar business page and ask students where they could apply OR.  Should I copyright the idea?

Thursday, 10 January 2013

Ulcers and wheelchairs

From time to time I have written about the problems of defining the extent of the "system" that is being studied and modelled in an OR study.  The mantra that was instilled in me as a student and which was reinforced throughout my professional career is this: "Do you want to optimise your part of the system, or the whole system?"  All too often, optimising part of a system is wasteful and conflicts with the needs of the larger system.

Today, a chance conversation gave me another instance of this.  A friend was describing the work that his wife does with those who need wheelchairs, whether because of age or long-term illness.  I mentioned that my late father, a six-footer who needed a wheelchair after two strokes, had been given a chair with a deeper seat and higher back after several months suffering in a standard wheelchair.  The conversation developed, and I discovered that there is a move to restrict provision of wheelchairs to an extremely limited range of sizes.  Somebody is optimising a part of the system, because a limited range gives economies of manufacturing scale.  However, provision of wheelchairs is about people, not economies of scale.  And, if wheelchairs are only available in limited sizes, people suffer, and ulcers are a common problem for people in poorly fitting wheelchairs.  So saving money by restricting the variety of size and shape of wheelchairs puts more burden on health care providers and hospitals, so another part of the system suffers. 

I pointed out to my friend that this was a common situation, and mentioned the mantra of the part versus the whole.  He knew that I was interested in the maths and statistics of everyday life, and told me that I could describe the situation in my blog.

But, my friend went on, there are further aspects to the system.  He drew my attention to another one which he was aware of.  If you can provide high-tech wheelchairs to people, specifically the kind which raise the user from seated to standing, then those users can use work-surfaces and kitchen appliances, which gives them extra independence.  And, those users do not need so much domestic support in their homes, thus saving money in another part of the health care and social services system.   (There wasn't time to discuss further conflicts between managing the provision of wheelchairs and managing the care system for those who need wheelchairs.) 

And his final comment was salutary; if you are working in a system like this, and point out a solution to the conflict between managing your part of the system and giving efficient management to the whole system, then you run the risk of doing yourself out of a job because your part may not need your kind of leadership.  So what is optimal for you (keeping your job?) may not be optimal for the whole system.

Wednesday, 9 January 2013

Cash or card to pay with?

Nearly four years ago, in my old blog, I mentioned the design of self-service checkouts at supermarkets.  (See <a href="http://iaoreditor.blogspot.co.uk/2009/03/coin-machine-problem.html">this</a>.)  In Exeter we have a new twist to the design of supermarket self-service checkouts, and I was pondering the modelling that has gone into the design of this system.

In our local Waitrose supermarket, there are several conventional checkouts, which are staffed according to demand.  One or two further ones are open to customers with one basket.  A third option is to take a scanner which you use as you go round the store, and then pay at a checkout dedicated to such machines.  It is the fourth option whose modelling I was thinking about.  Here are three self-service tills, but the only way to pay is by card, either credit or debit. 

So, the modelling has come up with the need for these machines (as opposed to ones taking coins) and for three of these machines.  On what basis?

First, the space constraint.  These three fit into a similar space to that occupied by a conventional checkout.  So, the choice is between three and six.

Second, the capital cost.  Presumably, machines which do not need coins are cheaper to make. 

Third, the day-to-day running cost.  These machines do not need to be refilled with coins, and because they do not have the mechanical parts for coin collection and return, are less likely to break down.

Fourth, the financial running cost.  The supermarket pays fees for card transactions, so the modelling must include these.  Against this, the supermarket would be paying for cash transactions at its bank, so is saving these charges.

Fifth, human behaviour.  Presumably, like other stores, the supermarket has collected data about the number of card transactions and the distribution of the size of these, and also the number of cash transactions and the distribution of their size.  Since the store is part of a national chain, there will be data about these transactions on such machines where they had been introduced before our local store opened.

What I would find particularly interesting is to know the extent to which the presence of these machines has changed human behaviour.  There are several types of customer to consider.  Some people will pay by card at any type of check-out, irrespective of the total amount of the purchase.  (I am almost in that category, though I do use cash on self-service machines from time to time for very small purchases.  It may be inconsistent, but I don't use a card when making small purchases with independent traders, who generally pay a higher charge for card transactions than do the multi-branch supermarkets.)  Some people will use a check-out with a human cashier every time they shop.  Some people will decide which check-out to use depending on the amount purchased (self-service tills have a small area for packing bags, and a conventional till has advantages in such cases).  But there must be a category of shopper whose behaviour has been modified by these card-only machines.  How many people are willing to use a self-service machine, would prefer to pay by cash when they did so, but change to a card in this situation? 

And having asked the questions, I wonder how they collected the data.  And do the statistics change with time, either as a trend or with seasonality? 

Once again, I realise that you need to include psychology of behaviour in the mathematical and financial OR model.

Monday, 7 January 2013

The house price algorithm - a little too simple?

One consequence of the recession is that advertisers are very keen to get business. Here in Exeter, we receive several leaflets each week from local businesses, trying to get our business, especially in the service sector. We could have a different business or individual to clean our house every day for a month, have our garden redesigned every month, have someone do the ironing, clean the stove or shampoo the pets. And the deliveries include several magazines, which combine syndicated articles with local adverts. Today's blog is prompted by a piece in one of these magazines, which used the word "algorithm" in the opening sentence. (How many people read no further?) Suppose you want to buy a house in Exeter. You collect information from the estate agents, either in person or online. You find a house that you like. Let's say it has an asking price of £250,000. Before committing yourself, you log in to a property valuation website - and one is the dominant player in this online business, and find that it sold for £200,000 four years ago, and the property valuation website gives an estimate of £220,000 for it. So what do you think about the price? The piece in the magazine suggested that this is a frequent problem, and is a consequence of too much transparency, supported by a poor algorithm. That price of £200,000 is a single number; it conceals a great deal about the house when it was bought at that price, why it was for sale, what state it was in, and numerous other pieces of information. If it was a new house, the builder may have offered special deals for purchasers at the start of a new development, or at other times to help cash flow. It it had been an older house, what state was it in when it was sold? Did it need a lot of repair, leading to a low asking price? Was it sold to clear a debt? Was it sold in a hurry, accepting a low offer to get the property sold as quickly as possible? So what is to be done about the difference between £250,000 and £220,000? You, as buyer, wonder whether you should offer to buy at a price nearer to £220,000 than the higher one. The vendor feels that the website is misleading; so does the vendor's agent, who proposed the higher price. And it all follows because the property valuation website has used a naive algorithm to achieve the figure of £220,000. Their algorithm is a simple forecasting model based on quite sparse data. They do not have the sales price for a particular property every year. People do not move house that often. So they collect prices for a small neigbourhood, and prices for similar sized properties in a wider area, and generate their expected increase in value as a percentage by a suitable combination of these two datasets. But each house is individual, and the two surrogates (small neighbourhood, similar properties) do not give a very good correspondence to what happens to the house that is for sale. One could forbid such property valuation websites - but that would be pointless. Or the property valuation website could make a very clear statement about the difficulty of forecasting (even to giving a range of values). Or, perhaps most important, improve the algorithm. I wonder where there are other algorithms whose use is potentially unhelpful?