Monday, 12 January 2015

Collecting goods for a charity

February's issue of the Journal of the Operational Research Society (JORS) opens with a case study about collecting items for a charity in the UK.  Items have to be collected from the charity's shops and from large collection bins.  The aim of the work was to find the best routes for the collecting vehicles, subject to a variety of constraints on travel times, collection windows and vehicle capacity. 

The paper, Matheuristics for solving a multi-attribute collection problem for a charity organisation by Güneş Erdoğan, Fraser McLeod, Tom Cherrett & Tolga Bektaş (JORS (2015) vol 66 issue 2, p177-190) gives a mathematical programming formulation for the problem discusses where it fits into the canon of problems related to the travelling salesman problem.  They model and solve the problem by Matheuristics and give results for simulated runs of the model, using data from the charity.

(Matheuristics are, according to the paper, combinations of metaheuristics and exact optimization methods, giving the diversification ability of metaheuristics and the intensification ability of exact methods.  It was not a term that I had met before - go on learning, even when retired!)

I enjoyed the paper, because it tackles a real-life problem with messy constraints, models it well enough for the solution to be useful, and is realistic about the assumptions that are made.  Well worth reading!

Wednesday, 7 January 2015

Making postal collections

Something curious happened towards the end of 2014.  We are fortunate that there is a letter box at the end of our road, about 100 metres from our house.  For non-UK readers, mail is collected by Royal Mail vans from letter boxes, taken to a central sorting office and sent to its destination.  Letter boxes are emptied at some time every day except Sundays.  There is a sheet on the front of the box to indicate the time when the box will be emptied.

Until quite recently, "our" box was emptied (according to the sheet on the front) at 6:30pm daily, except for Saturdays when it was emptied at 12:30pm.  Then, the sheet was changed.  It now reads 9:00am daily and 7:00am on Saturdays.  This sudden change caught us by surprise.  A note on the sheet says that there is a later daily collection at our hospital, about ten minutes' walk away, at 4pm.  There is a general caveat that the box may be emptied later than these times.

We looked at another letter box nearby; its sheet had been changed in the same way.  So I went onto the Royal Mail website and discovered that this has been part of a nationwide change of procedure.  Mail in the UK is now going to be collected from many letter boxes at the same time as it is delivered in local roads.  In other words, the vehicle used for delivering the mail will also take mail away from the boxes where this change has occurred.  This was normal practice for many rural letterboxes - and often people in the countryside would leave their mail at the door for the deliveryman (postman in the UK) to take away, though this was never official procedure. 

The website went on to explain that letter boxes such as the two that we looked at have been judged to have low usage.  Across the country, all such boxes will now be emptied by the delivery vehicle.  This will save costs, but I doubt whether the price of mail will fall as a result.  The website also mentioned a survey of users of the mail who were content with such a change. 

It looks as if there has been some O.R. modelling here.  Someone has looked at the marginal cost of collecting mail from a box which only has a small number of letters and asked the question "What if? ... What if we did away with that box in the late collection?"  And the conclusion is that sending one vehicle to the letter box near my house during the day is cheaper than sending two. 

Now, what about the user's perspective?  Only a very few of the letters that I send in the 21st century are time critical.  Nearly all of them can be prepared and posted one day earlier than would have been my practice before the change.  And that is probably true for most of the people who use that letter box.  However, I may need - occasionally - to write a letter and post it the same day so as to be in the mail by the evening.  And here is where the O.R. has slipped up.  The letter box at the hospital is probably the nearest to me with an afternoon collection, but it is not the most convenient to use.  The "What if?" study hasn't fully explored the "What will users do if they want to catch an afternoon  collection?"  They will not necessarily go to the closest letter box with such a collection; they will probably behave in a different way.  And for the local letter box, they will go:
 (1) where they can park easily (the hospital car park is generally very full, there are high parking charges, and the area is patrolled so that the risk of being fined for parking without paying the charge is quite high);
