MP in Action‎ > ‎Other Applications‎ > ‎

Aircraft Swapping by Constraint Logic Programming

This article is based on a talk given by Naomi Fine of British Airways to the Mathematical Programming Study Group.

British Airways is one of the world's leading airlines, making more than 1000 flights a day to 180 destinations in 80 countries. Supporting its activities is the largest OR group in the U.K., some 150 people divided into 9 sections covering everything from corporate strategy and airport planning through sales and marketing to engineering and cargo.

Flight Scheduling Hierarchy

One of the most fundamental problems which an airline faces is deciding which aircraft to fly on what routes when. This is actually a series of problems over a variety of timescales, as shown in Figure 1.

Figure 1: Flight Scheduling Hierarchy

Different areas within BA have responsibility for these tasks:

  • Network Development identifies changes to the pattern of routes between 3 and 5 years in advance. They are concerned with trends in demand and negotiating the rights to fly new routes.
  • Fleet Scheduling's role is to develop detailed schedules for the routes which BA will be flying. These are generally known 3 years in advance and the schedules are refined successively with increasing detail (times, aircraft types, etc) as they come closer to fruition.
  • Operations Scheduling manages the current season (BA has two, Summer and Winter, with separate timetables) and makes minor changes to the timetable, adding flights or changing the aircraft type. It does this in collaboration with Revenue Management, which is concerned with maximising the revenue from the available flights and aircraft.
  • Operations Control is concerned with making things work on the day, overcoming the problems which inevitably arise.

In the USA LP-based techniques are used widely to plan airline schedules, allocate aircraft to them and schedule crews. The problems there are, however, somewhat different as most flights are domestic and there is greater scope for reallocating resources from one flight or route to another. BA does not use such techniques but may move towards them in future.

The Aircraft Swapping Problem

One specific problem which Operations Scheduling tackles is responding to one-off demands for increased capacity, for instance when there is a trade fair. Operations Scheduling attempts to meet the increased demand by increasing the size of the aircraft on the route or by inserting an extra flight. Usually this involves swapping the aircraft on this route with that on another route with lower demand, so the problem is known as aircraft swapping.

When planning an aircraft swap, Operations Scheduling must negotiate changes with the resource holders within BA: Cabin Crew; Flight Crew; Ground Operations and Cargo. It may also have to negotiate with external parties, e.g. with airports where changes to take-off. or landing slots are required.

The present aircraft swapping system is based on the Lotus Notes package. Revenue Management post a request for increased capacity on a flight and say what the expected revenue is. Operations Scheduling look for 1:1 swaps and offer up to 3 solutions. The resource holders then give their views, which may be (and often are) to reject the proposal because it makes something else worse or is technically impossible. If one of the proposals is acceptable to all the resource holders it is accepted and put into the detailed operational schedule.

Prototype System using CLP

Constraint Logic Programming (CLP) is an attractive technique to use to tackle this problem. What is wanted is a series of swaps of aircraft to achieve the necessary increase in capacity with the fewest disadvantages and a minimum of hassle. This suggests a technique based on a local search which is able to handle logical constraints, such as CLP. By contrast, an LP-based technique would consider changing everything.

BA have developed a prototype aircraft swapping system in conjunction with IC-PARC, the commercial offshoot of Imperial College, London. The system holds data including:

  • the operating schedule;
  • the fleet of aircraft;
  • planned maintenance;
  • turnround times at airports;
  • buffer times to be allowed between scheduled activities;
  • capability of airports to service aircraft;
  • branding restrictions (e.g. shuttle aircraft don't have a section for Club passengers);
  • numbers booked on flights and expected revenue.

The user specifies the flight for which increased capacity is required, the number of extra passengers and the expected revenue. The system generates a list of potential solutions and a comparison of the lines of work in the modified schedule against those in the original schedule. An example is shown at Figure 2.

Figure 2: Lines of Work for an Aircraft Swap

The lines of work are timetables for each individual aircraft, showing where it is at any time and what it is doing

Some of the data are of varying degrees of "softness". For instance, it is possible to shave the turnround times at some airports but not at others. Where an airport does not have the capability to service a particular aircraft, BA may be able to overcome this by putting a licensed engineer onto the flight. The user can specify which of the constraints are to be "softened" and the system will then generate solutions which may violate soft constraints. The resource holders then review the list of violations associated with each potential solution and decide whether they are acceptable.

How it Works

The system generates its solutions in three stages:

  • a pre-processor uses CLP to identify all possible lines of work which are relevant to the required change;
  • an enumeration routine generates all possible solutions involving up to 4 swaps of segments of the lines of work;
  • a reintegration routine uses CLP to assess the impact on the current lines of work and identify the best solutions.

It has been implemented on a Sun Sparc 10 workstation and typically takes 10 - 20 minutes to run, the majority of which is in the enumeration routine. The constraint logic has been written using the Eclipse language, which was developed under a European collaborative research programme. Constraints are defined declaratively, as are the domains which the variables can take. The search routines consist of algorithmic code which specifies how the constraints are to be used to propagate values from variable to variable. These routines are the mathematical core of the system and guide the search intelligently through the branch-and-bound tree.

Results

The prototype system has been run in parallel with the existing system for 3 months. It has found all the solutions which Operations Scheduling have found, together with extra solutions, especially for the bigger fleets. The quality of solutions has been higher than for the manual solutions which Operations Scheduling has been producing, i.e. they have demanded fewer a smaller compromises from the resource holders.

One large benefit of the CLP system has been that it has worked automatically. Revenue Management has known the number of aircraft swaps which Operations Scheduling could handle and has restricted its requests accordingly. With the CLP system it is able to explore for itself the practicability of potential requests for increased capacity without having to make a formal request. It would like to use the system more often when flights are full. However, to achieve the full benefits the aircraft swapping system would have to be integrated with BA's existing hardware and software and that runs up against other resource constraints.

Related articles include Making Best Use of the World's Favourite Runways. To find other articles, refer to the MP in Action page.

Comments