Thursday, 12 May 2016

Queuing for Beginners - a book by Joe Moran

I found a copy of the book "Queuing for Beginners" by Joe Moran in a charity shop.  It has the subtitle: "The story of daily life from breakfast to bedtime", and is a study of aspects of everyday life in Britain, and in particular, in the cities and towns.  It is a book about sociology and social history - and the mathematics of queue theory is only mentioned in passing.

The book's chapters are arranged by hours of the day from what people eat - and used to eat - at breakfast through commuting to shopping and taking smoking breaks, through to television watching in the evening,  Some of the evidence comes from Mass Observation reports in the 20th century, other data from more recent studies and commercial reports.

For the O.R. reader, there are several interesting notes in the chapter on queues - "Cashier number one, please" (for non-U.K. readers, this is the recorded announcement one hears in many banks and businesses, telling the person who is waiting which server is now available).  In the layout of the book, this queue is timed at noon, because so much queueing happens at lunchtime, when office workers are free, and cashiers are scheduled to have their lunch. 

Moran's coverage of queues starts with 19th century references to waiting for service, then continues into the wartime queues for rationed food.  " ... the myth of the British as patient queuers developed during the Second World War.  In this time of rationing and shortages, there was nothing trivial or decorous about queueing etiquette.  Waiting in line was a fraught, politically charged activity ..."  After the war, queues became politically charged, leading to a famous poster in 1978-79.
Moran writes briefly about queue management systems, and the snaking queue system which is found at airports and in amusement parks.  Disney discovered the psychology of these, that they give the impression of movement when the queue is hardly moving at all.

Finally, he distinguishes between the camaraderie of some queues - for tickets to Wimbledon, or to buy a new mobile phone - with the everyday frustrations which "do not have the same warm glow of togetherness".

All in all, an interesting, sideways look at queues, as one important aspect of everyday life (and in O.R. we know how important they are!)

Monday, 9 May 2016

Discrete optimisation for fun

I have mentioned Bob Bosch and his mathematical art before; recently the (US) National Museum of Mathematics released a video on Youtube of Bob giving a lecture there on some of his work ("Math Encounters - Life is Beautiful: The Startling Consequences of Three Simple Rules")  It is a lecture on creating artworks that use patterns from John Conway's "Game of Life" as the building blocks and using discrete optimisation software to lay out those patterns in a picture.  
I thoroughly recommend it!  There is a plug for O.R. during the lecture and the first person in the audience to join in the questions (at 1:13:14) expresses delight in that publicity.  
As an undergraduate maths student, John Conway taught me Number Theory.

Tuesday, 29 March 2016

An app for better vehicle scheduling

I used to lecture a little about vehicle routing and scheduling.  One of the regular problems that came into the discussion of the reality of the subject - as opposed to the theory and mathematics - was that of vehicles returning empty.  A lorry would take a load from A to B and then have to return from B to A empty.  As a class, we would discuss ways that the haulier could avoid such empty returns - and as a mathematical exercise we would consider the availability of loads at C1, C2 and C3 (close to B or on the route from B to A) to be taken to near A.  Given the appropriate parameters of cost of the lorry per unit distance, when empty and loaded, the cost of loading and unloading, the cost of extra time on the road, and so on, it was a straightforward calculation to decide whether any of those loads was worth taking. 

Now I learn that a start-up company, Quicargo, has devised an app to help with this.  A customer needs a haulier, and broadcasts the specification.  Hauliers with the app can make a quote for taking the load, rather like the apps used for finding a taxi in many cities.  There are differences; some hauliers will not want to take loads on some routes, and other hauliers are contracted to a limited number of clients.  We will see what happens.

The size of wheels and castors

In the early 1960s, Dr Alex Moulton launched the bicycles that are known by his name.  They were a revolutionary design - for well over half a century, bicycles had (almost) invariably a diamond frame and wheels about 26inches in diameter, and no suspension.  Moulton bicycles had suspension, small wheels (17inches in diameter) and an open frame.  The smaller wheels meant that the tyre pressure had to be higher than was then normal, and the suspension was essential.  It was about 25-30 years before suspension became common on "traditional" sized bicycles.  Modern small-wheeled bicycles have slightly larger wheels (20inches is common).

