Thursday, 19 March 2015

Lake control at Te Anau

Sign by Lake Te Anau

Dealing with multiple, conflicting, objectives is part of operational research.  I have written earlier about the Noah and Joseph problem and the conflicting objectives there.

When we were on holiday, I saw this sign on the bank of Lake Te Anau, in southern New Zealand.  The text is worth recording, as it describes control rules and the conflicting objectives.

Lake Levels
A Government appointed body, The Guardians of Lakes Manapouri, Monowai and Te Anau" ensures that the lakes are managed within their natural levels.
A complex set of guidelines determines how long a lake can be held at a certain level.
It it is too high for too long shoreline vegetation may 'drown'.
If it is too low for too long beaches are prone to sand and gravel loss and slumping.
The rate at which the lake level is lowered is also controlled. but weather determines how fast it rises.
The higher the lake level peaks above this mark (202.7 metres above sea level) the longer it is before the lake is allowed that high again.
for example, if levels reach 202.7 for up to 125 days, recurrence is prevented for another 20 days but if levels go higher to 204.3 even for just 1 day recurrence is prevented for 100 days (this in the high operating range).
As the lake lowers below this mark (201.5) fewer days can be spent at each level (this in the low operating range)

notes at the side read 
Aquatic plants are protected from drying by the lake level guidelines
Vegetation above mean lake level is protected from drowning and shoreline erosion

It is notable that the range of allowable lake levels is only 1.2 metres (4 feet)

Just stop and think about the modelling behind these rules.  Engineering (for the water release and control) meets biology (how long does it take to drown a plant, how long for it to dry out) meets geology (gravel loss) meets hydrology (modelling the lake levels) meets meteorology (rainfall) meets mathematics and operational research.  It is multidisciplinary, in the way that the best O.R. should be!  Well done!

Thursday, 12 March 2015

Hidden queues

Tina and I holidayed in New Zealand in February.  While there, we noticed several warning signs, like this:
Sign by a New Zealand road
How perceptive!  There are hidden queues in many everyday systems.

Podcast about queues

The BBC radio programme, The Bottom Line, on 26th February 2015 was devoted to the science, psychology and management of queues.  Podcast here.

Well worth hearing.

One of the three speakers is Jeff Griffiths, a leading member of the Operational Research Society

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!