Open Flight Repair for Air Crew

Allocating air crew (flight deck and cabin crew) to cover the flights of an airline is typically done with a large-scale rostering application, which are often based on column generation techniques, resulting in very large-scale set covering problems. These tools generate a roster for a 4 week period or for one month, while running for several hours or even days.

SAS MD-80 (from Wikipedia)

What happens if the published schedule breaks, either because of illness of some crew member, or because some flight connections can not be reached in time, due to delays of earlier flights? This is where the TAP-AI application comes into play, a decision support tool for day-to-day management of “open flights”. Open flights are flights for which one or several previously allocated crew members will not be available. Usually, a replacement crew must be found with the right qualifications, and he must be notified in time to reach the flight, including all briefing and preparation tasks. At SAS (Scandinavian Airline System), finding solutions for these open flights was done by hand, a difficult, stressful job.

Flight deck qualifications (aircraft, destinations) impose strict constraints on replacement crew (Wikipedia)

How can we express the problem with constraint programming? This problem is more complex than most scheduling problems, as people not only perform certain tasks, but move from one location to another. Their next activity must start after they have arrived at the destination, and must begin in the same location as the arrival location of the previous flight.

We model this problem as a directed graph. The nodes are the flight activities (both the open flights and the ones already assigned to crew) and the crew itself. We have a link between two flights i and j if it is possible to continue work with flight j after finishing with flight i. This means that the arrival location of flight i must be the departure location of flight j, the departure time of flight j must be after the arrival time of flight i (plus time to travel inside the airport, and all preparation times that are required). There are many other constraints to consider, for example if the aircraft types are compatible, i.e. one person can be qualified to handle both activities.

Connecting Two Flights

We have a link from some crew node to a flight node, if the crew can start work with that flight. We have a link from a flight to a crew node, if that flight can be the last flight on a trip for that crew.

Starting a Tour

In order to find a trip for some person, we search for a cycle in that directed graph. This means that we start in a crew node, we move along the directed edges of the graph, linking multiple flights together, and then return to the same crew node.

Cycles in Directed Graphs

Unfortunately, not all cycles are legal tours. There are any number of rules and regulations that apply, as well as agreements between airlines and unions that must be respected. Some of those rules we can add to our constraint model. For example, there is a constraint on the total number of flight and on the total flight time in a single trip. To satisfy this, we consider the flight times for all activities, and impose a limit on the length of each cycle. In a similar way, we can impose a limit on the total working time, i.e. the time between the departure of the first flight, and the arrival on the last flight assigned to a person (adding time for clocking-on and off, briefings, preparation activities etc).

But some of the rules are too complex to be handled directly in the constraint model. These rules are checked with a generate and test approach. We generate a possible tour, that satisfies all rules known to our constraint model, and then ask an external rule checker program, if that is a legal tour. The checker will apply all rules, and will decide legality. Writing a legality checker is a complex task in itself, but fortunately this is a component that was already in place at SAS.

An important aspect of the open flight management system is that it does not have to find solutions to every problem. It is a tool to free the human operator from routine work. If a problem is relatively simple, then the computer should propose a solution, which can then be implemented.

For really complex situations, it might be enough to push the problem forward in time. Instead of adding the flight to an existing crew roster, we may want to swap the open flight against some flights which are further into the future. We solve the original open flight problem, but have created a new one. What we have gained is time. We now have more time to contact people, reroute some trip for some aircrew, or call in a spare crew from stand-by duty.

The TAP-AI system was built very rapidly, to bridge the gap before a more complex, but delayed system would be available. The constraint programming framework was ideal for this task, the project duration was 6 month, with 6,000 of the total 7,000 lines of code being concentrated in the constraint model.

The picture below shows the user interface of the TAP-AI prototype. It shows a list of flights at the top, then a line containing all open flights, and then a Gantt chart displaying the duty assignment for all crew in that scenario. Fortunately, we can decompose the overall problem into many smaller one, by solving the open flight problem for each crew category separately. Pilots, for example, are typically only qualified for a particular type of aircraft (or family of aircraft). We can solve the problem for each aircraft type on its own, reducing the problem size dramatically.

User Interface for TAP-AI Prototype

To learn more

The open flight handling problem and its solution in CHIP are described in “G. Baues, P. Kay, P. Charlier. Constraint Based Resource Allocation for Airline Crew Management. In Proceedings Air Transport and Travel Information Systems (ATTIS 94), Paris, April 1994.” Open flight management was also a topic in the European DAYSY project, but that is another story, as the saying goes.

Advertisement