International OR
Air Canada Reaches 'Altitude'
Preferential Bidding System helps carrier integrate 1,400 pilots following acquisition of Canadian Airlines
By Jacques Desrosiers
Scheduling crew members is a complex problem for any airline under normal conditions, but imagine how difficult the problem becomes if the airline's number of pilots increases more than 60 percent almost overnight. That was the situation Air Canada faced last year when the airline acquired Canadian Airlines and saw the number of pilots on its roster zoom from 2,200 to 3,600. Looking for solutions, Air Canada headed for AltitudeTM PBS, a preferential bidding system developed by Montreal-based AD OPT Technologies Inc.
Altitude is a suite of advanced planning and scheduling applications used for workforce planning, scheduling and management for both passenger and cargo airlines. At a time when airlines are increasingly challenged to improve operational efficiency, the Altitude product line supports the deployment of pilots and crew members in a way that addresses the needs of both airline management and its crew. Air Canada was AD OPT's first Altitude PBS customer, and the airline was instrumental in the initial development of the software. Air Canada now uses PBS to generate the personalized flight schedules of the newly integrated Canadian Airlines' pilots.
Figure 1: The Altitude product family.
The Altitude product line is powered by GENCOL, a state-of-the-art column generation optimizer. GENCOL is the result of nearly 20 years of collaborative research among four Montreal universities in the field of advanced mathematics and operations research. Based on the Air Canada experience, a system such as Altitude PBS is capable of generating annual savings of 5 percent or more in total labor and related expenses, which can be worth millions of dollars a year to comparable airlines.
Altitude PBS allows crew members greater participation in the scheduling process while enhancing scheduling efficiency, thus balancing the interests of employees and airline management while bringing an important quality-of-life aspect to those scheduled. It is a comprehensive system for assembling crew pairings built within single or multi-domicile contexts into personalized lines that respect the collective agreement and pre-assigned ground task. More importantly, such monthly blocks for flight deck and cabin crewmembers also take into consideration personal preferences (expressed as bid options).
Altitude PBS is composed of three components: the Bidder Interface, the Scheduler Interface and the Optimizer. Crewmembers use the Bidder Interface to specify their individual personal preferences from an extensive menu of choices. Planners use the Scheduler Interface to control the construction of lines while the Optimizer generates the monthly blocks.
Traditionally, blocks are built first, and crew members bid on their preferred one. With the Altitude PBS Bidder Interface, crew members are able to tailor their duty around their individual needs based on a wide spectrum of personal bid options. Employees can submit an unlimited number of bids either from home or remote locations using an e-Scheduling module available on the Internet or via designated terminals located in airport pilot lounges.
Altitude PBS enhances scheduling efficiencies by building around carryover and known absences (vacation, training, etc.). The system is fast and fully automated and gives airlines full control over open time. Using the Planner Interface, planners can end bid periods, control line-construction constraints, reserve coverage, save or delete solutions, archive solutions and prepare files for other systems.
Altitude PBS has no built-in bias towards the airline or its crew; the objective is to deliver a quality solution for all concerned. Powered by GENCOL, the Altitude PBS Optimizer determines the optimal way to accommodate the preferences of each crew member, taking into consideration the pairings of the bid period, the line construction constraints and the airline's global objectives (open-time volume and distribution, as well as reserve distribution). The Altitude PBS Optimizer produces regular, relief and reserve lines and uses a global approach to maximize the awarding of crew preferences based either on seniority or equity privileges.
From an operations research perspective, preferential bidding presents an interesting problem. To account for his personal work preferences, a pilot draws up a list of bids and associates a weight with each one. Afterwards, these weights are used to evaluate the score of its potential blocks. For example, he may indicate preferences for a specific pairing, a rest period, a weekend off or flight departures after 8 a.m. A bid may also affect the entire schedule; for example, the pilot may prefer a schedule that has at least 74 flight hours. At Air Canada, about 75 different kinds of bid options are available.
The mathematical problem can be formulated as a generalized set-partitioning model. When looking at a direct approach to solve it, the weights must be chosen so as to differentiate the bids selected by a pilot and to reflect the priority of a senior over juniors. Given the number of bids a pilot can make, it requires a 32-bit computer word to differentiate them. Therefore, the score of a pilot is an integer number that can be as large as 109. To reflect the strict seniority between two pilots, 64 bits are necessary, which makes the number closer to 1019. Given 200 pilots, seniority restrictions require a score function taking values up to 101927. This huge number is larger than the number of elementary particles in the universe!
Decisions are sometimes easy to make when there is only one alternative. It is inevitable that the score function imposes a sequential solution process. However, this apparent simplicity conceals several traps. To solve a 200-pilot problem, one has to solve 200 integer programs, and it is difficult enough to solve a single one by column generation. If we are unable to get a feasible solution for one of the pilots, the overall process does not reach its conclusion.
Figure 2: Altitude PBS components.
It took about two months to design a prototype for Altitude PBS. The GENCOL optimizer developed at the GERAD research center in Montreal was used to solve the sequence of problems. This optimizer uses a branch-and-bound algorithm where the linear relaxation of the generalized set partitioning formulation is solved at each node using column generation. This method proceeds by alternately solving a master problem and then the sub-problems. The master problem is a linear program defined on the current set of blocks. The CPLEX optimizer, which is the core module of GENCOL, obtains its optimal solution and provides dual variables used to price out new blocks.
Solving the sub-problems (one associated with each residual pilot) generates the blocks. These are defined as constrained longest-path problems and solved by a specialized dynamic programming algorithm. The column generation stops when no blocks can improve the master problem solution. At this point, branch-and-bound starts using branching and cutting plane decisions and new blocks are generated as needed at each node of the enumeration tree.
The Story Behind the Prototype
The design of the Altitude PBS prototype posed a challenge for AD OPT staff. Two days before Air Canada representatives were scheduled to examine the preliminary results and decide if the project would proceed or not, AD OPT encountered difficulties on the computational side while working on two test problems provided by the airline. The GENCOL optimizer was insufficient. On a number of specific pilot problems, the solution of the linear relaxation was distant from any integer solution. Integrality gaps sometimes reached 99 percent, an awful situation! When the gaps were small, the experience allowed AD OPTS to find a solution. This time, though, the gaps were truly excessive. Running the optimizer all night did not provide a feasible solution.
François Soumis and I were out of town attending the INFORMS meeting in Boston. Partners since 1981, we developed the fundamentals of the column-generation method and applied them to various vehicle-routing and crew-scheduling problems. Back in Montreal, Éric Gélinas, the programmer-analyst in charge of the PBS project, was growing increasingly nervous.
After a brief telephone discussion, François, a real operations research guru, proposed an "original" idea that he had used 25 years earlier to solve a single-machine scheduling problem. We agreed to implement an innovative cutting plane that, fortunately for us, was compatible with our column-generation approach. The cutting plane added a supplementary dimension to the constrained longest-path problem but kept the problem within the same combinatorial family.
Éric immediately comprehended the new concept and all the programming and structural implications required within the GENCOL optimizer. One hour later, he called us back. "These cutting planes are unbelievable," he said. "The integrality gaps are completely dropping off with very few cuts." The two test problems were easily solved and the meeting with Air Canada was a complete success.
|
References
- 1. M. Gamache, F. Soumis, D. Villeneuve, É. Gélinas and J. Desrosiers (1998), "The Preferential Bidding System at Air Canada," Transportation Science Vol. 32, No. 3, p. 246-255.
- 2. J. Desrosiers, Y. Dumas, M.M. Solomon and F. Soumis (1995), "Time Constrained Routing and Scheduling, in Handbooks in OR & MS 8," M.O. Ball et al. (eds.), Elsevier Science B.V.
Jacques Desrosiers is professor at École des Hautes Études Commerciales, Montréal, in the Quantitative Methods for Management Department.
OR/MS Today copyright © 2001 by the Institute for Operations Research and the Management Sciences. All rights reserved.
Lionheart Publishing, Inc.
506 Roswell Street, Suite 220, Marietta, GA 30060, USA
Phone: 770-431-0867 | Fax: 770-432-6969
E-mail: lpi@lionhrtpub.com
URL: http://www.lionhrtpub.com
Web Site © Copyright 2001 by Lionheart Publishing, Inc. All rights reserved.