Airline Optimization

Researchers at IBM have played a fundamental role in the development of the underlying mathematical optimization technology for airline scheduling problems. In the case of fleet assignment, IBM researchers have worked with airlines to exploit the structure of the problem and devised improved integer programming technology. These improvements have enabled the solution of complex and highly constrained fleet assignment problems with several thousand flights and hundreds of aircraft. In the case of crew scheduling, where the challenges are even greater, IBM has pioneered global solution approaches that have resulted in fun crew management decision support solutions. The success of IBM in solving these vast comprehensive models is largely due to investment in advancing core optimization methods, such as those in the Optimization Solutions Library (OSL), the Volume algorithm and the Branch-and-Cut-and-Price (BCP) framework for high performance parallel computer architectures. Through work with the financial and utility industries, IBM researchers have also made significant strides in the area of stochastic optimization, which will likely prove to be very important in future airline models. IBM Research is also using simulation models to help airlines understand the impact that new technologies, such as self-service kiosks, voice-recognition check-in, smart cards and electronic ticketing, can have on bottlenecks, personnel needs and customer service levels.

Crew Pairing Optimization


The area of crew pairing optimization continues to pose challenging problems to both scientists and software engineers. The basic problem is to partition a given schedule of flights into individual flight sequences called pairings, that each start and end at a crew domicile. What makes the problem difficult are a plethora of crew work rules and FAA safety regulations that govern pairing construction. Another complication is that the projected cost of a pairing depends on complex crew pay guarantees. Also, the number of possible pairings is extremely large for many airlines.

Over the last five years, IBM has developed a solution called the Crew Pairing Optimization System (CPOS) in collaboration with the Sabre group. CPOS is currently used by US Airways and Southwest Airlines. In its 1996 annual report, US Airways cited CPOS as saving the company $50 million annually. In a 1998 IBM press release, Al Davis, vice president of special projects at Southwest, said "It previously would take a team of six to eight people several weeks to complete the entire crew pairing process with every schedule change, which was happening with increasing frequency given market dynamics and new aircraft deliveries. Now, CPOS generates daily, weekend and transition pairing solutions in a fraction of that time, while reducing aircraft ground time, crew work hours, flight schedule costs and, more importantly, improving quality of life for airline crews and schedulers."

CPOS uses a combined linear programming and integer programming approach (LP/IP) based on a set partitioning problem (SPP) formulation where the rows are flights and the columns are pairings. The problem is to select the least cost partition from a pool of candidate pairings. CPOS first solves the LP using a method called Sprint pioneered at IBM and based on core solvers in OSL. It then employs a branching rule based on how flights connect in the LP solution in order to obtain the integer solution. A key IBM innovation concerns the generation of a very good starting pool of candidate pairings for the LP/IP approach. Here a column generator produces pairings based on approximate LP duals from a new IBM subgradient method called the Volume algorithm. Computational experience shows that the Volume duals are much better seeds for column generation than LP duals, and are also much easier to compute. Additionally, the final Volume duals provide an advanced starting basis for the LP/IP approach.

Crew Trip Repair


Repairing broken crew trips is a daily airline activity in the face of disruptions such as bad weather, unscheduled aircraft maintenance, air traffic congestion, flight cancellations or delays, and sick or illegal crews. Trip repair usually follows flight cancellation and aircraft rerouting decisions, but often flight dispatchers and crew schedulers coordinate to explore the best options. Trip repair is a hard problem because of complex crew work rules, complex crew cost computations, changing objectives and having to explore many options. Often, due to time pressures, airlines are forced to implement the first solution found. Airline investment in technologies to expedite trip repair and reduce crew costs has increased in recent years.

IBM developed a trip repair prototype (TRP) as part of a contract with US Airways in 1997. A unique feature of TRP is to simulate disruptions ranging from simple flight cancellations to severe snowstorms. This feature has proved very useful for validating the system and gaining rapid user acceptance. TRP also reports broken trips and open flights resulting from a disruption.

The solution approach involves iterations through column generation and optimization, based on a SPP formulation where the columns are trip proposals and the rows refer to both flights and non-reserve crews. The solution strategy is to see if the problem can be fixed by swapping flights among only the impacted crew, and bringing in reserves and other non-disrupted crews as needed. This strategy ensures fast solution times and keeps the problem relatively small. Many heuristics are used to localize the search during column generation. Computational experience indicates that for simple events solution time is on the order of seconds and for more severe events, the times are on the order of minutes.

Journey Management


