Wednesday, 27 November 2013

Sequential decision making - on Maltese buses



One of my personal favourite "techniques" in O.R. is dynamic programming, both as a way of modelling problems, and because it can be a formal description of sequential decision making.  We were on holiday in Malta, when a situation arose which called for some interesting sequential thinking.
The island of Gozo is just north of Malta, and is the second inhabited island of the archipelago. A ferry runs every 45 minutes between the islands.  We wanted to go to Gozo for the day.  From our hotel, we could take bus 222, leaving at 7:45 and 8:15, scheduled to take 51 minutes to the ferry.  Or we could catch bus 12 for three stops and five minutes, at 8:02, to connect with the X1, a fast service.  We opted for the latter.  The X1 service was supposed to arrive a few minutes before the departure of the ferry.  Bus 12 was late, and reached the connection point at 8:12.  My timetable said that X1 left there at 8:15, but the timetable on the stop said it was due to leave at 8:12.  So, at this stage in our progress, we didn't know if the X1 had been or not.  Our only option was to wait and see.
One of Malta's buses
 Then we discovered that the bus stop had a display showing the estimated time of arrival of two buses.  We hadn't seen such a display before in Malta, so didn't know if this was updated on GPS data from the buses.  And the display showed the 222 and the X1.  The latter was due at 8:24, so we thought that it might make up time to connect with the ferry.  Then the X1 dropped off the display, because another bus service was on the display.  This was extra evidence that the data was being continuously updated.  But we faced a dilemma - what should we do when the 222 arrived?  Get on it, or wait?  We had evidence that the fast X1 was on its way, and were inclined to believe that the information was correct - maybe not to be sure, but enough to give us a strong belief in the information.  We knew that the 222 would miss the ferry, but didn't know if the connection between the X1 and the ferry was strong enough for the ferry to wait if the bus was a little late. 
So, we chose to wait.   
The Gozo ferry, returning from the island
And as the X1 drove into the ferry terminal, the 9:00am ferry went out. 
It was interesting to face the problem of the credibility of information, assorted bits of uncertainty, and a choice from which there was no turning back - once on a bus, we couldn't change.
Parallels with commercial O.R. are numerous, as decision-making proceeds over time, with varying amounts of information being available, and the credibility of that data needing to be assessed.   
And somebody in the island's bus services had decided that this bus stop should have data for the next two bus arrivals, not one, not three.  Again, another decision, which affected passengers.

Thursday, 14 November 2013

The power of analogy

It is often claimed that one of the greatest strengths of people in the operational research profession is that they can look at a practical problem and draw an analogy with a similar problem in another business or commercial enterprise.  (O.R. people have many strengths, so, if you are one, pat yourself on the back for the practical skills and strengths that you possess.)  The topic of queues is often given as an example of this power of drawing parallels - relating the problems of scheduling traffic lights to the problems of stocking infrequently used spare parts to the problems of staffing call centres.  But it applies in so many other areas as well - the design of rotas for bus drivers is the same sort of problem as making a plan for locating health clinics in a developing country. 

A couple of things came up earlier this year, which were vaguely related to one another, and where I felt that the skill of drawing parallels ought to have been used.  And, thinking about why the proposed solutions were less than ideal, I recalled a text-book which we sometimes used with undergraduate students and prospective students as preliminary reading.  It was the book "How to Solve it" by George Polya.  Polya was a polymath, but O.R. people probably know him best for that popular book, and  for his writing on problem solving in general.  He encouraged readers to use "The power of analogy" to help them approach and solve problems, whether they were mathematical or commercial.  Drawing an analogy and using the skill of recognising parallels between problems are the same kind of ability. 

(amusingly, a few days after recollecting Polya's "Power of analogy", I found a second-hand copy of "How to solve it" ... coincidences happen.)

These thoughts were triggered by two news stories.  In Devon, agriculture and tourism are major contributors to the county's economy.  We have a benign climate, which is good for both.  However, tourism depends on people wanting to travel to this part of the UK, rather than any other destination.  So there must be something to attract them.  And, within the county, there is naturally some competition and rivalry between different areas.  So, inevitably, those involved in the tourism industry try to develop Unique Selling Points (USPs) for their locality. 

Anyway, investors from two towns in the county made proposals for spending money on new developments.  One proposed a land train through the town; the other proposed moving a theatre from its site on the shore to a man-made island.  In each case, the proponents claimed that these developments would lead to USPs for the locality. 

But, suppose we use the power of analogy.  Why do you choose a holiday destination?  Would I go to a place simply because it possessed a theatre on an island, or a land train?  Those were the questions that the proponents should have asked.  Do you choose town A over town B because it has a land train through the town?  A few people might do so, but the majority would simply accept it as a small piece of the holiday mixture.  And some extra people might go to town C because it would be exciting to go to a theatre on an island, but the marginal increase in tourism is likely to be slight.  The proposers should have drawn an analogy with their own holiday habits.  "Would I go to a place simply because ...?" is the analogy question. 

Now, I am not despising investment in tourism.  But changing one thing in a locality is not going to change the holiday-maker's attitude towards that place very much.  Investment, in a mixture of facilities, may boost tourism by changing the attitudes of potential visitors, but the decision-makers need to step back, draw analogies with their own attitudes, and decide whether spending money on local facilities will affect the perception held by potential visitors. 

And I recall the failure of Exeter's Maritime Museum.  It was a very nice place, with many interesting boats to see, laid out reasonably well.  But it didn't draw enough visitors to thrive.  Why not?  It was a little way away from the city centre, the principal USP for the city.  And many holiday-makers in Devon come to Exeter when the weather is wet, so they can't go to the beach or the moors.  And walking round a museum which is partly out-of-doors on a wet day is not attractive. 

Friday, 1 November 2013

An optimisation problem with letters

Browsing in a local craft shop the other day, I spotted this sheet of rub-down letters.  I happened to have a camera with me.

Letters for card making and other craftwork


Several aspects of this sheet are interesting.  First, the designer has not taken any account of the frequency of appearance of different letters in the English language.  There are two of each letter, numeral and symbol, except there are three "I"s and one "?".  Purchasers are going to have a lot of waste, unless they create cards with pangrams such as "Cwm fjord bank glyphs vext quiz".  You can't write "Happy birthday David" with the selection here.

Second, there has been a slight attempt to optimise the packing of letters; look at the inverted "A" and "7" which mean that the two examples of these are closer together than if both were upright.  But, if this was a genuine attempt to pack the letters, why not use the same idea to pack the "J", "L" and "W".  Possibly also the "Y", "V" and "T"? 

Third, why is it necessary to keep the letters in strict alphabetical order?  One could imagine a layout with the letters packed more tightly if the designer could deviate slightly from strict order, as has been done with the letter"I"

Fourth, what is the constraint here?  Is it the size of sheet?  Was the designer told to pack the letters onto a given size sheet, and make the letters as large as possible while supplying two complete alphabets?  Or was the designer given the size of the letters, and told to pack them onto as small a sheet as possible?  I suspect that the sheets are of a standard size, so that the letters have been made as large as possible.

Starting from 1959, before personal computers, a company called Letraset made rub-down letters and symbols which were used by designers, magazine editors, artists, engineers and architects.  Their sheets had different numbers of the letters.

A sample of Letraset 


Again, these sheets were of standard sizes, so the number of letters and symbols was optimised for each point size; it would be interesting to know how the numbers were chosen.  I remember that as teenage schoolboys, we enjoyed collecting the give-away samples of Letraset from a local stationery shop.

O.R. has contributed several algorithms for packing objects; I wonder whether they have reached designers of craft materials?