Friday, 18 November 2016

A thought-provoking day

Yesterday I made the long return day trip from Exeter to London (for non-UK readers, it is a 3-hour rail journey each way, so a day trip means at least six hours in trains).  I wanted to attend the Operational Research Society's annual Blackett lecture.  This year Professor Andrew Blake from the Alan Turing Institute spoke on "Machines that learn: big data or explanatory models".  It was a stimulating lecture, and it was good to see many old friends (sadly, old is appropriate, as most of my friends are retired or close to that age).
One of the side benefits of a trip to London is to observe life and the changes in the capital.  I picked up a copy of the free evening newspaper, the Evening Standard.  Maybe someone should do an O.R. study of the advantages of a free newspaper, paid for by the advertisers, and determine the critical number of copies when another city might offer a daily, local free newspaper.  There was a fascinating article about an anaerobic digestion plant that processes 54,000 tonnes of London's food waste each year.  You can read the article here.  A few years ago, I wrote about meeting the owner of a local digestion plant (article here) and discussed some of the O.R. aspects of running such a business.  I also commented that O.R. is not well suited to start-up businesses.  The article in the Evening Standard commented that the business had started very small and had grown rapidly.  Would O.R. have helped? 

Mr Killoughery, the chief executive, is a qualified accountant and engineer who joined the family business recycling building materials when he was 26. Seven years ago he saw the writing on the wall for landfill and decided to go it alone and branch into food waste.
“I bought one truck and began collecting food waste from local schools,” he said. “Since then, the Government’s landfill tax escalator has caused the price of landfill to rocket from £20 to £100 a tonne and Bio Collectors has expanded on the back of it to 30 trucks.”

Sunday, 13 November 2016

Silly statistics, to be taken with a very large pinch of salt.

The headline reads: "UK food goes global", and the story went on to tell the readers that "a new study reveals that in 2016 most people consume twice as much international food as traditional British dishes".
Read on, and you find some amazing deductions from a survey of 2000 people, commissioned by a restaurant chain whose philosophy is to introduce diners to international flavours.  Their set menu for evenings starts with: Salt & Pepper Squid, or  Tacos locos, or  Halloumi skewers, or World breads.  Nothing there that is a "traditional British dish", so it is not surprising that the spokesperson for the restaurants said "At our restaurants, we've noticed an ever-increasing hunger for dishes from further afield".
I haven't been able to find the survey questions.  So I don't know which traditional English dishes were compared with which international food.  Would roast lamb served with rice be British or international?  What would curry and chips count as?  If they are both "international food" because my grandparents would not have eaten such dishes, then the finding in the first paragraph could be a reasonable deduction from a survey.
But the report went on, and I did wonder whether the writer had really engaged his or her brain with  what was being reported: "The average person will eat 2079 American meals, 1890 Indian dishes and 1701 Chinese meals in their lifetime".  2079, not "about 2100", please note.  How do you measure that from a survey?  It is a Gee-Whizz statistic.  Take some dubious data, extrapolate it far beyond what is reasonable, and present it as an accurate fact.  Incidentally, what is the significance of distinguishing between "meals" and "dishes"?  And Italian food is even more popular than American meals, according to the survey.  
I'd better stop; it's time to eat.  We'll start with Bean sprout soup (Indian) with a flatbread (Middle East), go on to Lemon chicken (Chinese/Thai), Baked potatoes (are they English - or an import from America 400 years ago?), Sweetcorn (US), and end with Tiramasu (Italian) with French white wine, Port (Portuguese) and a cup of tea (we like a Kenyan blend).  (oh, and we'd better have more meals like this, or we won't be average)

Tuesday, 8 November 2016

Parking Permit Problems