The IBM Journey Management Library (IBM JML) is a decision-support tool for quickly building simulation models toward the goal of improving airline passenger processing. The fast growth in airline passenger traffic, combined with the slow growth in airport capacity worldwide, is putting a severe strain on the capability of airlines to adapt their processes to maintain satisfactory levels of customer service. The IBM JML is targeted for use by airline and airport authority business process analysts, planners, operations personnel and operations research experts throughout the organization to plan for improvements in existing or proposed terminal facilities. Simulation models built using the IBM JML, an Arena Professional Edition solution, are helpful in understanding what impact new technologies, such as self-service kiosks, smart cards and electronic ticketing, will have on bottlenecks, personnel needs and customer service levels. These models also incorporate fixed, variable and process-related (i.e., per transaction) costs so that financial comparisons can be made between proposed scenarios before actually investing in new information technology. The IBM JML has a Visual Basic for Applications interface to Microsoft Excel 97 making it easy to quickly import or export parametric data for a simulation model. Design and development of the IBM Journey Management Library was a collaborative effort between IBM Corporation, Air Canada and Systems Modeling Corporation.

IBM and Air Canada have developed a simulation model of domestic passenger processing and baggage handling for Toronto Airport. Jim Ohlsson, director of Air Canada's Commercial Business Unit/Information Technology, says "IBM's Journey Management Library will help identify and plan timely solutions that keep us ahead in this very competitive market." Ohlsson is heading a project to introduce self-service kiosks as a remedy to growing passenger queues at check-in. "I wanted to learn as much as I could without piloting this in real life. With simulation, we hoped to assess the impact of customers using kiosk check-in and agent-assisted check-in. While new technology is important, we also need to look at how existing processes can be improved."

Air Canada has concluded that the ticketing, check-in and baggage drop-off processes represent an opportunity to use self-service kiosks to improve throughput. Air Canada has completed a successful pilot implementation of IBM kiosks at their Ottawa airport facilities, where 15 kiosks are in use today. Based on the success realized at Ottawa Airport, Air Canada plans to install IBM kiosks at Toronto Airport in the near future. Use of the IBM Journey Management Library is expanding within Air Canada to model Montreal Airport. The airline realizes that the appropriate application of advanced technology can improve customer service, reduce costs and better utilize assets. Simulations, according to Ohlsson, will play an increasingly critical role in operations and planning at Air Canada as an aid to selecting cost-effective technologies and streamlining processes.

Optimization Technology Advancements


IBM continues to make significant technology advancements in the field of solving large-scale mixed integer programs. Two recent advancements are the Volume Algorithm for linear programming and the Branch-and-Cut-and-Price (BCP) framework for mixed integer programming.

Volume Algorithm. Linear programs coming from certain areas like network design, facility location, crew scheduling and airline schedule planning might involve hundreds of thousands of variables. Traditional LP methods like simplex and interior point algorithms might take several hours to find an exact solution, even when an approximate solution suffices. IBM has developed the so-called Volume Algorithm to rapidly produce approximate LP solutions. The Volume Algorithm is named after a new way of looking at LP duality, using volumes below the active faces to compute the dual variables and the direction of movement.

This algorithm is an extension of the subgradient algorithm which is known to produce good dual solutions with low computational effort. However, the subgradient algorithm does not produce primal solutions. In contrast, the Volume Algorithm not only finds primal values, but also achieves better convergence than traditional subgradient methods.

The Volume Algorithm is easy to implement, requires minimal storage, decreases dramatically the computing time, and can be parallelized in a natural way. Another advantage of the volume algorithm is that its duals are better than simplex duals in accelerating column generation schemes, such as Dantzig-Wolfe decomposition. Excellent computational results have been achieved for LPs arising from a variety of combinatorial problems.

Branch-and-Cut-and-Price. BCP is a development framework for parallel implementation of problem class specific Branch-and-Cut-and-Price algorithms that use LP relaxations with variable and constraint generation at the sub-problems. Constraint (cut) generation strengthens the LP relaxation at the sub-problems, while variable (column) generation extends their feasible regions. Parallelism is achieved by processing the sub-problems simultaneously. A master-slaves model is employed where the master oversees the distribution of the subproblems and the slaves process them. Communication between master and slaves uses a message passing module which allows execution either sequentially or in a distributed parallel environment.

BCP handles the general tasks common in (parallel) Branch-and-Cut-and-Price algorithms, while the developer provides only the problem class specific routines through C++ virtual classes. User routines may include input/output management, preprocessing, heuristic upper bounding, and both variable and constraint generation. Interfacing with the framework for a specific problem class is facilitated in two ways. First, the design allows easy incorporation of already existing code base. Second, there is an extensive collection of default options for performing various tasks, such as testing feasibility, selecting branching objects, and communicating an LP solution to the cut generator.