(2) where they can combine posting mail with another errand, e.g. shopping.  (I don't need to go to the hospital at the same time as posting mail)

So, dear friends doing O.R. for Royal Mail, when the sheets of collection times are being prepared, ask postmen with local knowledge about the accessibility and advantages of several local letter boxes, and list more than one on the information sheet.  After all, O.R. is not just about the mathematics of vehicle routing, not just about the economics and costing of a scheme, not just about statistics of performance, but also about the psychology and behaviour of all those affected. 

Thursday, 1 January 2015

Sat-navs, 2048, and what does operational research have to do with them?

Last year I wrote a blog about 2048, the addictive game which came online then, which has spawned apps for Android and iOS, and has led to discussion about using artificial intelligence (AI) to play online games.  As that blog has had numerous hits, I felt that it was worth returning to the topic.

First, a paragraph about operational research (O.R. or operations research or management science). O.R. is the science of decision making, the science of making management better, the science of asking "What's best?" and answering it, or the science of asking "What happens if a change is made?".  Some people say that O.R. is the hidden science, because nobody has heard of it - but it is used by almost every company on every stock exchange in the world, by public utilities, by governments and charities.  O.R. is the science that ensures that there is a mast in the right place and with the right frequencies for your mobile phone.  It is the science that determines the price for your next train or plane ticket.  It is the science that routes your eBay purchase from vendor to you.  It is the science that stocks up your supermarket with ice-cream before a hot weekend.  And much else.  (Yes, I am an enthusiast - but I have seen how O.R. helps managers and workers, customers and passengers.)

The ideas which give simple rules for playing the game 2048 well are rather like the rules which are programmed into your sat-nav or route-finder on your tablet or computer.  The most important underlying principle for playing the game well is to choose a corner and aim to get the cell with the largest value on the grid "stuck" in that corner.  Then the cell with the next largest value should be adjacent, along one edge, the next largest adjacent to that and when an edge is filled up, those cells form an edge for the rest of the game.  I choose the lower right-hand corner, and that means that I use the "down" and "right" buttons for as long as I can.  Those two are my preferred moves.  When I can't use one of these, then I am forced to use "up" or "left" - because I stack my cells on the right hand edge, I do not use "left" unless I really, really have to.  (And almost invariably, this means that my game is in trouble.)

So, what are the parallels between playing the game and the sat-nav?

Both have an objective;
2048: to get a cell with value 2048 (or higher)
sat-nav: to get to the destination on the best route possible.

Both break achieving that objective into a series of manageable steps;
2048: each movement of squares is a step in the game; you make a decision about what to do after each movement;
sat-nav: the route is broken into steps at each road junction; (in theory) the program makes a decision about which route to take at each one.

Both work with extremely simple rules:
2048: keep the cell with the largest value in a corner (and the rest in an ordered pattern)
sat-nav: choose the best route to the destination from each road junction.  (This is a rule which is sometimes known as Bellman's Principle, after an American scientist - who I would have liked to have met - Richard Bellman.  He put into mathematics an idea which is simple and should be obvious.  If the best route from A to C goes through B, then the best route from A to C is made up of the best route from A to B followed by the best route from B to C.  This is useful, because it saves the sat-nav computer calculating routes over and over and over again.)

Both need to deal with the situation when things go wrong:
2048: it may be bad luck, or you may have made a mistake (which is why some versions of 2048 now include the facility to "undo" moves)
sat-nav: the driver may miss a turning, or there may be a blockage

So, when things go wrong, the objective may be changed temporarily:
2048: try and put it right, while keeping the structure of the cells as "tidy" as possible (and "Tidiness" will depend on what went wrong.)
sat-nav: either recalculate the whole route - so the objective becomes the best route from wherever you have got to, or make the objective that of getting back on the right route as soon as possible

Both look several steps ahead:
2048: although the game has a random element, it is still possible to look a few steps ahead and make choices of your preferred moves accordingly
sat-nav: looking ahead means that the direction is not always pointing towards the destination - it may be better to choose a faster road than to head in the compass direction.  (I sometimes explained to students that the motorway system in the UK meant that some sat-nav optimal routes would take the driver along three sides of a square, seen on a map, simply because there was no good direct road.)

And what is this to do with O.R.?  Simple; rules for sat-navs have been developed by people with expertise in one branch of O.R..  It's the hidden science in the electronics, or in the app on your tablet or phone.  So when you are playing 2048, you are actually doing O.R.!  And if you want to know more, contact one of the many O.R. societies in the world - such as the UK Operational Research Society, or the American INFORMS

Monday, 29 December 2014

Complexity Theory - a Tool for Operational Research?

From time to time, I come across a book which I would have liked to have read and had on my academic bookshelves years ago.  Here is one.  It is Neil Johnson's book on complexity theory, which is published under two titles:  the copy that has come from a UK library has the title: Two's Company, Three is Complexity: a simple guide to the science of all sciences, but Amazon has a similar book:
Simple Complexity.

There is comparatively little about Complexity Theory, as Johnson defines it, in the O.R. literature.  Type "complexity" into International Abstracts in O.R. and you come up with analyses of the complexity of various algorithms, and a very few references to complexity theory in the sense of the book.  But Johnson is writing about the complexity of large systems, and so it overlaps with systems theory in O.R., with knowledge management, and with agent-based simulation (among others).  

Johnson comes from a background in physics, but his work links to the work of others in traffic modelling, conflict analysis, epidemiology, financial modelling, and much else.

In this book, Johnson defines the key components of complexity and complex systems as follows:
  • The system contains a collection of many interacting objects or "agents"
  • These objects' behaviour is affected by memory or "feedback"
  • The objects can adapt their strategies according to their history
  • The system is typically "open"
  • The system exhibits emergent phenomena which are generally surprising, and may be extreme
  • The emergent phenomena typically arise in the absence of any sort of "invisible hand" or central controller
  • The system shows a complicated mix of ordered and disordered behaviour

Other entries in this blog have mentioned the need in O.R. for the analyst to define the extent of the system being considered in a project.  Learning about complexity theory from the book has emphasised the importance of that.  I thought of two linked studies that I did; the first involving the long-term strategy for managing some water resources, and the second with the hour-by-hour management of part of those resources.  In the first part, we assumed that there were good rules for the hour-by-hour management, and for the latter we used the long-term results as a constraint on the control policies.  But throughout these two studies, we were aware that the interaction of the two models needed much more refining - but we lacked the data and computing power to do it.  One system had a time horizon of years, the other, used models with a horizon of a few hours.  The two time scales differed by several orders of magnitude.  We might have made progress by introducing some concepts and techniques from complexity theory.    

In another study, we looked at the deployment of patrol vehicles along a motorway; there was a "basic" policy for assigning them.  But as soon as those vehicles were being "used", their deployment needed active human intervention.  Traffic on the motorway, and the patrols, created a complex system which matched the list of components above.  

My recent blog about supermarket shopping in the run-up to Christmas touched on some aspects of the complexity of human beings going shopping!

Johnson's work on financial models overlaps with some models in O.R.  What I found especially interesting was the discussion of time series analysis ... there was a lot of material which deserved a place in an O.R. module about forecasting.

The one gap in the book for me was how to use some of the models to do what O.R. people do - answer questions "What happens if?"  The models work to describe real-life phenomena, but don't always offer opportunities for studying the effects of change through management decision-making.   There's scope for a follow-up book.  When I looked in the International Abstracts in O.R, one abstract was for a paper which covered some of this, and the abstract claimed that the paper would be the first of two papers.  I can't find the second paper!

All in all, if you are doing O.R., and you want to learn a little about how complexity science is modelling systems which are of interest to O.R (and many of us ought to have done this a few years ago!), have a look at this introduction!

Wednesday, 24 December 2014

When did you do your Christmas food shopping this year?

According to one of Britain's leading supermarket chains, Morrisons, the optimum time to go shopping for perishable food for Christmas was in a window between 6:30am and 7:30am on December 23rd. 

This suggestion was the result of some analysis of footfall at stores, and also used arguments about the freshness of perishable foods.  Because the stores receive deliveries in the small hours, and the fresh deliveries are stacked on the shelves early in the day, the early shoppers will have fresh goods, and there will be a large number of assistants working in the shop to help customers.  Also, footfall statistics show that this hour is not a popular time for shopping, so there will be fewer customers to battle with. 

As the result was announced in the news media the previous day, one wonders how many people changed their behaviour and did their food shopping in that time window this year.  I don't know if enough people did so to make the time non-optimal. 

I confess that I did consider suggesting to Tina that we might change our plans ...

But we did observe an interesting phenomenon when we turned up at our nearest supermarket where we planned to use a discount voucher before it expired.  It was 10am, and the car park was full.  All the checkouts were busy.  It took us about 45 minutes to complete our shopping, and by then the queues at the checkouts had almost gone, and the car park had plenty of space.  We concluded that many people had set out to shop in the 9am to 10am window ... maybe the rush had started earlier, but the observation of our shopping time, the queues and congestion suggested that many shoppers were coming first thing after breakfast.  (We felt smug, as we had been swimming for nearly an hour first thing after breakfast, before shopping.)  So, maybe there is another good window for shopping if you arrive at about 10:30am?

And, late this afternoon, after the crib service at church, we cycled to the same store, on the lookout for bargains at the end of the trading day.  (Yes, we did find some food that had been reduced in price.)  We had expected that most customers would have finished their purchasing, but it wasn't so.  There were queues for the car park, and busy checkouts.  It was busier than in the last two years, when we have also wandered up after the crib service, seeking bargains.  (Even the cycle racks were full.) 

Modelling customer demand for this supermarket would be interesting.  We got the impression that customers have been adapting the time when they shop - in response to their own and other people's experience?  If so, how does a modeller make forecasts?  It is a reminder that operational research modelling that involves people and their actions needs to acknowledge the complexity of people's psychology.  As is often the case, modelling humans is much more complex than modelling machines!

Saturday, 20 December 2014

A Christmas tipple, statistically

Did you know that half Britain's adults have their first glass of wine on Christmas Day at 1:12pm?  It must be true - it is in a newspaper!

Leaving aside the silliness of recording such an item of data (I can't tell you to the nearest minute what time today I had any drinks, and I doubt if many of the readers of this can either), there is the interpretation of the data.  I suspect that what was meant was

half Britain's adults have started their first glass of wine on Christmas Day by at 1:12pm soon after 1pm

Cheers!  And Happy Christmas!

Everyday heuristics

Fifty-six years ago, a paper appeared in Operations Research (vol 6, p1-10) with the title: "Heuristic Problem Solving: The Next Advance in Operations Research".  Written by Herbert A. Simon and Allen Newell, it daringly proposed advances in the power of computers to solve problems by heuristic methods, and not by purely algorithmic methods.  It caused a flurry of discussion in the correspondence section of the journal. 

Since then, we have become accustomed to the use of heuristic methods as part of the tool-kit of O.R.  But we do not have one heuristic method for problem solving - we have many.  Some of them have developed into the well-established metaheuristics of simulated annealing, tabu search, genetic algorithms, ant-based algorithms, and many others.  A glance at the content pages of our journals, or (even better since it classifies papers) through the index of the International Abstracts in O.R., will show how often heuristics have been used to advantage in the "Science of Better".  Of course, heuristics are for finding "better" rather than "optimum", although there are many situations where the heuristics do find an optimum.

But it is salutary to look at the frequency of heuristics in the equipment we use in everyday life.  Usually the heuristic is hidden in some computer chip or electronic circuitry, and only by stopping to think about it do we recognise that someone, somewhere, has realised that a heuristic is needed and has programmed it.  One of the earliest papers on heuristics that I ever read (and I can't find a reference to it - any suggestions?) gave a list of simple, everyday heuristics.  "Use an old golf ball when there is water hazard".  "Order a new chequebook when you reach the reminder slip in your present one" and so on.  The second of these examples is now outdated with my bank; the bank's computer has a heuristic which recognises when I am nearing the end of the chequebook, and issues a new one without my need to remind the bank.  I wonder whether the heuristic also has a parameter based on the average number of cheques that I write each month.  So there is a heuristic that affects my life.  

What about others?  We replaced our old car with a newer model a few months ago.  This one has several heuristics built into its control electronics.  With the headlights set to an automatic setting, the lights come on when a sensor detects the ambient light levels to be too low.  That is wonderful - except that the headlights come on when we drive the car into or out of the garage.  They also come on in some Devon lanes, when the hedges or banks create a dark canyon.  The heuristic is good, but it isn't optimal.  The car has sensors for the drag on the windscreen wipers, so adjusts the sweep if there is light rain.  That heuristic can be disconcerting, if, like us, you are used to regular sweeps of the wipers.

The kitchen is another place where everyday life encounters heuristics.  The freezer pump switches on when it detects an internal temperature which is too high - but it is not so sensitive that it will switch on immediately the door is opened.  The oven has a thermostat which controls the heating elements and fan - according to a simple heuristic.  I was surprised to see an advert for an oven which claimed that it could be controlled to an accuracy of one degree Celsius.  None of the recipes that I use require such excessive accuracy.

The radio tunes when there is a signal of sufficient strength.  The mobile phone operates with numerous heuristics.  

So are these heuristics that solve problems part of the breakthrough that Simon and Newell anticipated?  Yes.  They are parts of the hidden application of O.R. in twenty-first century life.  And there are many, many more.