Article Outline
Keywords
See also
References
Access provided by Autonomous University of Puebla. Download reference work entry PDF
Similar content being viewed by others
Keywords
- Network design and schedule construction
- Fleet assignment
- Aircraft routing
- Crew scheduling
- Revenue management
- Irregular operations
- Air traffic control and ground delay programs
The airline industry was one of the first to apply operations research methodology and techniques on a large scale. As early as the late 1950s, operations researchers were beginning to study how the developing fields of mathematical programming could be used to address a number of very difficult problems faced by the airline industry. Since that time many airline related problems have been the topics of active research [26]. Most optimization-related research in the airline industry can be placed in one of the following areas:
-
network design and schedule construction;
-
fleet assignment;
-
aircraft routing;
-
crew scheduling;
-
revenue management;
-
irregular operations;
-
air traffic control and ground delay programs.
In the following, each of these problem areas will be defined along with a brief discussion of some of the operations research techniques that have been applied to solve them. The majority of applications utilize network-based models. Solution of these models range from traditional mathematical programming approaches to a variety of novel heuristic approaches. A very brief selection of references is also provided.
Construction of flight schedules is the starting point for all other airline optimization problems and is a critical operational planning task faced by an airline. The flight schedule defines a set of flight segments that an airline will service along with corresponding origin and destination points and departure and arrival times for each flight segment. An airline's decision to offer certain flights will depend in large part on market demand forecasts, available aircraft operating characteristics, available manpower, and the behavior of competing airlines [11,12].
Of course, prior to the construction of flight schedules, an airline must decide which markets it will serve. Before the 1978 ‘Airline Deregulation Act’, airlines had to fly routes as assigned by the Civil Aeronautics Board regardless of the demand for service. During this period, most airlines emphasized long point-to-point routes. Since deregulation, airlines have gained the freedom to choose which markets to serve and how often to serve them. This change led to a fundamental shift in most airlines routing strategies from point-to-point flight networks to hub-and-spoke oriented flight networks. This, in turn, led to new research activities for finding optimal hub [3,18] and maintenance base [13] locations.
Following network design and schedule construction, an aircraft type must be assigned to each flight segment in the schedule. This is called the fleet assignment problem . Airlines generally operate a number of different fleet types, each having different characteristics and costs such as seating capacity, landing weights, and crew and fuel costs. The majority of fleet assignment methods represent the flight schedule via some variant of a time-space network with flight arcs between stations and inventory arcs at each station. A multicommodity network flow problem can then be formulated with arcs and nodes duplicated as appropriate for all fleets that can take a particular flight. Side constraints must be implemented to ensure each flight segment is assigned to only one fleet. In domestic fleet assignment problems, a common simplifying assumption is that every flight is flown every day of the week. Under this assumption, the network model need only account for one day's flights and a looping arc connects the end of the day with the beginning. The resulting models are mixed integer programs [1,16,27,30].
Aircraft routing is a fleet by fleet process of assigning individual aircraft to fly each flight segment assigned to a particular fleet. A primary consideration at this stage is maintenance requirements mandated by the Federal Aviation Administration. There are different types of maintenance activities that must be performed after a given number of flight hours. The majority of these maintenance activities can be performed overnight; however, not all stations are equipped with proper maintenance facilities for all fleets. During the aircraft routing process, individual aircraft from each fleet must be assigned to fly all flight segments assigned to that fleet in a manner that provides maintenance opportunities for all aircraft at appropriate stations within the required time intervals. This problem has been formulated and solved in a number of ways including as a general integer programming problem solved by Lagrangian relaxation [9] and as a set partitioning problem solved with a branch and bound algorithm [10].
As described above, the problems of fleet assignment and aircraft routing have been historically solved in a sequential manner. Recently, work has been done to solve these problems simultaneously using a string-based model and a branch and price solution approach [5].
Crew scheduling , like aircraft routing, is done following fleet assignment. The first of two sequentially solved crew scheduling problems is the crew pairing problem. A crew pairing is a sequence of flight legs beginning and ending at a crew base that satisfies all governmental and contractual restrictions (some times called legalities). These crew pairings generally cover a period of 2–5 days. The problem is to find a minimum cost set of such crew pairings such that all flight segments are covered. This problem has generally been modeled as a set partitioning problem in which pairings are enumerated or generated dynamically [15,17]. Other attempts to solve this problem have employed a decomposition approach based on graph partitioning [4] and a linear programming relaxation of a set covering problem [21]. Often a practice called deadheading is used to reposition flight crews in which a crew will fly a flight segment as passengers. Therefore, in solving the crew-pairing problem, all flight segments must be covered, but they may be covered by more than one crew.
The second problem to be solved relating to crew scheduling is the monthly crew rostering problem. This is the problem of assigning individual crew members to crew pairings to create their monthly schedules. These schedules must incorporate time off, training periods, and other contractual obligations. Generally, a preferential bidding system is used to make the assignments in which each personalized schedule takes into account an employee's pre-assigned activities and weighted bids representing their preferences. While the crew pairing problem has been widely studied, a limited number of publications have dealt with the monthly crew rostering problem. Approaches include an integer programming scheme [14] and a network model [24].
Revenue management is the problem of determining fare classes for each flight in the flight schedule as well as the allocation of available seats to each fare class. Not only are seats on an airplane partitioned physically into sections such as first class and coach, but also seats in the same section are generally priced at many different levels. The goal is to maximize the expected revenue from a particular flight segment by finding the proper balance between gaining additional revenue by selling more inexpensive seats and losing revenue by turning away higher fare customers. A standard assumption is that fare classes are filled sequential from the lowest to the highest. This is often the case where discounted fares are offered in advance, while last minute tickets are sold at a premium. Recent research includes a probabilistic decision model [6], a dynamic programming formulation [31] and some calculus-based booking policies [8].
When faced with a lack of resources, airlines often are not able to fly their published flight schedule. This is frequently the result of aircraft mechanical difficulties, inclement weather, or crew shortages. As situations like these arise, decisions must be made to deal with the shortage of resources in a manner that returns the airline to the originally planned flight schedule in a timely fashion while attempting to reduce operational cost and keep passengers satisfied. This general situation is called the airline irregular operations problem and it involves aircraft, crew, gates, and passenger recovery.
The aircraft schedule recovery problem deals with re-routing aircraft during irregular operations. This problem has received significant attention among irregular operations topics; papers dealing with crew scheduling during irregular operations have only recently started to appear [28,35]. Most approaches for dealing with aircraft schedule recovery have been based on network models. Some early models were pure networks [19]. Recently, more comprehensive models have been developed that better represent the problem, but are more difficult to solve as side constraints have been added to the otherwise network structure of these problems [2,33,36]. In practice, many airlines use heuristic methods to solve these problems as their real-time nature does not allow for lengthy optimization run times.
Closely related to the irregular operations problem is the ground delay problem in air traffic control. Ground delay is a program implemented by the Federal Aviation Administration in cases of station congestion. During ground delay, aircraft departing for a congested station are held on the ground before departure. The rational for this behavior is that ground delays are less expensive and safer than airborne delays. Several optimization models have been formulated to decrease the total minutes of delay experienced throughout the system during a ground delay program. These problems have generally been modeled as integer programs ([22,23]), but the problem has also been solved using stochastic linear programming [25] and by heuristic methods [34].
Optimization based methods have also been applied to a myriad of other airline related topics such as gate assignment [7], fuel management [29], short term fleet assignment swapping [32], demand modeling [20], and others. Airline industry is an exciting arena for the interplay between optimization theory and practice. Many more optimization applications in the airline industry will evolve in the future.
See also
References
Abara J (1989) Applying integer linear programming to the fleet assignment problem. Interfaces 19(4):20–28
Argüello MF, Bard JF, Yu G (1997) Models and methods for managing airline irregular operations aircraft routing. In: Yu G (ed) Operations Research in Airline Industry. Kluwer, Dordrecht
Aykin T (1994) Lagrangian relaxation based approaches to capacitated hub-and-spoke network design problem. Europ J Oper Res 79(3):501–523
Ball M, Roberts A (1985) A graph partitioning approach to airline crew scheduling. Transport Sci 19(2):107–126
Barnhart C, Boland NL, Clarke LW, Johnson EL, Nemhauser G, Shenoi RG (1998) Flight string models for aircraft fleeting and routing. Transport Sci 32(3):208–220
Belobaba PP (1989) Application of a probabilistic decision model to airline seat inventory control. Oper Res 37:183–197
Brazile RP, Swigger KM, Wyatt DL (1994) Selecting a modelling technique for the gate assignment problems: Integer programming, simulation, or expert system. Internat J Modelling and Simulation 14(1):1–5
Brumelle SL, McGill JI (1993) Airline seat allocation with multiple nested fare classes. Oper Res 41(1):127–137
Daskin MS, Panagiotopoulos ND (1989) A Lagrangian relaxation approach to assigning aircraft to routes in hub and spoke networks. Transport Sci 23(2):91–99
Desaulniers G, Desrosiers J, Dumas Y, Solomon MM, Soumis F (1997) Daily aircraft routing and scheduling. Managem Sci 43(6):841–855
Dobson G, Lederer PJ (1993) Airline scheduling and routing in a hub-and-spoke system. Transport Sci 27(3):281–297
Etschamaier MM, Mathaisel DFX (1985) Airline scheduling: An overview. Transport Sci 9(2):127–138
Feo TA, Bard JF (1989) Flight scheduling and maintenance base planning. Managem Sci 35(12):1415–1432
Gamache M, Soumis F, Villeneuve D, Desrosiers J (1998) The preferential bidding system at Air Canada. Transport Sci 32(3):246–255
Graves GW, McBride RD, Gershkoff I, Anderson D, Mahidhara D (1993) Flight crew scheduling. Managem Sci 39(6):736–745
Hane CA, Barnhart C, Johnson EL, Marsten RE, Nemhauser GL, Sigismondi G (1995) The fleet assignment problem: Solving a large-scale integer program. Math Program 70(2):211–232
Hoffman KL, Padberg M (1993) Solving airline crew scheduling problems by branch-and-cut. Managem Sci 39(6):657–680
Jaillet P, Song G, Yu G (1997) Airline network design and hub location problems. Location Sci 4(3):195–212
Jarrah AIZ, Yu G, Krishnamurthy N, Rakshit A (1993) A decision support framework for airline flight cancellations and delays. Transport Sci 27(3):266–280
Jorge-Calderon JD (1997) A demand model for scheduled airline services on international European routes. J Air Transport Management 3(1):23–35
Lavoie S, Minoux M, Odier E (1988) A new approach for crew pairing problems by column generation with an application to air transportation. Europ J Oper Res 35:45–58
Luo S, Yu G (1997) On the airline schedule perturbation problem caused by the ground delay program. Transport Sci 31(4):298–311
Navazio L, Romanin-Jacur G (1998) The multiple connections multi-airport ground holding problem: Models and algorithms. Transport Sci 32(3):268–276
Nicoletti B (1975) Automatic crew rostering. Transport Sci 9(1):33–48
Richetta O, Odoni AR (1993) Solving optimally the static ground-holding policy problem in air traffic control. Transport Sci 27(3):228–238
Richter H (1989) Thirty years of airline operations research. Interfaces 19(4):3–9
Rushmeier RA, Kontogiorgis SA (1997) Advances in the optimization of airline fleet assignment. Transport Sci 31(2):159–169
Stojkovic M, Soumis F, Desrosiers J (1998) The operational airline crew scheduling problem. Transport Sci 32(3):232–245
Stroup JS, Wollmer RD (1992) A fuel management model for the airline industry. Oper Res 40(2):229–237
Subramanian R, Scheff RP Jr, Quillinan JD, Wiper DS, Marsten RE (1994) Coldstart: Fleet assignment at delta air lines. Interfaces 24(1):104–120
Tak TC, Hersh M (1993) A model for dynamic airline seat inventory control with multiple seat bookings. Transport Sci 27(3):252–265
Talluri KT (1993) Swapping applications in a daily airline fleet assignment. Transport Sci 30(3):237–248
Thengvall BT, Bard JF, Yu G (2000) Balancing user preferences for aircraft schedule recovery during airline irregular operations. IEE Trans Oper Eng 32(3):181–193
Vranas PB, Bertsemas DJ, Odoni AR (1994) The multi-airport ground-holding problem in air traffic control. Oper Res 42(2):249–261
Wei G, Song G, Yu G (1997) Model and algorithm for crew management during airline irregular operations. J Combin Optim 1(3):80–97
Yan S, Tu Y (1997) Multifleet routing and multistop flight scheduling for schedule perturbation. Europ J Oper Res 103(1):155–169
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2008 Springer-Verlag
About this entry
Cite this entry
Yu, G., Thengvall, B. (2008). Airline Optimization . In: Floudas, C., Pardalos, P. (eds) Encyclopedia of Optimization. Springer, Boston, MA. https://doi.org/10.1007/978-0-387-74759-0_7
Download citation
DOI: https://doi.org/10.1007/978-0-387-74759-0_7
Publisher Name: Springer, Boston, MA
Print ISBN: 978-0-387-74758-3
Online ISBN: 978-0-387-74759-0
eBook Packages: Mathematics and StatisticsReference Module Computer Science and Engineering