There continues to be debate about the comfort and ease of riding bicycles with different sized wheels.  There is not much choice, because they are standardized.

Not so castors and wheels on trolleys used for moving goods around shops.  The first vendor that I found in the UK offers castors with diameters: 50mm, 75mm, 80mm, 100mm, 125mm, 150mm, 160mm, 200mm, 250mm, 260mm, 330mm, 370mm and 400mm (and I may have missed some out!).  If you want, you can have castors made to measure.

An assortment of castors
Bicycle wheels need to match the other components of their vehicle.  However, castors can be chosen for the purpose.  They don't need to match mudguards and frames.

The cleaner in the shopping centre this morning was struggling with his trolley, when I stopped to chat.  The shopping centre is paved with small slightly rough flagstones, about 300mm square.  The trolley was not designed for use on such a surface.  It had 100mm castors, and they didn't cope.  Actually, I think they were a little too small for use on a hard surface indoors, because of the load being carried.  Some designer had economised - someone who didn't have to move the trolley around that shopping centre - and there was no feedback to suggest a change in the design.   For the sake of a few pounds, the cleaner's work was being made harder.  Now, if the designer had applied a little operational research "What if?" analysis, things might have been much better.

Later in the day, I found a trolley of similar dimensions, with larger wheels, which was much easier to handle.  It was in a department store, and moved bags of clothing across the smooth floor with ease.  Well done, that designer!

Sunday, 6 March 2016

Supermarket plastic bags and credit cards

Since October 1st 2015, in England, supermarkets are not allowed to give away plastic carrier bags.  They make a charge of 5 pence (about 4 US cents) for each bag.  Up to that date, shoppers could take away a free bag in most of the larger chains of supermarkets.  There are some exceptions to this law, and smaller shops are allowed to give away a free bag, but very few do.  A few days ago, a news item recorded that one company making plastic bags for supermarkets had been forced to close, leading to 40 employees losing their jobs.  That was sad news, but was one demonstration of the way that the nominal charge of 5 pence had altered the behaviour of the shopping public.  Instead, people have bought long life plastic bags (see next paragraph and later) or cloth bags which they bring with them to the stores.  Estimates from the retail sector suggest that the consumption of "One trip" bags has fallen by 80%.  Hence the effect on the manufacturer.

Supermarkets sell long life plastic bags, which are tougher than the free bags - but most of them have a policy that you can exchange a worn-out long life bag for a new one for no charge.  The long life bags are, naturally, emblazoned with the shop's logo and name, to act as a mobile advert.  The same news item that revealed the closure of the manufacturer reported the obvious phenomenon that shoppers are taking the bags from company X when they shop at supermarket Y.  Tina and I have been doing that for ages.  We have a "bag of bags" which contains long life bags from at least four different companies. 

I wonder how effective the long life bags are as mobile adverts.  This is the sort of question which O.R. scientists might study with the aim of determining an appropriate marketing strategy.  My gut feeling is that they will have a tiny effect on other shoppers;  when did you last notice the brand of the carrier bags of the person at the neighbouring check-out?  Yes, I have been aware of them a few times - once when I passed a shopper with a bag for life from a French hypermarket, and a couple of times when the bag seemed out of place, with a discount supermarket bag in an upmarket store, and vice versa.  But there is a possible marketing opportunity to target the owner of the long life bag.  And it depends on using big data.

Supermarkets issue loyalty cards which offer their users different benefits (Tesco Clubcard, Sainsbury use Nectar, Morrisons has "Match and More", Waitrose use MyWaitrose).  Using one of these loyalty cards allows the supermarket to build up a picture of the shopping habits of the owner of the card, which can be coupled with the data that had been needed to register the card.  And some of the supermarkets have credit cards linked to the loyalty cards.  So, without giving away too many details, we have two such credit cards.  The first we use for most of our shopping, whether in the parent supermarket or not.  The second we use in its parent supermarket and for online shopping.  So the first parent supermarket can track how much we spend in some of its rivals, and know that we are not completely loyal to it.  The second can see that we do not do all our grocery shopping with them.

What incentive could these stores give us to try and change our habits?  Could they devise an extra incentive to encourage regular loyal shopping?  And I suggest that bags for life could be used. 

