Monday 20 December 2010

O.R. and some French roads

I am always intrigued when I find references to some kind of modelling which is identifiable as O.R. in obscure places. A book on the historical geography of France has provided two such observations. ("The Discovery of France" by Graham Robb)

Writing about the mid nineteenth century, "In the Landes, where carriages sank in the sand up to their axles, the engineer Chambrelent calculated that once a road reached a certain length it would be destroyed by the process that built it: 'In travelling to the point where it will be used to prolong the road, one cubic metre of stone or gravel wears out more than one cubic metre of road.'"
The modelling must have been based on some observations and statistical analysis.

Then, about roads later in the nineteenth century, "The chief engineer in the Limousin, Pierre Tresaguet, had insisted that a limit sould be placed on [road] gradients. ... The old road east of Morlaix still includes a needless climb of 15 per cent (1 in 7) because the blundering military Governor of Brittany, the Duc d'Aiguillon, preferred straight lines to the more accommodating curve of the older road that runs alongside. Thanks in part to Tresaguet, it is unusual now to find a climb in excess of 8 per cent (1 in 12). This was thought to be the steepest gradient that a fully laden mule could manage. British mountain roads seem to rise in fits and starts like step pyramids. French mountain roads go much higher, but more steadily, and can comfortably be climbed for hours by a fully laden cyclist."

So far so good; the road builders were given a constraint which had been thought about in terms of the users of the road. But there's a twist in the footnote to these comments, indicating that other people didn't make observations:

"To judge by the army handbook of 1884, it is fortunate that most road building was left to civil engineers:
Gradient on which troops can still march in good order: 25 per cent;
Gradient manageable by mounted horses and light carriages: 33 per cent;
Gradient manageable by mules: 50 per cent;
Escarpment that an infantryman can still cross by using his hands: 100 per cent (completely vertical)"

OR and the holidays (2)

This blog post contributes to the INFORMS monthly blogging theme. Look for the INFORMS blog to summarize the blogs at the end of the month.

A Christmas tradition in the U.K. is the office Christmas party, when everyone in the company gets together for some kind of celebration. This year, the economic situation has meant that some companies have cut back on the expense of these events. However, my wife Tina's company held one on Friday evening, and the director invited spouses and partners to attend. More importantly, as an O.R. problem, he arranges taxis for everyone to and from the event. To save money, each one is shared by several people, collected on the way from the most distant employee.

So here is the O.R. problem. How many taxis should be ordered, and which routes should they take? It should be recognisable as a "Vehicle routing problem" for which there are numerous soilution approaches. The constraints and interesting features include:
1) some calls have one pick-up, others two; a route which is feasible for one size of taxi may not be feasible for a smaller one;
2) the supply of large taxis in Exeter is limited;
3) there is heavy demand from other users on a Friday evening, so a supplier may not have enough vehicles; should you order taxis from several taxi companies;

It was a good party, though I ate too much. And the Christmas ale ("Raisins to be Cheerful" from St Austell Brewery) was very good.

Monday 13 December 2010

More about queues

This is simply a link to a wonderful account of how Disney and other theme parks in the USA manage their queues.
How do you disguise the fact that you are in a queue which zigzags in a snake? You make it zigzag through something that is part of the attaraction. Read about it here.

Thursday 9 December 2010

You can’t have a sys­tem if there is no line on it

Do you believe that "You can’t have a sys­tem if there is no line on it"? If you go to this site there's a rap song about numbers, with the refrain above.

What do you think?

Queues, psychology, and collapsing websites

One of the problems of queues which involve people is to forecast when and at what rate the customers will arrive. Recently, the UK supermarket giant, Tesco, made a spectacular mistake in the run up to the Christmas rush and the holidays. Here's the story:
---------------
The Tesco Big Christmas Exchange
Back in November 2010, Tesco announced it was launching a Big Clubcard Voucher Exchange. Lasting four weeks, it gave collectors of Clubcard points the opportunity to double the value of their vouchers on a large range of non-food items, ranging from wine and computers to Christmas decorations.

A similar scheme was launched earlier in the year. However, Tesco trumpeted the fact that this time the scheme had been revamped, so now customers would be able to exchange their vouchers online.

