How to cut queues at immigration – with maths

When going on holiday to a foreign country, there’s one part of the journey that everybody dreads: border control. Everyone has to have their passport checked by an immigration official when entering a new country – and even when leaving some – so queues are almost inevitable.

At Heathrow airport – one of the largest in the world – many arriving passengers are experiencing waiting times of up to two hours at passport control. Border control officials seek to manage these queues through staff rosters – and when there aren’t enough staff rostered on to meet the number of arriving passengers, then queues at passport control can become excessively long.

Staff rostering presents what’s known in industry as an “optimisation problem”. It is used in hospitals for nurses, in call centres and even in schools, for playground supervision. The main goals are typically to ensure that services are completed in a reasonable amount of time, and to reduce the cost of staff.

But these two goals are often contradictory – since paying more staff usually leads to better service. And because of this contradiction, staff rostering can be a very difficult optimisation problem to solve.

Meeting requirements

To balance these two aspects of staff rostering, organisations or regulatory bodies typically impose “service requirements”, in the form of expected service times. At Heathrow airport, the service requirements state that 95% of passengers should be processed at passport control within 25 minutes for EEA citizens and 45 minutes for everyone else.

Unfortunately, the border force at Heathrow has been unable to meet the services requirements for non-EEA immigrants since February 2018. July saw the worst performance, with 24.5% of all passengers entering the UK through terminals three and four experiencing waiting times of more than 45 minutes at passport control. In June, July and August, there have been reports of passengers waiting longer than two hours.

Having lots of valid data is critical to making a good roster and reducing waiting times. The main components of staff rostering are modelling demand, scheduling days off and assigning staff to shifts or tasks. If the demand is known exactly in advance – for example, if the number of playground supervision tasks are the same every day throughout the school year – then staff rostering only needs to consider the last two components.


In more dynamic environments, such as airport arrivals, demand modelling plays a crucial role in staff rostering. In an airport, the demand for passport control is directly related to the arrival times of aircraft, which can in turn be delayed. For example, in May 2015 only 75.93% of flights arriving into Heathrow airport were on time. Of the remaining flights, 17% were delayed by less than an hour, and about 7% were delayed by longer. Since 94% of passengers are international travellers, border control is massively affected by flight delays.

Digging into the data

One of the worst options, in regard to meeting service requirements, is to roster staff according to the scheduled arrival time of all flights. Although this would be relatively cheap, it ignores the fact that air travel is routinely subject to delays.

A better way for border force to reduce delays at passport control is to roster staff so that the largest expected demand can be served within the set service requirements. Basically, this would mean opening as many booths at passport control as possible, at the busiest time for arrivals – taking into account any expected delays.

But this is a very impractical and expensive solution, and there are limitations with respect to the number of available staff – especially since border force is already struggling with insufficient numbers of staff. Fortunately, there is lots and lots of data relating to air travel, which can be used to model demand more accurately, and roster staff and employ other available technologies accordingly.

Historical records of flight arrivals, the number of EEA and non-EEA citizens arriving and the demand at passport control are all available. Through the use of statistical and data science techniques, such as forecasting, a sophisticated model of demand at passport control can be developed.

Performing staff rostering with such a demand model may be conservative, meaning a higher overall cost, but it will be more likely to fit with the reality of air transportation. Yet proper demand modelling can also highlight situations – periods of time when predominately EEA citizens are arriving – where automatic passport scanners could provide flexibility in rostering staff, and which could decrease costs.

Given the excessive delays reported at Heathrow border control, we can only assume that there is significant limitations to the demand model currently being used for staff rostering. By making better use of statistical techniques and drawing on the large amount of data that is available, it’s possible to significantly reduce the waiting time for passport control – even when flights are delayed.

The Conversation

Stephen J Maher, EPSRC Research Fellow, Lancaster University

This article was originally published on The Conversation. Read the original article.