Exeter, like many cities and towns, has a parking problem.  There are many streets which have no provision for off-street parking for residents and businesses.  Some were built in the 19th century, before cars, others date from the 20th century and the houses were built on false assumptions; either that local people would not have cars, or, in many parts of the city, the houses were planned when cars were smaller.  (The latter is seen in at least two ways; the plots for garages were made the wrong size; houses were built too close together and the garages were built behind the houses.)  And increasingly, households own more than one car.  So many people park their cars on the roads outside their homes.
However, if this parking is not regulated, chaos may follow.  If the streets are close to places of work, then commuters may try to park there.  Often there is not enough space in a street for every house to have one parking space, let alone have space for more than one.
So, residents in many streets obtain parking permits.  These allow the car to be parked anywhere within a zone around the owner's home, generally including the street in front of their home (but not always, because it may be a major traffic route).  Exeter has several zones, and cars may only have a resident's permit for one.  Business users may have permits for some vehicles, and there is a category of "essential visitors" as well. 
The operational research problem is the establishment of the zones.  It is not like the problem of establishing wards for elections, since not all streets need to be allocated to a zone; there may be sufficient parking in a residential area so that no restrictions are needed.  The zones do not overlap, so one could pose the problem as one of dividing the whole city into parking permit zones and the rest.  If you did that, the "rest" might be quite hard to define - it seems better to simply say that the problem is of defining zones for parking.    A zone must be contiguous, have natural boundaries, be easy to define, and must be "fair" to residents and businesses.  And it must not be too large.  (A large zone could lead to people commuting from one side (home) to the other (work or shops or transport hub) especially if the zone touches areas of business or commerce.)    So there are multiple objectives to be satisfied. 
One approach would be to create one zone at a time.  It might not be optimal, but it might give a "good enough" solution.  Heuristic methods can be pretty good!
All over the city, such zones have been set up.  Generally, people are happy with them, even though you have to pay for the privilege of parking outside your own house, or as near as you can find a space.
However, changing the zones can be controversial.  Recently, the city has added new zones where there was unrestricted (read "free for all") in the past.  Not everyone was happy, because it was necessary to draw boundaries where the residents were in the former habit (of necessity) of parking in one of several nearby streets, and these were now in different zones.  But the council does not issue two permits for one vehicle. 
So, here is a practical problem.  I have suggested one solution method.  Is there a better one?

Saturday, 5 November 2016

Thoughts on fleet management

It happens to all of us in Operational Research; we are asked what we do.  Sometimes I explain that I used to teach mathematics students at the university, and then add "I used to do the interesting bits of mathematics".  I mean no disrespect to my colleagues; it is simply that to non-mathematicians, the fact that somebody forecasts the demand for peanut butter in the supermarket, or ensures that there are enough hire cars at the airport, or that there is enough coverage for mobile phone signals - that is interesting mathematics.

The other day I met an enthusiast.  His job was to drive delivery vehicles for a big local company, and he had come into Exeter to promote the company's chosen charity for the year.  And he had a 40 ton vehicle with him, emblazoned with the name of the charity.  Exeter normally only allows such vehicles into the city to make deliveries and only on certain roads.  So I rarely see one close up.  Anyhow, he was happy to talk to passers-by and as most people were scurrying past without stopping, fearful (perhaps) that they might be approached to support the charity, I had the chance to spend ten minutes or so learning about his work and about the company's business. 

Operational Research has been involved with problems of fleet management in the past, but published papers tend to be very simplistic.  The reality for this business was much more complex than appears in the literature.  They had about 700 vehicles.  These were divided between two depots, one in the south and one in the north.  They vehicles were of several different types, and the one I was standing by was split into a frozen section and an ambient temperature section.  The company has regular contracts with certain clients, and short-term contracts for others - short-term might be for one load, or for a few to deal with fluctuations in the client's needs.

And so, I came away thinking about some aspects of decision-making for the management. 
  • When to replace or repair vehicles.
  • Purchasing policies.
  • Fleet mix decisions.
  • Location of the fleet.
  • Terms of each contract.
  • Whether to accept new contracts, long-term or short-term.
  • Assigning vehicles to loads.
  • Maintenance management.
  • Driver scheduling, training and hiring.
  • Vehicle routing
  • and so on ...

 It's enough to keep an O.R. person very busy indeed!

Tuesday, 1 November 2016

Combinatorial nail varnish

I begin with a confession.  Although the problem that follows can be represented as a combinatorial optimisation problem, I have not studied the literature about that problem.  However, I know that it is in the same class of difficulty as the Travelling Salesperson Problem (TSP), about which there is a vast literature.

The story begins when I went for a haircut.  My hairdresser subscribes to a service which delivers six to ten monthly magazines that will appeal to men - and, no, there are none of that kind, thank you very much!  His science magazine had a page of mathematics, and the theme was based on using nail varnish to represent binary digits on a hand.  Using your right hand, the smallest finger represents 0/1, then working to the left, the next is 0/2, then 0/4, 0/8 and 0/16.  So every number from 0 to 31 can be represented by the presence or absence of nail varnish (or having plain varnish and glitter) on the appropriate fingers in the binary expansion.  In particular, this means that any date in the month can be coded on you fingers.  

So, the maths writer Katie Steckles posted a video on YouTube about this process.  (look for Nail Varnish Tutorial - Binary numbers).  Then she posed the question:

Suppose I want to paint my nails on one hand differently every day for a month – so I need to use all 31 combinations involving glitter. Assuming that a nail painted with plain varnish can have glitter added, but a nail with glitter needs to be nail-varnish-removed before it can become a plain nail again, what order do I apply the different combinations so that you minimise the amount of nail varnish remover I’ll need to use?
(Obviously, the answer does not need to code the dates in order.)

Would you like to think about solving this before looking at the published answer.