Consider the scenario.  This shopper has a credit card linked to supermarket Z.  According to the big data, that shopper spends 40% of their monthly food shopping at Z and the other 60% at two or three others.  Supermarket Z might find it to their advantage to offer the shopper a free bag for life with a minimum spend, or a discount if they do their shopping in Z with an old bag for life from Z.  The data exists - how do you want to use that data to make profits? 

Tuesday, 1 March 2016

Queueing at the traffic lights

My colleague came into the department, fuming.  He lived outside Exeter, and commuted by car along one of the main routes into the city.  Because the city is divided by the river, there was no alternative route for his daily journey.  And there were road works on the road.  His frustration was the setting of the temporary traffic lights, which controlled a section of the road where there was one-way traffic.  Over coffee, mid morning, we analysed the symptoms and tried to diagnose the underlying problem, and worked towards a solution.  I think it became an undergraduate discussion topic - we wanted the students to think about the topics they were learning about.
At each end of the one-way section, there was a set of traffic lights, which used radar to detect the presence of a car waiting.  But, he explained, the traffic flowing into the city in the morning and the traffic flowing out in the evening, would be limited to about 60 seconds' worth of green light, then the vehicles in the opposite direction would be allowed through, and they might have 60 seconds - or less - which would completely clear the queue from that direction, leaving the lengthy queue of commuters (in or out) moving forward in a succession of 60 seconds-worth chunks of traffic.  He regularly sat through five or six sets of changes before getting through the one-way section. 

It was a problem of queueing and the way that the "server" (traffic light) dealt with the queue.  There was clearly a setting on the system which used an algorithm like this:
(A) If the light is red and there is a car waiting, signal that the light should change at the next epoch;
(B) If the light is red and there is no car waiting, signal that the light should stay at red;
(C) If there is a signal to change the light, the next epoch is defined as the first of (i) 60 seconds after the lights last changed; (ii) there is no car waiting at the other end.
There was probably a further rule to change all lights to red if there was no car at either end

These rules led to the queues for commuters and their frustration at seeing the traffic in the opposite direction moving so quickly.

So what could be done about it?  The radar did not measure the length of the queue, it only detected the presence of a vehicle at the head of the queue, but common sense would have suggested that the traffic would be unbalanced during the weekday rush hours.  So we postulated a variation on (C)(i) to make it 120 seconds during the rush hour for the commuting traffic.  (120 seconds arises from a psychological observation about UK drivers - if traffic lights do not change in that length of time, then in this country, drivers start to think that the lights do not work and take risks.  As I recall, in other countries, drivers may be more patient or more impatient - there are national variations.) 

I don't know whether such rules have been included in the programming of temporary traffic signals; we were using common sense and knowledge of queues and statistics. 
French traffic lights - with handles and a wheel
Now, several years later, we have a related problem at road works near home.  There are temporary lights at a local crossroads, replacing the lights which are out of action for a short time.  Once again, the problem is the setting of an algorithm.  The lights are radar controlled, and at busy times behave like this:
  • green for westbound traffic for 50 seconds or until there are no cars (whichever is first)
  • red all round for 12 seconds because the westbound traffic must clear a narrow section (*)
  • green for eastbound traffic for 50 seconds or until there are no cars (whichever is first)
  • red all round for 12 seconds (#)
  • green for both northbound and southbound traffic for 50 seconds or until there are no cars (whichever is first)
  • red all round for 12 seconds (##)
(*) is sensible because of the narrow section
(#) and (##) are not sensible because the traffic does not need such a time to clear the junction - and that is the wrong setting which results in frustration
The permanent lights use 10 seconds in (*) and 3 or 4 seconds in (#) and (##)

I imagine that the installers would argue that they act with a safety margin - but the excessive safety leads to impatience and annoyance; a little application of queue modelling (and common sense) would improve the road user's lot.

Monday, 22 February 2016

Inspecting millions of items

This is a management problem without an obvious solution.  In the U.K., private motor vehicles must - by law - pass a test each year.  It is called the "MOT test", and people talk about "going for the MOT", even though the Ministry Of Transport (MOT) is now the DVLA (




What the test covers