Optimization Earns Its Wings
The development of crew scheduling systems for Air New Zealand
By David M. Ryan
While the successful application of optimization methods in solving parts of the crew scheduling problems for major airlines has been well documented in recent years, such was not the case in the early 1980s when I first approached Air New Zealand to inquire about their crewing decisions. At the time, stories circulating in the airline industry suggested that a number of larger airlines had tried and failed to implement optimized crewing systems. A senior manager at Air New Zealand informed me that he was aware of the failures and asked what made me think I could solve crewing problems for his airline. I responded that I didn't know if I could solve the problems, but I wanted to learn more about them, obtain some data and try to solve them.
In 1984, Air New Zealand agreed to provide information about their planning or tour of duty (pairings) problem for us to use in an honors project for a student in Engineering Science at the University of Auckland. Michelle Kunath undertook this initial project, involving a small part of the domestic (or internal) problem. The results we presented to Air New Zealand at the completion of the six-month project provided the basis of a productive and successful collaboration between the University of Auckland and Air New Zealand. Over the intervening period of more than 16 years, optimization methods have been developed and implemented to solve all aspects of Air New Zealand's crew planning and rostering problems.
In 1984, all crewing decisions were made manually and the airline used no OR/MS techniques. Today, the airline is totally dependent on state-of-the-art, optimization-based computer systems in the areas of crew planning and rostering. The airline now employs more than 10 staff members and contractors with backgrounds in OR/MS. This article will document the transition from dependence on manual methods to dependence on OR/MS methods at New Zealand's national airline.
Crewing Systems at Air New Zealand
The University of Auckland, in collaboration with Air New Zealand, has undertaken considerable research and development of underlying optimization methods for crew scheduling during the past 16 years. This research has resulted in the development of seven optimization-based computer systems to solve all aspects of both the planning and the rostering processes for both the national and the international airlines. Each business problem is characterized by unique aspects that prevent the development of a single common optimization solver.
These systems incorporate state-of-the-art, mathematical optimization technology and provide Air New Zealand with sophisticated crewing solvers. In 1989, when the International flight attendant rostering system was implemented, Air New Zealand knew of no other airline with an implemented rostering system based on optimization. Even today, few airlines use optimization-based rostering techniques. Further details of each of these systems and their integration are given below.
National (domestic) planning. The original planning system for the national airline covering both flight attendants and technical crew was developed in 1984 and 1985 and implemented as a mainframe computer system in 1986. The system remained in production essentially in its original form until 1997 when it was replaced by improved optimization methodology implemented on a Unix workstation. The current system generates optimized tours of duty (TODs) for all crew ranks and for crew bases in Auckland, Wellington and Christchurch. It is also able to produce "fully-dated" solutions.
National (domestic) rostering. While involving relatively small crew ranks (at least compared to the international airline), these problems are probably the most difficult of all the Air New Zealand optimization problems to solve because of their combinatorial complexity. Two previous attempts to solve the problems in the late 1980s were unsuccessful, but the problem for flight attendants was finally solved in 1993 by Dr Paul Day in his Ph.D. research sponsored by Air New Zealand [Day, 1996, and Day and Ryan, 1997]. In 1998, the same solution methodology was adapted to produce technical crew rosters under quite different operating rules. These two unique systems are now fully integrated into the Air New Zealand Genesis Rostering System and produce rosters of excellent quality for all crew ranks and all crew bases in less than four-person days. Previous manual rostering methods involved six roster builders and took two weeks to complete. The actual optimization runs take less than one hour in total.
International flight attendant rostering. This problem, involving 1,500 flight attendants in four crew ranks, is the largest problem solved at Air New Zealand. The original system was implemented in 1989 and was revised to incorporate column generation methods in 1996. At the time of its implementation in 1989, the optimized solution demonstrated that it was possible to construct rosters with a 5 percent reduction in the number of flight attendants and significantly improve the quality of the rosters from a crew point of view. The development and implementation involved representatives of the Flight Attendant Union who defined the issues of roster quality that are incorporated in the optimization. The current system also incorporates a language assignment optimization step [Waite, 1995] that ensures that flight attendants with relevant language qualifications are assigned TODs requiring those language skills. This aspect of flight attendant rostering has important commercial benefits to Air New Zealand in that many of its passengers, particularly from Asia and Europe, are non-English speaking.
International technical crew rostering. International technical crews at most airlines worldwide are rostered by systems based on preferential bidding by seniority (PBS). The algorithms are generally based on greedy sequential heuristic roster construction methods. PBS involves crew members bidding for work or days off; rosters are then constructed by satisfying as many bids as possible given the constraint that crew members are considered strictly in seniority order within the crew rank. During 1992 and 1993, M.E. Thornley developed a new optimization model and solution method for PBS [Thornley, 1993]. The solution method incorporates a unique "squeeze procedure" that violates the bids of more junior crew members in order to satisfy the bids of more senior crew members. This guarantees that the maximum number of bids can be satisfied in seniority order. Heuristic methods used by other airlines are unable to provide such a guarantee. The PBS system was implemented in 1994 and is now fully integrated into the Genesis Rostering System at Air New Zealand.
International technical crew planning. Following the completion of his master's degree research on the topic, Andrew Goldie implemented the technical crew planning system for Air New Zealand International in 1996 [Goldie, 1995]. The system automatically generates "third pilot" TODs that allow duty periods to be extended by including a third pilot on some relevant sectors. This feature is believed to be unique since we understand that planning systems used by other airlines construct such TODs in a subsequent step.
International flight attendant planning. The international flight attendant planning problem is a particularly difficult problem in that flight attendants are qualified to operate on more than one aircraft type. The added complexity arises because each aircraft type requires different numbers of crew. For example, a full B747 crew may split after a B747 sector and part of the crew may fly a B767 sector in their next duty period. The remaining part of the B747 crew could fly as passengers or could be combined with other crew members to make up a crew for some other sector. This crew-splitting complication does not occur for technical crew who are qualified to fly just one aircraft type. Chris Wallace developed an optimization solver for international flight attendant planning in his Ph.D. research. This system is again unique in that it automatically permits crew splitting. No other known planning system incorporates this feature.
Implementation and Integration Issues
On-site development by a small team of developers, working closely with the users, has been central to the successful implementation of these systems. The complex rules-bound nature of the industry requires detailed understanding, and the optimization solvers must be developed with constant reference to the planners and rosterers.
The optimization solvers are able to find many solutions of similar dollar value, some of which are preferred by the users, and much effort has been spent developing control mechanisms for the users to interact with the solutions and so "shape" the solutions produced. For example, users may wish to fix a particular subset of a solution, or prevent particular undesirable characteristics from being included in a solution. Similar mechanisms have been developed to handle changes to inputs to the problem. For example, if a flight is re-timed in the flight schedule, the optimizer will minimize the changes required from the previous solution to the new solution.
The TOD optimizers are integrated into a purpose-built PC-based user interface, also developed as part of the project. The system receives flight schedule data for both proposed and published flight schedules in industry-standard formats from Airflight, the schedules management tool supplied by the Sabre Group. The solutions produced by the TOD optimizers can be viewed graphically using a tool specifically developed for the purpose. Solutions may be electronically uploaded into the Aircrews System provided by Sabre.
The Genesis Rostering System, which has been developed independently of this project, is used by rostering staff to manage the construction of rosters for aircrew. It has replaced mainframe and PC-based systems and manual methods. Genesis accesses the Aircrews database for roster data and provides a common user interface for managing crew pre-assignments, training and crew requests. Genesis passes data to the rostering optimizers where the roster is constructed before it uploads and displays the optimized rosters in the graphical interface. The final rosters are then uploaded into the Aircrews system.
There are two important aspects associated with the implementation of sophisticated crewing systems. The first is concerned with the effects of new technology; the second is concerned with issues of technology transfer.
The introduction of high-technology mathematical optimizers has changed the nature of the jobs and the key competencies of staff in the planning and rostering areas. Staff now manage data and processes associated with the construction of TODs and rosters, rather than simply constructing TODs or rosters. The optimizers allow staff to concentrate on meeting specific business requirements, which might include training or absences, meeting special requirements of management or crew, or incorporating last-minute changes.
Because of the sophisticated nature of the mathematical optimization models and methods, it is important that management, the crew and the planning and rostering staff develop trust and confidence in the solution methods and the quality of the solutions. This can only be achieved through close collaboration with these affected groups. The development of trust and confidence has been a major objective of this project since it is an essential requirement of successful technology transfer from a research and development environment to a production environment. We believe that this objective has been fully achieved in this project.
Keys to the project's success:
- Each application is built to solve a particular business problem, with further domain-specific customizations exploiting facets of Air New Zealand's business problem. These customized solvers produce better results in less time than a general-purpose solver. Since the solutions are developed in close liaison with the users, the systems have a natural fit, both in supporting Air New Zealand's business practices and integrating into the existing computer systems infrastructure.
- Each optimization application has reduced the costs of operating a flight schedule. Over the past 10 years, Air New Zealand's aircraft fleet and route structure has increased significantly in size, but the number of staff required to manage the crew scheduling process has been reduced significantly.
- Solution quality is maintained, even after staff changes, as the optimizers incorporate the complex business rules. This has the additional benefit of complying with legislative and contract limitations, as required by the Civil Aviation Authority.
- Solutions are developed in significantly less time than manual solutions. This has different business benefits in the two different areas: in planning, this results in more scenarios being evaluated leading to improvements in the value of the flight schedule; in rostering, the roster-build can commence later, therefore incorporating late changes and reducing rework.
- The definition of the "best-quality roster" is predominantly a concern of the crew since many feasible rosters exist for the same work and number of people. Optimized crew rostering based on a crew-defined quality measure provides a win-win opportunity for crew and management. Any complaints with rosters are directed to crew representatives for evaluation and comment. Many "soft rules" have been agreed to, leading to improved roster quality. These non-contractual "soft rules" can usually be stepped back from inorder to find a feasible roster, and they therefore have no significant impact on crew productivity.
- As optimization methods have been improved, harder problems have been solved and better implementations of existing solvers have been completed. Redevelopment has yielded additional savings, in both planning and rostering, as the newer optimization technology is able to examine larger and larger parts of the possible solution spaces.
- Use of mathematical optimization solvers provides a robust solution method that is guaranteed to identify infeasibilities when a solution cannot be found. Manual or heuristic methods can never provide such a guarantee because there is always a doubt that infeasiblity might be due to the less effective solution method.
Economic Benefits
The TOD optimizers provide real dollar cost savings to Air New Zealand by reducing the cost of crewing in areas such as the total number of crew required, the number of hotel bed-nights, meals and other expenses which must be paid to support crew away overseas.
Air New Zealand's flight schedule has considerable variation from week to week, as the airline responds to market opportunities. These minor changes in the flight schedule may significantly impact the costs of the solution, due to the complex inter-related nature of the rules. Solutions created at the time of publishing a schedule may not "survive" a schedule change, or may now be significantly more costly than alternative solutions. The TOD optimizers can be used to re-confirm a solution after changes have been made to the published flight schedule, ensuring that the schedule is crewed as efficiently as possible.
Using the TOD optimizers, a solution can be produced in a matter of minutes, compared with two or more days, to create a manual solution. For example, a B767 pilot TOD problem can be optimally solved in approximately 60 minutes, while the B747-400 pilot TOD problem can be solved in less than five minutes on a standard Sun workstation. These fast solution times have made it possible to provide valuable feedback to the schedules creation process with more proposed schedules now comprehensively evaluated prior to the publication of a new flight schedule. This is a significant intangible benefit to Air New Zealand in that it facilitates the development of robust and profitable flight schedules.
The TOD optimizers reduce Air New Zealand's dependence on a small number of highly skilled staff who must be conversant with the relevant rules and awards, and have sufficient experience to create consistently high-quality manual solutions. These staff now use the TOD optimizers as their core tool to create TOD solutions, which they then analyze, tune and modify using the optimizers to generate the preferred solutions.
The rostering optimizers are "production systems." By the time they are used, the number of crew, the flight schedule and tours of duty are already well defined and specified. The rostering objective is, therefore, to build the best-quality roster possible, where "roster quality" is a concept that is defined from the crews' perspective. The rostering optimizers have improved the quality of the "fair-and-equitable" rosters, and allowed the introduction of a properly optimized "seniority preferential bidding" rostering method for international pilots.
Rosters now take less time to build, with far less manual input, resulting in a reduction in the number of rostering staff from 18 in 1987 to eight today. Roster construction is begun much later and closer to the roster publication date with the result that last-minute changes can be more easily incorporated.
| Airline Crew
Scheduling Problems
Airline crew scheduling involves two distinct processes of planning and rostering. The planning process (also referred to as the pairings problem) involves the construction of a minimum cost set of generic tours of duty (TODs) or pairings which cover all relevant flights (sectors) in an airline flight schedule. Each tour of duty begins and ends at a crew base and consists of an alternating sequence of duty periods and rest periods with duty periods including one or more sectors.
At Air New Zealand, domestic (or national) TODs on B737 aircraft are between one and three days in duration, while for international airline operations on B767 and B747 aircraft, TODs can be up to 14 days in duration. New TODs are constructed for each new flight schedule and for day-to-day variations in an underlying schedule. It should be noted that the construction of TODs does not involve any consideration of the crew members who will actually perform the TODs.
The rostering process involves the allocation of TODs to each crew member of a certain rank so that all flights are crewed with the correctly qualified crew complements and each crew member has a legal, feasible line of work over a given roster period. At Air New Zealand, domestic rosters are built over a 14-day roster period, while international rosters cover a 28-day period. Roster construction must take into account activities rostered in the previous roster period that carry over into the current period. From a crew point of view, it is also important to provide high quality rosters that satisfy crew requests and preferences as much as possible.
During the past two or three decades airlines have invested heavily in the development of optimization techniques to solve their crew scheduling problems. The main reasons for this focus on crew scheduling can be identified in the following major factors.
Many scheduling problems can be formulated mathematically using a set-partitioning model. From a technical point of view, this model is a specially structured zero-one integer linear program that has relatively few constraints but a very large number of variables. Both the planning and the rostering problems of airline crew scheduling can be formulated as set-partitioning problems with special structure. Research conducted at the University of Auckland, in collaboration with Air New Zealand, has resulted in major breakthroughs in the solution of numerous instances of set partitioning models which occur in practical applications. By recognizing the special model structure and incorporating it in the solution methods, it is possible to solve optimization problems that just 10 or 15 years ago were considered far too difficult. In particular, practical instances of the rostering problem can be very large, but it is still possible to produce high-quality solutions. These important technical and implementation developments have involved:
(For complete descriptions, see Ryan and Falkner [1988], Ryan and Osborne [1988] and Ryan [1992]). |
References
- D. M. Ryan and J.C. Falkner, 1988, "On the integer properties of scheduling set partitioning models," European Journal of Operational Research, Vol. 35, p. 442-456.
- D.M. Ryan and M.R. Osborne, 1988, "On the solution of highly degenerate linear programmes," Math Programming, Vol. 41, p. 385-392.
- D.M. Ryan, 1992, "The solution of massive generalised set partitioning problems in aircrew rostering," Journal of the Operational Research Society, Vol. 43, p. 459-467.
- P. R. Day, 1996, "Flight Attendant Rostering for Short-haul Airline Operations," Ph.D. thesis, University of Auckland.
- P. R. Day and D. M. Ryan,1997, "Flight Attendant Rostering for Short-haul Airline Operations," Operations Research, Vol. 45, No. 5, p. 649-661.
- J Waite, 1995, "Language Assignment For Flight Attendant Rostering," Master's Dissertation, University of Auckland.
- M E Thornley, 1993, "Crew Rostering Under A Seniority Preferential Bidding Environment Using Column Generation," Master's Thesis, University of Auckland.
- A P Goldie, 1995, "Optimal Airline Crew Scheduling Using Dynamic Column Generation," Master's Thesis, University of Auckland.
David M. Ryan is a professor of Operations Research and head of the Department of Engineering Science at the University of Auckland in Auckland, New Zealand.
E-mail to the Editorial Department of OR/MS Today: [email protected]
OR/MS Today copyright © 2000 by the Institute for Operations Research and the Management Sciences. All rights reserved.
Lionheart Publishing, Inc.
2555 Cumberland Parkway, Suite 299, Atlanta, GA 30339 USA
Phone: 770-431-0867 | Fax: 770-432-6969
E-mail: [email protected]
URL: http://www.lionhrtpub.com
Web Site © Copyright 1999, 2000 by Lionheart Publishing, Inc. All rights reserved.