BCP contains an extensive list of state-of-the-art features such as the use of cut and variable pools, reduced cost fixing, strong branching, an extended notion of branching objects, multi-way branching and warmstarting. The modular design of BCP allows for the use of various message passing protocols and LP solvers.

Future Research Directions


Current research in crew pairing optimization at IBM focuses on reducing the computational time and creating a more robust system using the BCP framework. An implementation using BCP has numerous advantages. The framework facilitates column and cut generation at search tree nodes to improve solution quality using local information, such as the current primal/dual solution. Also, using the parallel nature of BCP, execution can easily be spread out to utilize all available computing power. Finally, various LP solvers, including the Volume Algorithm described above, can be easily adapted.

IBM is now working with Southwest Airlines to prove the technology in TRP. Southwest operates a single fleet of more than 250 aircraft performing more than 2,300 daily departures. The difficulty here is to identify aset of crews who can potentially alleviate a schedule disruption. IBM is researching the use of relaxed multi-commodity flow problems to address this challenge.

IBM has recently focused its attention on the Schedule Planning problem combining fleet assignment, routing and market demand requirements into a single model. There are two manifestations of this problem: strategic and tactical planning. First, determine a global solution to strategic problems such as increasing market share, improving resource utilization and meeting performance standards. Second, determine a tactical solution for daily, weekly, and holiday or transition schedules.

Despite the sophistication of airline mathematical optimization techniques, the approaches to date have largely been deterministic in nature. Frequently, much better solutions can be obtained by modeling some of the parameters as random variables and applying stochastic programming methods. IBM's Stochastic Extensions to OSL (SEOSL) allows a richer solution to transportation problems in which uncertainty plays a key role.

SE-OSL provides the functionality needed for managing the stochastic programming core model, timing and uncertainty elements. SE-OSL internally structures the model for effective solution using a parallelizable decomposition method. Once solved, a variety of information about the solution can be obtained, including probability distributions.

We are investigating the use of stochastic programming in our work on fleet planning and assignment problems, as well as issues in the pricing of transportation and other services. This work shows promise in providing solutions that are much more robust in their response to actual operations than deterministic formulations.

References



- Anbil, R., J. J. Forrest, and W. R. Pulleyblank, "Column Generation and the Airline Crew Pairing Problem," Documenta Mathematica, Extra Volume ICM, 1998.


- Barahona, F., and R. Anbil, "The Volume Algorithm: Producing Primal Solutions with a Subgradient Method," IBM Research Report RC 21103(94395), IBM T. J. Watson Research Center, Yorktown Heights, N.Y., October 1997.


- Bitauld, P., K. Burch, S. El-Taji, E. Fanucchi, M. Montevecchi, J. Ohlsson, A. Palella, R. Rushmeier, and J. Snowdon, "Journey Management," OR/MS Today, Vol. 24, No. 5, 1997, pp.30-33.


- Snowdon, J., S. El-Taji, M. Montevecchi, E. MacNair, C. A. Callery, and S. Miller, "Avoiding the Blues for Airline Travelers," Proceedings of the 1998 Winter Simulation Conference, eds. D. J. Medeiros, Edward F. Watson, John S. Carson, and Mani S. Manivannan, 1998, pp.1105-1112.



Ranga Anbil is manager of Network Logistics at the IBM T.J. Watson Research Center specializing in applied large scale optimization. He holds a Ph.D. in Operations Research from Ohio State University.

Francisco Barahona is a research staff member at IBM's T.J. Watson Research Center. He specializes in combinatorial optimization and integer programming. He received his Ph.D. in Operations Research from the University of Grenoble, France.

Laszlo Ladanyi is a postdoctoral associate at the IBM T.J. Watson Research Center. He received his Ph.D. from Cornell University, where he was also a postdoctoral associate before joining IBM.

Russell Rushmeier is a research staff member at IBM's T.J. Watson Research Center working on applications of large-scale mathematical optimization. He received his Ph.D. from Cornell University, and has held positions as an assistant professor at the Georgia Institute of Technology and principal consultant with US Airways.

Jane L. Snowdon is a research staff member at IBM's T. J. Watson Research Center and specializes in mathematical optimization, simulation and business process reengineering. She holds a Ph.D. from the Georgia Institute of Technology in Industrial and Systems Engineering.