Monte Carlo or bust (Monte Carlo Method, part 4)

By Brian Clegg

This is the final post on the mathematical approach known as the Monte Carlo method, following ‘Generating random numbers.’

We have seen in previous posts why the method is named Monte Carlo, how it was first used and the difficulties of obtaining a stream of truly random numbers. This approach is now used across the sciences, as well in engineering, economics, AI and more. It’s an technique that comes in useful when there is a complex mathematical problem solve, where taking repeated random samples of weighted possible outcomes will give a better understanding of a real world situation.

There are far too many applications to go into detail here (you can find a length set of possibilities in the Wikipedia entry). To see a simple one in action, take a look at this Monte Carlo-based pi generator. But I just want to pick out another application that I’m particularly familiar with from using it to help understand queues in an airport terminal. I’ve always thought that queuing is one of the most fascinating aspects of Operational Research, which I worked in for a good few years. Apart from anything, this is because queues involve people, and the way that people interact with each other.

Anyone who has visited theme park rides in different countries may well have experienced varying cultural approaches to dealing with a conventional single line queue, from polite fairness to ‘cram in and try to get in front’. But things get more interesting when there are multiple servers. Once upon a time there would typically be an individual queue for each server. This is still often the case, for example, with supermarket trolley checkouts and airport passport checks. But in many cases, it is more effective to have a single queue feeding all the servers, where the person at the front goes to the first available server.

It’s not long ago that such queuing systems were treated with suspicion: since the single queue is much longer than any one of the individual queues it replaces, it looks like it will make waiting time longer. But it doesn’t in many circumstances. Usually when we want a single queue multiple server setup we corral people to make it easier to see what’s happening. With no enforced structure, for example, at a row of several busy cash machines you usually see a queue forming behind each dispenser – though I was delighted a few years ago (when I used to use cash) to see a spontaneously formed single queue, multiple server arrangement developing as people held back from cashpoints and let the first person go to whichever became free.

There are times, though, when the intuitive setup may not be the most effective – and this is where a form of Monte Carlo Method comes in, in the form of simulation. (Some pedants don’t include simulation as Monte Carlo, but I disagree, and it’s one of the easiest examples to get your head around.) When I did this, I manually coded it, though for many years now you have been able to use off the shelf simulation packages. After collecting data on the distribution of times a transaction takes, which depends on the complexity of the interaction (e.g. the number of items in a shopping trolley, the number of bags and options in a check-in, or the complexity of a bank transaction ranging from a simple deposit to setting up a new account) plus the flows of customers at various times, the simulation makes use of random number generation to control both the availability of servers, the arrival of customers with different transactions, and their queue selection if there is more than one queue.

This is then run as a simulation, a bit like a self-playing video game, churning through a virtual day over and over to build up an effective picture of what is likely to happen. The same approach can then be taken with variations in the queuing layout, making it possible to provide the best structure of queue(s) for the particular requirement.

I had many a happy hour looking at queuing possibilities for Heathrow’s Terminal Four (don’t blame me if the queues don’t work now – this was many years ago and the queuing structures/airline usage have changed several times since). It was a delight to be putting (pseudo-) randomness to good use.

Image from Unsplash by Lisanto

See all of Brian's online articles or subscribe to a weekly digest for free here

Now Appearing is the blog of science writer Brian Clegg (www.brianclegg.net), author of Inflight Science, Before the Big Bang and The God Effect.