MP in Action‎ > ‎Other Applications‎ > ‎

### Making Best Use of the World's Favourite Runways

 This article is based on a talk given by David Haydon of National Air Traffic Services to the Mathematical Programming Study Group. Runway Capacity at Heathrow London's Heathrow airport is the world's busiest international airport with 440,000 movements (take-offs or landings) in 1996. Although it cedes the title of the world's busiest airport to Chicago's O'Hare with 900,000 movements in 1996, that airport has 9 runways compared to Heathrow's 2. It is the intensity with which the runways are used and the desire by airlines for more take-off and landing slots which creates constant pressure to improve how they are used. The runways at Heathrow are used to capacity 15 hours a day, 364 days of the year (Christmas Day is the exception). During the day there are peaks and troughs with high demand in the morning and early evening and a period of relative slack in the early afternoon. Figure 1 shows the expected delay on take-off through the day, which is a measure of the level of congestion. Figure 1: Average Delays on Take-off through the Day The definition of capacity is interesting and gives some insight into the problems of scheduling aircraft movements. A runway's capacity is defined as the number of aircraft movements which may be scheduled to use a runway such that the average delay is no greater than some specified value and the peak delay is no greater than another value. For Heathrow the upper bound on the average delay is set at 10 minutes over any 2-hour period averaged over the entire month; the peak delay is set at 20 minutes for arrivals and 25 mintes for departurtes, each to occur no more than 1 day a month. These definitions are expressed in terms of expectations and probabilities because the processes of taking off and landing are partially stochastic, especially the times which it takes to perform the various stages. Some of the flight-paths are also stochastic. For instance, transatlantic flights may approach Heathrow either from Scotland or from Ireland depending on the location of the jetstream, a high-level wind on which they piggy-back; conversely the outbound transatlatic flights follow the alternative route. Constraints on Movements At Heathrow one of the runways is used for take-offs and the other for landings. (The two runways switch over in the early afternoon to spread the noise burden but that is a detail.) The greater problems with capacity occur with take-offs so that is what we shall consider in more detail. There are six types of contraint on departures: wake vortex separation; SID (standard instrument departure route) separation; speed group separation; calculated take-off times; minimum departure intervals; physical constraints. A general limit is that one aircraft cannot start down the runway until the previous one is safely airborne. This imposes a minimum separation of 1 minute between take-offs. Wake vortex separation is concerned with ensuring that an aircraft is not destabilised by the vortices created by the preceding take-off. Large aircraft (e.g. Boeing 747s) have sufficient momentum and power that they can take off 1 minute after any preceding aircraft. Smaller aircraft may be able to take off 1 minute after another small aircraft but need to wait 2 minutes after a large one. There are 6 standard instrumentation departure routes from Heathrow. For the sake of this discussion we can simplify this to two: North and South. On any route the separation between two aircraft must be at least 5 miles, which equates to 2 minutes at take-off speeds. If we have 4 take-offs, 2 going North and 2 South and we schedule them NSNS the interval between the first and the last take-off is 3 minutes. But if we schedule them NNSS the interval between the first and last take-offs is 5 minutes. This is a huge difference and one which is potentially controllable. It represents the main opportunity for improving the use of runways at Heathrow. Aircraft fly at different speeds; for instance, Concorde takes off much faster than subsonic jets. This means that unless extra separation is imposed between it and the preceding flight on the same SID, it could catch up, which would be dangerous. Calculated take-off times are allocated by the Central Flow Management Unit in Brussels and are time-slots of 5 - 10 minutes. If an aircraft takes off within this interval it will be able to fly through the various air-traffic control zones on the Continent without delay; if it misses the slot it may have to wait a significant time for another slot. Minimum departure intervals are similar and protect UK air traffic control sectors from overload. Beneficial Queues A general result from queuing theory is that as the demand for a service increases, the expected time waiting to be served at first increases linearly and then increases exponentially (see Figure 2). Figure 2: Average Delays on Take-off through the Day Because of the multi-stage process involved, the expected delay on take-off is more complicated than this, but the principle remains the same that from some point it increases exponentially. During peak hours, Heathrow's runways operate in the early part of the exponential section. Despite this, such is the demand for peak-hour slots that the airlines recently agreed to an increase in the average expected delay from 5 to 10 minutes because this enabled the scheduled number of departures to be increased by 1 an hour. With a normal queue the benefit from increasing the expected delay arises from ensuring that the server is kept busy despite random fluctuations in the arrival of people to be served. As the runways at Heathrow are already busy throughout the peak hours, it might be thought that no such benefit would follow. But the rules about SID separation and the availability of multiple taxiways mean that longer queues of aircraft waiting to take off give the air-traffic controllers greater flexibility in selecting which aircraft to despatch next. As a result they are less likely to be obliged to send off two aircraft along the same SID route and so more aircraft are actually able to take off. Sequencing Departures At the moment the air-traffic controllers schedule departures manually. Despite the difficulty of keeping track of all the aircraft and the pressure they are under, they generally make a very good job of it. Nonetheless, the value of extra take-off slots is so great that it would be worth millions of pounds a year to be able to squeeze in an extra flight. This has led NATS to engage in a programme of work to try to assess how many extra flights might be able to be squeezed in and what type of decision-support system would be most effective. A Mixed-Integer Programming (MIP) model has been built in order to work out an upper bound on runway capacity. This has taken observed data on aircraft movements and attempted to find a better sequence of movements than the one used. The model generates an upper bound on the improvement because it assumes that everything works as planned rather than being subject to random variations. Even with this caveat the predicted improvement of up to a 20% reduction in delays or between 1 and 1 1/2 extra movements an hour looks enticing. MIP itself is however not suitable as a solution technique: runs take hours or even days whereas an operational system must run in seconds. A heuristic approach looks more likely: some simple heuristics have been producing good solutions in 1 - 2 seconds. Conclusion Runway capacity at Heathrow is enormously valuable. An analytic approach to assessing peak runway capacity has already enabled more aircraft to be scheduled in the peak hours. Further improvement looks set to follow from the development of real-time models to support the sequencing of aircraft take-offs by air-traffic controllers. Related articles include Aircraft Swapping by Constraint Logic Programming and How to Build a Mathematical Programming Model. To find other articles, refer to the MP in Action page.