But it went wrong

The scheme was launched around the time that most customers received their November points statement, early in November. If you wanted to double up your vouchers, the closing date was Sunday 5 December.

Clearly Tesco expected the bulk of interested shoppers to take part once they got their statement through, rather than leave it to the last minute. This was very much a mistake, as news reports and Internet message boards are awash with tales of shoppers facing enormous queues to exchange their vouchers, only to give up and try and do it online. With predictable results, the Tesco website collapsed under the weight of so many users.
------------------
Yes, it was bad understanding of psychology, leading to not enough provision of servers for the customers. There is a great deal of literature about call centres and the behaviour of customers, so someone should have been aware of the likely rush at the end. And, I suspect, there should have been some monitoring of the rate of redemption of the vouchers, which might have given advance warning of the changing rate of redemption. If only 10% of the customers redeemed their points in the first half of the offer, then it might be foreseen that there would be a great demand in the second half.

Friday 3 December 2010

OR and the holidays

This blog post contributes to the INFORMS monthly blogging theme. Look for the INFORMS blog to summarize the blogs at the end of the month.

I have two younger brothers, and we all have families. Choosing where to meet, when to meet and what to do for a Christmas family get-together is a multi-criteria decision problem, and our conclusions demonstrate that solutions to a repeated problem change with time as circumstances alter.

One brother (Michael) lives near Leicester, one (Andrew) near Gatwick, and we live in Exeter. For simplicity, these may be regarded as the vertices of a triangle, sides 4 hours, 5 hours and 3 to 4 hours (depending on the traffic around London).

In the old days it was easy. We all met at my parents' home, which was reasonably central. All that was needed was to schedule who travelled when, and help mum with the catering, cleaning and beds. It wasn't too hard to plan what to do.

Even when mum died, we continued to gather at the same place, but we needed to plan a great deal more for the catering.

Then dad came and lived with us, and people came here; with a smaller house than the parents' home, we needed to arrange that Andrew and Michael would overlap for lunch on the day that one arrived and the other departed.

But when dad died, we all felt that there were better times of the year to visit one another. Tourist attractions are generally closed in December, and that limits the scope for days out. So the problem became more interesting. Meanwhile, the next generation was growing up, which brought other people's criteria into the decision process.

We reached a conclusion that we did not need to meet in December, and for several years got together for a Saturday in January, when it was cheaper to travel by public transport, and there were places we could visit together or things we could do together. So that gave a feasible solution, which ticked several boxes for all of us: ease of travel (we each made a train journey with at most one change of trains), a warm place to meet with space for presents to be exchanged, an activity which was pleasant. There was one surprising downside; the presents that we gave had to be compact and portable as we would be carrying them all day.

Then there was a birth and activities which involved theatre or shows in London became infeasible. One year we strolled in London with a toddler, and fortunately the weather wsa good. We all saw parts of the capital which were new, so it was a memorable meeting.

Another birth meant a baby and toddler to be entertained, along with two twenty-somethings who might or might not be around in January, but were more likely to be available in the week between Christmas Day and the New Year. So the weight attached to different criteria changed. We fed our locations into a website (rendeznew) which told us that the meeting point in the centre of the three homes was near Swindon. So we searched for a suitable place to meet and eat there, hopefully with space for the restless children.

And that is the solution at present. Soon after Christmas, three cars (loaded with people and presents) will congregate on a gastropub near Swindon. Each of us will have a two to three hour drive each way, and we have told the staff that it is a family gathering. We are trying out a third pub, for variety.

Could all this be automated? As I have explained, there have been changes in our needs and hence on the emphasis on different criteria. The web site wasn't really needed, as we could see from a map that Swindon was reasonably central, and we had the knowledge of the UK road system to guide us. Once we had found the right locale, we could have searched for places to eat, by specifying criteria (must have car park, serve vegetarian food, be child friendly) but these would be binary constraints (yes/no) and we might want to treat them as slightly soft constraints.

Sometime, I may return to the algorithm used in rendeznew, which has interetsing O.R. aspects.

An astute reader may spot that there is one constraint which we have implicitly included. Nobody wants to stay in a hotel for the family get together.