In the hairdresser's, my initial thought was that this could be formulated as a combinatorial optimisation problem as follows: 
Let each of the 31 patterns be a node in a network.  Define the edge distance between two patterns as 1 if the only change needed is to paint the nails, and 10N when you need to remove the varnish from N nails.  Now the problem is to find a route through each of the 31 nodes to minimise the total distance.

This is not quite a TSP.  You don't need to return to the start.  So you might think that the way to solve Katie's problem is to find a solution to the TSP on these 31 nodes, and then delete the longest edge.  Yes, but ... there might be a longer TS tour with a longest edge so long that it gave a smaller solution to Katie's problem.  And that is why I know that the problem is in the same complexity class as the TSP.  

Now you can look at the solution, which is that she needs to remove varnish 13 times.  There is a very neat proof that this is the lower bound, and the web page shows how to achieve this theoretical minimum.

So here is the answer.

Now for a related, more general, problem: I wish to create a walking tour of M places.  I can choose to start at any one of them, and finish at any one of them.  The journey from home to the start and from the end to home does not count.  How can I find the shortest walking tour?  Dear reader, do you know what literature there is on this problem?

My thanks to for drawing this amusing problem to my attention.


Monday, 10 October 2016

The best angle for traffic light louvres

Certain traffic signals in the UK are covered with louvres so that the light in the signal is only visible when your eye is aligned with the gap between the louvres.  Not everyone is happy with them.  In an online discussion, I found the following explanation:
The proper use for the louvred aspects on signal heads is to avoid conflicting signals being displayed. For example, if you have a pedestrian crossing within a few yards of a signal controlled junction, if there is a chance that drivers may misread an aspect being shown on the pedestrian signals [green] as the aspect for the junction then the louvres are fitted to ensure that you only see it from a certain distance from the stop line. This is also the case for the pedestrian aspects as well if the phasing is not all the same and you have another button to push in the centre refuge. It may appear 'difficult' to see in some circumstances but it does avoid confusion as you are required to check you are on green before proceeding.
However, not all drivers were happy with the introduction of such louvres, because they were driving trucks and the angle of the louvres was set for the benefit of car drivers, much lower on the ground.  The discussions did not mention the problem for cyclists, whose eye level is also higher than for car drivers.  As a cyclist in Exeter, there are some louvred lights that I cannot see unless I am close to them, because the light is "directed" down towards a car driver.  Geometry says that if the driver is supposed to first see the light when they are 40ft away, a cyclist or truck driver is likely to be about 20ft away when they see it.
 The louvres in this picture are set horizontally, with openings at the base.  Other examples do not have the openings, and have louvres set at an angle ... and as the angle is a number, there is mathematics involved and someone should try and optimise that number.   What criteria to use?  I leave it as an exercise in multiple objective decision-making

Scheduling electrical power supplies - the effect of on-demand TV

When a popular TV programme comes to an end, viewers rush to put the kettle on for a hot drink.  For some programmes, the resulting surge in demand for electricity put a strain on the power system, and so the power companies had generators ready to be brought online to meet the demand.  One of my industrial contacts worked for a power supplier, and we discussed the problem that his business faced.  It was an interesting application of O.R., and like so much O.R., it was hidden from view.  The company needed to know TV schedules, and forecasts of viewer numbers and the step in numbers between programmes, and what fraction of those who stopped viewing would use high wattage equipment. Occasionally, I used this as an example for students to consider how they would tackle such a forecasting and scheduling problem.
However, changing habits in TV viewing have reduced the size of "end-of-programme" surges.  Many people watch programmes on catch-up TV, so want their hot drinks at a time which bears no resemblance to the end of the original programme.
Fifteen years ago, the surge (called a "pick-up" in the power companies) after an episode of the popular soap, EastEnders, could be up to 660Megawatts.  Now there is still a surge, but only 200Megawatts.
Jeremy Caplin, the Energy Forecasting Manager for the National Grid, has the overall responsibility for developing models for forecasting demand.  He was recently quoted as saying: "We see as many spikes in demand, but they are much, much smaller than they were.  The way that people watch TV has meant that they have come down in size."  Nonetheless, during the summer's Olympic Games, there were many sizeable spikes, because so many people wanted to see events as they happened.
From an O.R. perspective, the integration of forecasting and resource allocation is an interesting case of several techniques coming together to deal with a problem, and it is one which occurs several times each day.
Besides forecasting the surges, the forecasters at the National Grid have had to forecast the effect on solar farms of a partial eclipse of the sun, and there is an infographic available (below) of the changed demand during the 1999 total eclipse of the sun when crowds of people stopped using power to watch the eclipse.

Putting on the kettle is not the only activity that follows a popular TV programme.  I met an engineer who had studied the variation in the flow in sewers during advertising breaks and at the end of TV programmes.