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