Airline planning and scheduling: Models and solution methodologies

Abstract

The airline industry is a representative industry with high cost and low profitability. Therefore, airlines should carefully plan their schedules to ensure that overall profit is maximized. We review the literature on airline planning and scheduling and focus on mathematical formulations and solution methodologies. Our research framework is anchored on three major problems in the airline scheduling, namely, fleet assignment, aircraft routing, and crew scheduling. General formulation, widely used solution approaches, and important extensions are presented for each problem and integrated problems. We conclude the review by identifying promising areas for further research.

Graphical abstract

Keywords

airline planning / fleet assignment problem / aircraft routing problem / crew pairing problem / crew rostering problem / crew scheduling problem / integrated planning

1 Introduction

The aviation industry has played an integral role for creating global economic prosperity in the past decades. This industry has displayed continuous growth and vibrancy given the rapidly increasing number of airline passengers, particularly in developing countries. Global passenger traffic, which is measured in revenue passenger kilometers (RPK), is predicted to grow at 4.1% annually from 2015 to 2045 (the International Civil Aviation Organization (ICAO), 2018). More than 4.5 billion passengers were transported by commercial airlines in 2018 (Mazareanu, 2019), which was the 9th consecutive year that RPK grew above the trend (International Air Transport Association (IATA), 2019). To satisfy additional demand, aircraft should be flown more intensively than before, and the number of scheduled flights is predicted to reach 39.8 million in 2019, which is about 76 aircraft departures per minute on average (IATA, 2018). That is, the global flight network becomes increasingly complex.

To accommodate the market and support the expansion of the flight network, the in-service fleet is expected to grow at an average annual rate of 3.4%, and new aircraft delivers are forecasted to top 44000, which are valued at over $6 trillion (Boeing, 2019a). Consequently, 804000 new pilots and 914000 new cabin crews are needed over the next 20 years for the aviation industry (Boeing, 2019b). However, the industry faces a worldwide crew shortage stemming from a mix of the dwindling number of crews supplied by the military, retirement of skilled crews, and lack of available training facilities (AINonline, 2017; Gall, 2018).

The airline industry is a representative industry with high cost, high revenue, and low profit. Fuel and crew costs and aircraft depreciation account for the major airline expenses. Airbus released a price list and indicated that an aircraft could cost $80–500 million (Airbus, 2018). For example, Airbus A320 costs $101.1 million each, and the price of Airbus A380 exceeds $440 million. Airlines also spend a considerable amount for crew resources. Depending on the airline, fleet, and experience level, a pilot earns approximately $70000 to $300000 per year in America (Phoenix East Aviation (PEA), 2019). In 2019, airline costs are expected to grow to 7.4%, thereby outpacing the 6.5% anticipated growth in sales (Goldman, 2019). IATA states that airline margins are squeezed by rising fuel prices and substantial weakening of world trade in 2019 (Goldman, 2019). In addition, online travel agencies present ticket prices with transparency to passengers. Thus, airlines should match the market fares to maintain their share. All these factors aggravate the airlines’ low profitability.

As mentioned above, the scale of the network is large, operations involving expensive aircraft and crews are complex, and profit margins remain low. Therefore, the mechanism of how profit-maximizing schedules are made poses a tremendous challenge for airlines (Barnhart and Cohn, 2004; Belobaba et al., 2009). Fortunately, since the 1960s, operations research (OR) has played a critical role in the development of the aviation industry because its techniques and models find natural contexts for application in the air transport environment (Barnhart et al., 2003a). More than 2800 professionals are recognized as present members of the Airline Group of Operational Research Societies (AGIFORS), and they represent more than 500 airlines, airline manufacturers, universities, and aviation-related companies and associations (AGIFORS, 2019). In academia, the Institute for Operations Research and the Management Sciences (INFORMS) Annual Meeting, which is the world’s largest OR and analytics conference, established the Aviation Application Section of INFORMS to encourage the development and dissemination of applications and research in areas relating to aviation (INFORMS, 2019).

An airline’s products are defined by its schedule planning (Barnhart and Smith, 2012). Airline scheduling is an enormous and complex challenge that involves thousands of flights per day, hundreds of aircraft, complex regulations related to crew fatigue control, and air traffic control, among others (Barnhart and Cohn, 2004; Cadarso and de Celis, 2017). This problem is generally divided into sequential sub-problems, namely, schedule design problem (SDP), fleet assignment problem (FAP), aircraft routing problem (ARP), and crew scheduling problem (CSP) (Rushmeier and Kontogiorgis, 1997; Stojković and Soumis, 2001; Belobaba et al., 2009; Sherali et al., 2010; Shao et al., 2017). CSP could be further divided into crew pairing problem (CPP) and crew rostering problem (CRP). SDP develops the timetable of flights that contains the origin and destination airports along with the departure and arrival time of each flight. FAP subsequently assigns an aircraft type (i.e., fleet) for each flight to maximize the expected airline profit. After the flight schedule is developed and fleets are assigned to every flight, ARP assigns an aircraft for each flight while satisfying the maintenance requirements. Afterward, CSP allocates the crew to flights without violating the related crew regulations. To the best of our knowledge, SDP is generally determined by the airline marketing department based on empirical and the market considerations. The flight schedule decision is affected by the long-term goal of the airline and the growth of the regional and global economy. Although numerous researchers tackle SDP from different perspectives, no universally well-recognized model is available. Hence, we focus on the latter three problems, namely, FAP, ARP, and CSP. In particular, we present the motivations, mathematical formulations, and solution approaches for these problems and summarize the literature by comparing the different methods and providing scientific and industrial insights.

Deveci and Demirel (2015), Kasirzadeh et al. (2017), and Eltoukhy et al. (2017) recently conducted reviews and focused on one or more of the aforementioned problems. Deveci and Demirel (2015) and Kasirzadeh et al. (2017) reviewed CSP. Deveci and Demirel (2015) focused on CPP by emphasizing recent studies and solution methodologies. Kasirzadeh et al. (2017) presented a comprehensive problem definition of CSP and reviewed existing problem formulations and solution methodologies. Eltoukhy et al. (2017) reviewed the literature on the four sub-problems of airline planning. Different from the existing reviews, we focus more on the mathematical modeling of different problems and extensions.

The remainder of the paper is organized as follows. Section 2 illustrates the basic model, important model extensions, and solution methods for FAP. Section 3 describes the ARP in detail. Section 4 presents the CSP that consists of the CPP and CRP. Section 5 describes the integration of two or more scheduling problems. Moreover, Section 6 briefly summarizes and presents several potential future research directions.

2 Fleet assignment problem

The FAP aims to determine the fleet (i.e., type of aircraft) for each flight (Hane et al., 1995; Bélanger et al., 2006a; Salazar-González, 2014) in a given flight schedule. Generally, an airline operates heterogeneous fleets. Aircraft of the same fleet constantly have similar requirements on aircraft maintenance and crew qualification and similar capacity (depending on the specific interior layout). A typical FAP covers the scheduled flights with limited aircraft resources to maximize the profit. Given that aircraft seats are considered the perishable product with high operating costs, the FAP should provide the “right number” of seats to passengers (Sherali et al., 2006).

In this section, we introduce two basic models based on different network structures. We also discuss the enhanced models with various operational and industrial considerations and subsequently present the solution approaches.

2.1 Basic fleet assignment model

The FAP is typically formulated as a mixed integer programming problem under the daily-schedule assumption (i.e., every flight repeats daily). There are two classical methods to construct the flight network, namely the connection network and the time–space network. The fleet assignment model (FAM) is presented based on connection and time–space networks in this section.

2.1.1 FAM based on the connection network

The connection network was introduced by Abara (1989) (Fig. 1). In the connection network, each airport has two timelines, namely, departure and arrival. Nodes represent the time points of the departure and arrival of legs. The connection network uses three types of arcs, which are leg arcs, connection arcs, and original/terminal arcs. The leg arcs represent different flights between airports. The connection arcs signify the possible aircraft connection between an arrival flight and a departure flight. The original arcs represent aircraft departing from the airport at the beginning of the day, and the terminal arcs represent aircraft arriving and remaining at the airport for the rest of the day.

The basic idea of the fleet assignment model is to assign a sub-network for each fleet, and thus, the flights in each fleet sub-network can be flown by aircraft in that fleet. All the fleet sub-networks are bundled by the set of the cover constraints, which ensure that every flight is assigned in one of the fleet sub-networks.

With the following notation, the basic mathematical formulation of connection-based FAM is given in Eqs. (2.1)–(2.6).

Model 2.1 Basic FAM based on the connection network

In this model, the objective function in (2.1) consists of two parts. The first part is the profit obtained by all legs and connections, and the second part is the cost of the number of aircraft used. Here, {{\displaystyle \sum }}_{j\in L}{x}_{\mathrm{0}jk} counts the total number of used aircraft for fleet k. The cover constraints (2.2) require each leg to be covered exactly once. The equipment continuity constraints (2.3) require that the two connections that begin or end at the same leg should be covered by the same fleet. Thus, the network flow balance is maintained. The schedule balance constraints (2.4) ensure that the number of aircraft originating from a station at the beginning of a day equals to the number of aircraft terminating at the end of the same day. Thus, the schedule can be repeated daily. The aircraft count constraints (2.5) ensure that the number of aircraft used does not exceed the total number of available aircraft for each fleet.

The equipment continuity constraints (2.3) and the schedule balance constraints (2.4) can be merged into flow balance constraints by introducing dummy source/sink nodes and dummy arcs for each airport (see Fig. 2). Given an airport, the dummy source node is the start-day node that connects all legs departing from the airport. Similarly, the dummy sink node is the end-day node that connects all legs arriving at the airport. The dummy arc, which is called wrap-around arc, starts from the dummy sink node and ends at the dummy source node. This arc represents the aircraft at the airport overnight. Equations (2.3) and (2.4) can be rewritten as Eq. (2.7) with additional notation as follows.

2.1.2 FAM based on the time–space network

The time–space network was first proposed by Hane et al. (1995) (Fig. 3). Three types of arcs are constructed, namely, leg arcs, ground arcs, and wrap-around arcs. Leg arcs represent flights between airports. Ground arcs represent aircraft staying on the ground. Wrap-around arcs link the last events of an airport to the first events of the same airport, which represent aircraft overnight at that airport. The nodes in the time–space network represent leg departure and arrival events. The time of arrival node is equal to the actual arrival time of the leg plus the minimum turn time for an aircraft. The minimum turn time is the shortest time for an aircraft to make a connection.

Given the time–space network above, the FAM can be formulated by Eqs. (2.8)–(2.13) with the following additional notation.

Model 2.2 Basic FAM based on the time–space network

The total profit in this model is maximized in (2.8). Constraints (2.9) reflect the cover constraints. The flow balance constraints (2.10) guarantee the balance of aircraft flow at each node. Constraints (2.11) are aircraft count constraints. On the left, {{\displaystyle \sum }}_{l\in L^{\mathrm{P}}}{x}_{lk} counts the number of aircraft in the air and {{\displaystyle \sum }}_{n\in N_k^{\mathrm{P}}}{y}_{n^{+}} counts the number of aircraft on the ground at the counting time point. Thus, the total number of used aircraft does not exceed the size of fleet k.

Table 1 reveals that the essential difference between the connection and time–space networks lies within a trade-off between the model size and the information obtained from the model. Given that the number of possible leg connections is larger than the number of legs, the model size of the connection network will grow faster than that of the time–space network as the number of legs increase. However, the solution to the FAM based on the time–space network fails to provide detailed information about the leg connections.

The majority of the constraints from the connection and time–space networks are flow balance constraints, which are considered as easy constraints and can be handled easily by commercial solvers. The connection- and time–space-based models can presently solve the largest real-life daily problem efficiently.

2.2 Enhanced models with additional considerations

In the airline industry, numerous real-life considerations can be captured by modifying the basic FAM. We discuss several important extensions to the basic FAM in the following sections.

2.2.1 Weekly fleet assignment model

Daily schedule is a widely adopted assumption in the airline literature (Rexing et al., 2000; Lohatepanont and Barnhart, 2004; Gao et al., 2009; Salazar-González, 2014; Shao et al., 2017). However, flight schedules may vary over the days in practice, for example, several legs are flown every other day. Furthermore, the demand and price at different days of a week might considerably fluctuate. Hence, weekly FAP should be considered.

Ioachim et al. (1999) focused on the schedule synchronization constraint, which requires the legs sharing the same flight number to depart simultaneously on different days of a week. A synchronized schedule produces highly reliable aircraft schedules that generate savings and requires low modification in operation. They propose a solution approach based on Dantzig–Wolfe decomposition. Their computational experiments on Lufthansa Airlines showed that the test case with 106 legs could be solved in 79.1 s. Apart from the time synchronization, fleet homogeneity is another concern of airlines and passengers. Fleet homogeneity requires the same fleet to fly the legs with the same flight number on different days in a week. Homogeneity makes the planning of ground service convenient and improves customer satisfaction. Bélanger et al. (2006b) incorporated fleet homogeneity into the weekly FAM. Their model aims to maximize the total profit and promote homogeneity by penalizing the fleet difference in the weekly FAM. A heuristic approach is developed for their problem. Their findings reveal that high level of homogeneity can be achieved at the expense of a little profitability.

2.2.2 FAM with consideration of itinerary-based demand

In the aforementioned FAMs, profit p _lk is estimated based on the forecasted leg demand and price. While some passenger itineraries consist of multiple legs, especially in the hub-and-spoke networks. An itinerary is a sequence of one or more legs linking the origin and destination of passengers. The demand for multiple-leg itineraries arises because the airlines fail to operate corresponding nonstop flights or provide multiple-stop flight (i.e., connecting flight) tickets with low prices. The fare of a connecting flight is typically less than the sum of all involved legs. Hence, the cost and demand of multiple-leg itineraries cannot be modeled by the leg-based model.

To capture the effects of flight leg interdependencies (i.e., network effect), Farkas (1996) incorporated itinerary-based demand in the time–space FAM (Eqs. (2.9)–(2.16)).

Model 2.3 FAM with consideration of itinerary-based demand

In this model, the total profit is maximized in (2.14). Aircraft capacity constraints (2.15) link the basic FAM and the itinerary-based demand. Given a leg, aircraft capacity constraints (2.15) require that the total accepted demand on itineraries containing the leg must not exceed the aircraft capacity of the fleet assigned to that leg. Demand constraints (2.16) ensure that the accepted demand is not larger than the existing demand. In Farkas (1996), two approaches are presented to solve the model, i.e., a column generation approach and a heuristic approach that partitions the fight legs into sub-networks.

Furthermore, if an aircraft is fully booked, the spilled demand of an itinerary could transfer to other itineraries that consist of different legs. These recapture effects of spilled demand cannot be formulated by the traditional leg-based model. Therefore, Barnhart et al. (2002) proposed an itinerary-based FAM (IFAM) to address this problem. The IFAM can be formulated as Eqs. (2.9)–(2.13) and (2.17)–(2.20) with additional notation below.

Model 2.4 IFAM

Equation (2.17) computes the summation of operational cost and the loss of profit. {{\displaystyle \sum }}_{i\in I}{{\displaystyle \sum }}_{j\in I}(p_i-b_{ij}{p}_j)z_{ij} can be rewritten as ({{\displaystyle \sum }}_{i\in I}{{\displaystyle \sum }}_{j\in I}{p}_i{z}_{ij}-{{\displaystyle \sum }}_{i\in I}{{\displaystyle \sum }}_{j\in I}{p}_j{b}_{ij}{z}_{ij}), if i≠ j. The first part {{\displaystyle \sum }}_{i\in I}{{\displaystyle \sum }}_{j\in I}{p}_i{z}_{ij} computes the maximum profit that can be achieved. The second part {{\displaystyle \sum }}_{i\in I}{{\displaystyle \sum }}_{j\in I}{p}_j{b}_{ij}{z}_{ij} computes the actual profit captured. Therefore, the term {{\displaystyle \sum }}_{i\in I}{{\displaystyle \sum }}_{j\in I}(p_i-b_{ij}{p}_j)z_{ij} computes the loss–profit cost. Constraints (2.18) indicate the aircraft capacity constraints. Given leg l, {{\displaystyle \sum }}_{i\in I_l}{{\displaystyle \sum }}_{j\in I}{z}_{ij} represents the passengers spilled from itineraries containing l and {{\displaystyle \sum }}_{j\in I}{{\displaystyle \sum }}_{i\in I_l}{b}_{ji}{z}_{ji} represents the passengers recaptured by itineraries containing l. Hence, constraints (2.18) require that the capacity assigned to any leg must not be less than the total number of passengers accepted by the leg. Demand constraints (2.19) ensure the total number of spilled and non-spilled passengers is equal to or less than the existing demand for the itinerary. Barnhart et al. (2002) developed a heuristic approach based on column and row generation to solve IFAM. Computational results showed that the IFAM could realize an annual revenue improvement of up to $153.2 million for a major US airline.

The IFAM adopts a fixed passenger transfer rate that can hardly be measured in real life because the transfer rate is affected by the set of available itinerary candidates. If itinerary candidates are less than expected, then the transfer rate will be high. By contrast, if itinerary candidates are more than expected, then the transfer rate will be low. To address this issue, Lohatepanont and Barnhart (2004) considered the effect of flight frequencies and departure times on spilled passenger transfer preferences. They solved their model through a similar heuristic approach for the IFAM and reported that an increase in the daily contribution of $561776 is achieved by such model compared with the planners’ schedules.

Barnhart et al. (2009) handled more comprehensive and realistic revenue functions compared with the IFAM to capture the spill and transfer demand in FAM. They solved the problem by decomposing the entire network into small sub-networks, in which the revenue of each sub-network can be accurately computed and can reflect the original revenue function. Their model provided tighter linear programming relaxations than the IFAM and outperformed the FAM and the IFAM in terms of profit and solution time.

2.2.3 Robust fleet assignment model

Numerous researchers focus on profit maximization and/or cost minimization in FAM, but the robustness in the schedule should also be considered. Flights may fail to consistently depart or arrive as planned when unpredicted disruptions happen (e.g., adverse weather, air traffic control, and resource shortage). Robust scheduling is one of the major schemes to mitigate the large financial effect caused by disruptions. Rosenberger et al. (2004) proposed a robust FAM with short cycles (i.e., a sequence of legs with the same departure and arrival airport), because the schedule with short cycles can provide more cancelation opportunities. Smith and Johnson (2006) addressed another measurement, namely, station purity, to promote schedule robustness. Station purity represents the number of fleet types serving a given airport. By limiting the number of fleets on each airport, additional opportunities are open for aircraft and/or crews to swap, thereby improving schedule robustness.

Table 2 summarizes the FAP reviewed above and indicates additional studies that are not mentioned in the text.

3 Aircraft routing problem

When the schedule design and fleet assignment are determined, the flight network is decomposed into sub-networks to each fleet. Given the sub-network of a fleet, ARP aims to construct the specific route (also called rotation) flown by each aircraft (Clarke et al., 1997). A valid route should satisfy aircraft maintenance requirements based on typical metrics, e.g., accumulated flight hours (FH), number of takeoffs/landings (cycles), and elapsed time since last check (Barnhart and Smith, 2012). Therefore, ARP is also called aircraft maintenance routing problem (AMRP).

3.1 Common maintenance checks

To remain airworthy, aircraft should undergo various regularly scheduled maintenance tasks. The tasks are grouped into work packages named blocks to minimize the time that aircraft out of service and maximize the utilization of maintenance resources. Daily check is the lowest scheduled check and merely inspects general items, such as fluid levels, emergency equipment, and deck cleaning, among others. Type A check is the next higher level maintenance, which is performed at approximately every 400–600 FH. A typical A check on B737 needs about 6–24 h, and the daily check could be included. Type B check is performed every 6–8 months or 400–900 FH, and needs about 120–150 staff hours. Type C check has a thorough visual inspection of specified components and systems, which occurs at approximately every two years and keeps the aircraft unavailable for a week. For several fleets, the B check could be distributed between the A and C checks, so to reduce aircraft downtime and improve manpower usage. Type D check dismantles the aircraft, checks all the components, and reinstalls back the parts. The D check requires three weeks or more time to finish. A and B checks are considered as light checks, which do not involve detailed disassembly. C and D checks are known as heavy checks, which are carried out in hangars at maintenance airports. The higher-level check can cover the checks with lower levels. Table 3 summarizes additional details (Hessburg, 2000; AEINFO, 2016; Qantas, 2016; Aviation Enthusiasts, 2019a; 2019b). All aforementioned data are estimated value, while the exact numbers in practice vary according to fleet, age, cycle count, accumulated FH, and elapsed hours since the last check of the aircraft. Furthermore, some components like the engines undergo maintenance according to their log files.

Nowadays, the flight schedule becomes much tighter. To decrease the time of aircraft on the ground and increase the feasibility of maintenance schedule, a variation of block maintenance or the phased-A check is proposed (Seidenman and Spanovich, 2018). The proposed check breaks a typical A check into small packages. The Director for Maintenance Planning and Technical Operations of JetBlue Airways, Boris Rogoff, stated that the phased-A check achieves better operational flexibility. On the other hand, Jonathan Berger, the Managing Director of Alton Aviation Consultancy, reported that it looks good on paper but has poor on-time performance, because the phased-A check is done more frequently, and components or labor are not constantly available. Therefore, choosing between traditional and phased-A check is a trade-off between flexibility and reliability.

The light checks, particularly Type A check with daily check embedded, are performed more frequently than other check types. Thus, the A check is typically incorporated into the ARP in various studies. In literature (Feo and Bard, 1989; Gopalan and Talluri, 1998; Haouari et al., 2013), the A check is referred as a daily check, which occurs at every 65 FH (not 400 FH in Table 3) and must be done at night by default. Few studies considered Type B (Clarke et al., 1996; 1997; Sriram and Haghani, 2003). For Type C or D check, the interval between consecutive adjacent checks is long, so the heavy checks are not typically considered in the ARP. However, they can be modeled via a reduction in the available aircraft number.

Modeling the maintenance requirement in ARP can be done in two typical methods. Numerous works assumed that maintenance should be performed within a fixed duration based on calendar days (Feo and Bard, 1989; Clarke et al., 1996; Liang et al., 2011; Maher et al., 2018). Another method imposes limitations on the accumulated FH (or cycles) (Sarac et al., 2006; Keysan et al., 2010; Başdere and Bilge, 2014). The two methods above show different advantages and difficulties in modeling, which are discussed below.

3.2 Three optimization models for the ARP

In this section, we discuss three typical aircraft routing models (ARMs), i.e., string-based model, connection-based model, and the time–space-based model.

3.2.1 String-based ARM

The string-based ARM was introduced by Barnhart et al. (1998). A string is a sequence of connected legs that begins and ends at maintenance airports. A string is extended with additional time for maintenance at the end of the last flight to guarantee aircraft maintenance requirements. The string-based ARM is presented in Eqs. (3.1)–(3.7) with additional notation below.

Model 3.1 String-based ARM

The total cost is minimized in the objective function (3.1). Constraints (3.2) are cover constraints. Constraints (3.3) and (3.4) enforce the aircraft flow balance at the first and the last legs of strings, respectively. Consequently, in a given airport, the number of aircraft arriving at the airport equals the number of aircraft departing from the airport. Aircraft count constraints (3.5) assure that the number of aircraft in the air and on the ground at any time point does not exceed the total number of available aircraft. As the number of possible strings grows exponentially with the number of flights, all the flight strings cannot be explicitly enumerated in the model. To overcome this difficulty, a column generation algorithm is proposed to solve the linear programming (LP) relaxation of the model, and a branch-and-price algorithm is proposed to solve the integer programming problem.

Notice that Barnhart et al. (1998) does not distinguish individual aircraft of the same fleet. In practice, airline routes have specific equipment requirements. For example, intercontinental long-haul routes often involve the extended overwater operations, and emergency equipment like liferafts must be installed (which are not mandatory for all aircraft) (Federal Aviation Administration, 2019). For plateau routes, there are some enhanced requirements for oxygen supply and engine performance. The aforementioned requirements can be achieved by adding aircraft index a to each string variable and modifying the objective function and constraints correspondingly.

In the string-based ARM, maintenance feasibility is checked during string generation. That is, maintenance-related considerations are implied in the string variables. Therefore, complex regulations and operational rules of strings can be easily incorporated into the string-based ARM.

3.2.2 ARM based on the connection network

Different from the string-based ARM, the connection-based ARM formulates the maintenance requirements (e.g., accumulated FH, cycles, and elapsed hours) via additional variables and constraints. Haouari et al. (2013) introduced additional decision variables to keep track of the maintenance indicators. Taking the accumulated flight hours as an example, the connection-based ARM can be formulated as Eqs. (3.8)–(3.15) with additional notation below.

Model 3.2 ARM based on the connection network

The presented model aims to find a feasible solution to the ARP with no objective value, however, it can be easily extended by modifying the objective function. Constraints (3.9)–(3.11) are cover, flow balance, and aircraft count constraints, respectively. This model uses u _j to compute accumulated FH. Constraints (3.12) reset u _j if the connection time between leg i and j is sufficiently lengthy to perform maintenance, and constraints (3.13) update u _j if the leg connection i→ j is insufficiently lengthy for a maintenance. The other two maintenance requirements, i.e., number of cycles and elapsed hours, can be formulated in a similar manner. This model cannot be solved directly by the commercial solver because of quadratic terms in constraints (3.12) and (3.13). To overcome this difficulty, Haouari et al. (2013) proposed a reformulation and linearization technique (RLT).

Based on the connection network, Başdere and Bilge (2014) solved an operational ARP, in which the maintenance deadline for each aircraft is given. An aircraft must undergo one particular maintenance before its maintenance deadline, and the objective function aims to maximize aircraft utilization by minimizing the total unused flying time before maintenances for all aircraft. Başdere and Bilge (2014) tackled this problem by duplicating leg connection arcs to represent different maintenance states, i.e., before maintenance, undergo maintenance, or after maintenance. The model is solved by branch-and-bound and a heuristic method based on compressed annealing. Safaei and Jardine (2018) extended the connection-based model to ensure that sufficient maintenance opportunities are provided within any time interval in the planning horizon for each aircraft. This procedure was performed by discretizing the entire planning horizon into a set time grid (days) and posing additional constraints to count the total maintenance opportunities for an aircraft within any possible discretized period.

3.2.3 ARM based on the time–space network

In many airline companies, daily maintenance is performed during the night after an aircraft completes all the flights, which maximizes aircraft utilization rate at daytime. Therefore, the maintenance requirement can be simplified to the maximum number of consecutive flying days without maintenance. To solve this kind of maintenance requirement, Liang et al. (2011) proposed a compact network representation of the ARP, namely, rotation tour network (Fig. 4). The two steps are followed for constructing the network. The first step is to duplicate the daily time–space network for D days, and D is the maximum number of days allowed between two consecutive maintenances (e.g., D = 3 in Fig. 4). The second step is to construct the maintenance arcs, which start at the end of each day at a maintenance airport and end at the beginning of the first day of the same airport. A maintenance arc that starts at the end of the day d represents the aircraft undergoing maintenance after d-days flying, where d = {1, 2,…, D}. Traditional overnight arcs at non-maintenance airports are omitted. Hence, the maintenance feasibility is guaranteed automatically in the rotation tour network (see Fig. 4(b)).

The mathematical formulation is given in Eqs. (3.8) and (3.16)–(3.22) with additional notation below.

Model 3.3 ARM based on the time–space network

The objective function (3.8) is 0, and the model is formulated as a feasibility problem. Cover constraints (3.16) ensure that each leg is covered once. Flow balance constraints (3.17) require that the number of inbound aircraft equals the number of outbound aircraft at each node in the network. Aircraft count constraints (3.18) assure the number of aircraft used equals or is below the total number of available aircraft. In particular, if a maintenance arc variable z _sd = 1, then a string lasting for d days is implied. Consequently, d aircraft should fly the string. Consider the example in Fig. 4, the string leg1→leg3→leg6→leg5'→leg2"→leg4"→z _A3 uses the maintenance arc at the end of day 3 at airport A. Hence, three aircraft are needed to cover these six legs every day. The number of variables and constraints increases linearly with the number of flights and the maximum maintenance day D. Airport capacity constraints (3.19) ensure that the number of aircraft being maintained at each airport is not greater than the airport’s capacity. This model can be solved directly by the commercial solver, and the computational results showed that the largest case with 352 flights can be solved within 15 s.

Table 4 shows the time–space-based ARM has less space complexity than the other two models and possesses good linear relaxation solution (Liang et al., 2011). One of the disadvantages is that the time–space network fails to provide the leg connection information. Hence, indicators, such as FH, cycle numbers, and elapsed hours, can hardly be formulated in this network. To consider these cumulative maintenance requirements in the time–space-based ARM, Khaled et al. (2018) used additional variables and big-M constraints to monitor the aircraft accumulated flight time and flying days without maintenance.

3.2.4 Comparison among three models

Table 4 presents the key differences among the three models. Given a fleet network, the basic ARP is typically modeled as a feasibility problem. Rows 2 and 3 reveal the number of decision variables and constraints corresponding to the three formulations, respectively. Table 5 indicates the computational capacities of different models.

Tables 4 and 5 show that different models have various computational capabilities and resolutions on solution details. In particular, the string-based model provides the most flexible solution approach to cater to various maintenance and routing considerations, whereas the time–space network-based model can directly solve the largest test instances in a timely manner. Hence, researchers and participants should select the suitable model to satisfy different research and business requirements. Given that the ARP aims to find the main feasible solution, the robustness of the result schedule becomes more important than that in FAP. A review on the robust ARP is presented below.

3.3 Robust ARM

As flight network becomes more complex, various disruptions, such as weather, air traffic control, and mechanical problems could have hazardous effects on airlines. In this section, literature that focused on robust aircraft routing problem (ARP) can be divided into two categories: Propagated delay (PD) minimization and domain-specific optimization.

3.3.1 Propagated delay minimization

Delay is a critical indicator to evaluate schedule performance. Thus, many studies focused on robust schedule via delay or PD minimization. Generally, the delays can be specified into two parts, namely, the primary delay (also called non-propagated or independent delay) and PD. Table 6 provides some of the relevant concepts of delay, where leg i and leg j are flown by the same aircraft successively, and minTm refers to the minimum turn time between the sequential legs. Table 7 shows examples of these concepts, which are further illustrated in Fig. 5.

Most researchers choose string-based network as convenient to model PD because delay propagates along the routes (Lan et al., 2006; Dunbar et al., 2012; 2014; Froyland et al., 2014; Liang et al., 2015; Yan and Kung, 2018).

Lan et al. (2006) modify the string-based ARM to minimize total PD. They fit flight delays as independent log-normal distributions using historical data. They also consider flight retiming to reallocate the buffer time between connected legs, thereby improving schedule robustness. A column generation algorithm is used to solve the linear relaxation of the model, and a heuristic branch-and-price algorithm is used to solve the integer programming problem. The test case with 278 flight legs and 4 fleets can be solved in 13 s.

Liang et al. (2015) present an accurate computation of the expected propagated delay (EPD) of a string. Because computing the EPD of a string could be time-consuming, they prove a tight lower bound for estimating the EPD and propose a two-stage column generation method that makes use of the lower bound to speed up the solution process. Large test cases with more than 6000 flights per week can be solved within 3 h.

Instead of minimizing EPD, Yan and Kung (2018) sought to minimize the maximal possible PD. When flight leg delays lie in a pre-specified uncertainty set, using a robust optimization approach, they propose an exact decomposition solution approach under a column-and-row generation framework. Their approach is reported to outperform the local approach provided in Dunbar et al. (2014) by reducing both mean and extreme total PD.

3.3.2 Domain-specific optimization

Studies on domain-specific optimization identify specific features of flight networks and improve robustness by strengthening or attenuating these features. Ageeva (2000) improves schedule robustness by creating more swap opportunities between aircraft routes. A heuristic approach is proposed to solve the problem. Burke et al. (2010) consider the schedule reliability and aircraft swap opportunities in ARP. They define reliability in terms of the probability that succeeding flights are not delayed because of previous flight delays and propose a multi-objective approach based on hybrid genetic algorithms for robust scheduling. Their simulation study shows that at least 20% improvement in both objectives could be realized. Liang et al. (2018) incorporate the flexibility of aircraft maintenance into their recovery model. Computational experiments have shown that swapping planned maintenances may bring a considerable reduction in recovery cost (about 20% to 60%). Hence, swap opportunities for planned maintenances might be considered in the planning stage to improve the robustness of ARP.

3.4 Industrial considerations

Apart from maintenance regulations, some studies incorporate industrial considerations into ARP. For example, the Euler-tour requirement (also called big-cycle constraints) is often applied to ARP to balance wear and tear among different aircrafts. A directed graph is called Eulerian if each node has in-degree equal to out-degree and is connected. An Euler tour of an Eulerian digraph is a cycle that includes all the arcs (i.e., leg arcs and ground arcs in the flight network) exactly once. For airlines, the Euler-tour requirement requires all aircrafts of the same fleet to fly the same sequence of all legs assigned to the fleet so that depreciation does not fluctuate among aircraft (Clarke et al., 1997; Talluri, 1998; Gopalan and Talluri, 1998). Another consideration is the maintenance capacity of airports. Aircraft maintenance requires necessary aircraft components and manpower and thus, the capacity of aircraft to receive service at a maintenance airport is not infinite. Therefore, many researchers consider airport capacity constraints in the ARP to make a more practical aircraft schedule (Liang et al., 2011; 2015; Liang and Chaovalitwongse, 2013; Khaled et al., 2018).

3.5 Solution methods

As discussed above, many studies on ARP are based on the string-based network. However, because of the large number of possible connections, enumerating all feasible strings is impractical. The column generation framework has been proven efficient and effective for such problems with a huge number of strings (Barnhart et al., 1998; Sarac et al., 2006; Lan et al., 2006; Dunbar et al., 2012; 2014; Froyland et al., 2014; Liang et al., 2015; Yan and Kung, 2018). Other methods, such as branch-and-bound (B&B), Lagrangian relaxation (LR), Benders decomposition (BD), etc. are also proposed to solve different models. Details are shown in Table 8.

4 Crew scheduling problem

After aircraft routing is performed, crew scheduling problem (CSP) will allocate crew to flights and is always divided into two sub-problems: Crew pairing problem (CPP) and crew rostering problem (CRP) (Arabeyre et al., 1969; Barnhart et al., 2003b). Similar to an aircraft route, a pairing consists of a sequence of legs spanning 1–5 days that begin and end at the same crewbase (Gopalakrishnan and Johnson, 2005; Belobaba et al., 2009). The crewbase is usually the domicile of the crew and is located in the same city where the airline has a hub. A crew member usually needs to complete a pairing before he or she can rest with one or more days. CPP selects a set of pairings with minimal crew cost, such that each leg is covered by at least one pairing. Then, CRP generates the monthly schedule (called a roster) for each crew member with respect to all crew regulations (Belobaba et al., 2009). A roster typically includes training, vacations, and pairings assigned to the crew member. The objective of CRP could vary from one airline to another. For example, in the US, the preference bidding process is commonly used and is usually driven by seniority (i.e., the preferences of more senior crew are prioritized) (Barnhart and Smith, 2012). In other countries like China, the fairness of workload and salary among the crew play an important role in CRP. In short, CPP focuses on total cost, whereas CRP focuses on people-related factors such as fairness, fatigue, and satisfaction.

4.1 Cost and regulations of crew

Given a solution to ARP, CSP will minimize the total crew cost, such that the regulations mandated by the governing agencies and other organizations like labor unions are satisfied. Rather than a fixed salary, the payment structure of the crew involves many factors, including flying hours, seniority of the crew, and additional allowance. As a primary method for fatigue risk management, various regulations have detailed limitations on the working time of crew. Figure 6 may help to understand the crew cost and formulation of regulations. We adopt the description of crew cost by Barnhart et al. (2003b) because the specific situation varies slightly among different countries and airlines. A pairing is composed of several duties and the duty is composed of several legs flown within a day. The duty cost is a maximum of three terms, that is, the accumulated flying hours, a fraction of the elapsed time, and a minimum guaranteed time (see Eq. (a) in Fig. 6). The cost of a pairing consists of two parts (see Eq. (b) in Fig. 6): (1) the maximum of the total duty cost, a fraction of the total elapsed time, and a minimum guaranteed cost, and (2) extra cost, such as lodging.

Crew regulations focus on (1) the flight duty period (the duty time), which begins at the time to report for duty and ends when the aircraft is parked after the last landing, (2) the flight time, which refers to the time between an aircraft moving from its parking place and resting on the designated parking position, and (3) the rest period. Some details are shown in Table 9.

As mentioned above, the crew cost is highly nonlinear. Because different regulations set limits on different indicators (see Table 9), any of these indicators could constrain the crew scheduling results. Usually, no indicator could dominate others. Hence, missing any of the indicators might lead to an infeasible solution. Therefore, catering to the complex cost and all regulations in CSP is a challenging issue.

4.2 Crew pairing problem

CPP is usually formulated as a set partitioning problem (SPP). Barnhart et al. (2003b) present a general formulation of CPP as shown in Eqs. (4.1)–(4.3). This model takes pairings as decision variables and captures implicitly the regulations and nonlinear cost in the definitions of variables and parameters.

Model 4.1 Basic crew pairing model (CPM)

In CPM, the total cost is minimized in the objective function (4.1). The cover constraints (4.2) ensure that each leg is covered by at least one pairing. The problem is a typical integer programming problem with a large number of variables, which can be solved efficiently by the branch-and-price approach.

In the basic CPM, any pairing from any crewbase could be selected in the solution. However, some crewbases might be assigned more pairings than the available crew capacity, whereas other crewbases might have fewer pairings for the available crew. Therefore, Hoffman and Padberg (1993) and Saddoune et al. (2012; 2013) introduce the base constraints (also called crewbase balancing constraints) to match the workload to the crew resource at a crewbase. The base constraints limit the total number of flying hours assigned to the crew of a base (see Eq. (4.4)).

Some studies adopt other formulations to model CPP rather than the general model. Vance et al. (1997) propose a duty-based formulation and divide the decision process into two stages: Cover legs by duties and cover duties by pairings. They propose a column-generation-based framework to solve the model. The largest test case with 174 flights takes about 10 h to solve. Barnhart and Shenoi (1998) develop a time–space network of duties and propose an approximate model for CPP. Their computational experiments show the solution of the approximate model can be used to speed up the solution process of the traditional model by 84%. Based on the connection network, Haouari et al. (2019) introduce decision variables that represent crew connection, that is, flying two consecutive legs by the same crew. Additional constraints are used to describe feasibility regulations of duties and pairings explicitly. They present a novel compact polynomial-sized nonlinear formulation for CPP, which is then linearized and lifted using the reformulation linearization technique. A real-life instance having 336 daily flights can be solved in two hours.

4.3 Crew rostering problem

CPP focuses on crew cost minimization because the crew cost depends mainly on the pairing structure, whereas CRP emphasizes solution feasibility by satisfying safety regulations and individual requirements of crew members. CRP can also be divided into two stages: The first stage makes the pre-assignment of each individual crew member and the second stage assigns pairings and rest periods to individual crew members without conflicting with pre-assignments. The pre-assignments usually include annual leaves, medical appointments, training, reserve blocks to be a substitute crew member when necessary, and other preassigned activities (Gamache et al., 1999). Barnhart et al. (2003b) present a basic CRM, shown in Eqs. (4.5)–(4.8).

Model 4.2 Basic CRM

The cover constraints (4.6) require a minimum number of crew members assigned to each pairing. The crew count constraints (4.7) ensure each crew member is assigned exactly one roster.

CRP focuses more on practical considerations. A more detailed description of typical rules and regulations can be found in Kohl and Karisch (2004). Some rules and preferences are formulated through variables and constraints, and others can be optimized in the objective function (see Table 10). For example, the target of CRP is to find a feasible solution and thus, the objective is to minimize the number or duration of uncovered activities (Gamache et al., 1999; Cappanera and Gallo, 2004). Some studies make a trade-off between infeasibility cost and operating cost (Saddoune et al., 2012; Zeighami and Soumis, 2019). Souai and Teghem (2009), Maenhout and Vanhoucke (2010), and Doi et al. (2018) penalize the deviation of the assigned workload to promote fairness among all crew members.

4.4 Extension of the crew scheduling problem

Many additional considerations are incorporated into CPP and CRP. Because CPP overlooks individual crew information, its solution may not be optimal for CRP. Therefore, considering the requirements and constraints of CRP in CPP is beneficial.

Guo et al. (2006) incorporate preassigned activities, such as training and requested off-duty days and crew availability, into CPP, making it easy to solve CRP through the heuristic approach, and a reduction of total crew cost is achieved. Obviously, solving CPP and CRP using an integrated model is a direct method to improve optimality, but it is impractical and intractable for real-life problems. Consequently, Souai and Teghem (2009) solve the integrated CSP using a genetic algorithm. Saddoune et al. (2012) speed up the solution process through a combination of column generation and a heuristic named dynamic constraint aggregation (DCA). DCA helps reduce the number of constraints in the master problem of column generation.

Deadhead means repositioning the crew as a passenger or non-operating crew member by any mode such as bus, train, and airplane. In the scheduling stage, it provides more feasible crew connections to construct pairings. As described in Barnhart et al. (1995), deadhead plays an essential role in long-haul operations, especially at the airport with few scheduled flights or flights not scheduled daily. A considerable number of legs could be deadhead candidates and thus, the CPP is solved iteratively and non-potential deadhead flights are eliminated in each iteration. To summarize, deadheads help to achieve better crew utilization via more flexibility.

Crew can be categorized into different ranks such as captain, first officer, and flight engineer, based on quality and experience. Different flights have specific demands of crew members, that is, how many captains and first officers are needed. Downgrading (also called fly below rank) allows a captain to fly as the first officer, whereas the converse is rarely allowed. It could be formulated via modification of coverage constraints as Eqs. (4.9)–(4.10).

Constraints (4.9) ensure that the number of captains meets the requirements and constraints (4.10) ensure that the total number of captains and first officers is greater than or equal to the demand of crew members and thus, a captain can be used as the first officer. The idea of downgrading also provides more flexibility to CSP, and it is considered in the enhanced rostering model proposed by Dawid et al. (2001).

In practice, not all flights are scheduled daily. On the contrary, some are operated only on weekends or several weekdays. Therefore, the solution pairings may not be able to fly repeatedly, which is unlikely to be friendly to the crew. Therefore, Klabjan et al. (2001) present a crew pairing model to make a trade-off between crew cost and regularity.

More swap opportunities are believed to benefit the crew recovery in operations. A move-up crew, introduced by Shebalov and Klabjan (2006), is a crew that is ready to fly the flight of a disrupted crew. Given a flight l, they define the rules to count the move-up crew (see Fig. 7, crew 2 is a move-up crew of leg 5), such as the crew members (1) are ready to fly before the departure time of l, (2) end their pairings at the same day of the pairing covering l, and (3) share the same crewbase of the crew covering l.

As shown in Eqs. (4.11)–(4.12), the additional variable z _lst is introduced to count the move-up crews, and the objective function is modified to minimize the total pairing cost and encourage more move-up crews.

Gao et al. (2009) extend the station purity idea of Smith and Johnson (2006) and set a limitation on the number of crewbases serving each airport, called crewbase purity. It provides more opportunities to find a move-up crew in the stage of recovery.

Similar to robust aircraft routing (see Section 3.3.1), the robustness of crew scheduling could also be realized by minimizing delay or delay cost. Yen and Birge (2006) propose a two-stage stochastic programming model that minimizes expected total cost in the first stage and the delay cost because of the crew changing aircraft in the second stage. Wei and Vaze (2018) study a robust crew pairing problem by considering not only the crew cost but also the other operational features such as the scheduled sit time when the crew changes aircraft, the scheduled rest time between duties, the flying time in a duty, the elapsed time in a duty, the number of crewbase purity violations, and the number of aircraft changes by the crew within a duty. To solve the problem, a column generation method is embedded in a variable diving heuristic. To capture the full complexity of the crew salary structure (see Section 4.1) and the effects of increases in duty/pairing elapsed times, Antunes et al. (2019) formulate a robust pairing model using robust optimization. They use column generation to solve the model and modify the approach developed by AhmadBeygi et al. (2009) to generate columns in the pricing problem.

4.5 Solution method: Column generation algorithm

As discussed above, both CPP and CRP are usually formulated as an SPP. However, it is often impractical to enumerate all the pairings and rosters for real-life problems. Therefore, the column generation is usually used to handle the difficulty. It is an implicit enumeration technique that guarantees the optimal solution to the LP relaxation. To obtain the optimal integer programming (IP) solution, the branch-and-price algorithm, which embeds column generation in the branch-and-bound procedure, is usually employed. Typically, the pricing problem of the column generation can be solved by multi-label shortest path algorithms (Irnich and Desaulniers, 2005).

For shorter computing time and less memory, traversing all branches is necessary. Two widely used strategies of branching are branch-on-variable and branch-on-follow-on. For CPP, the branch-on-variable strategy fixes a pairing each time, which means a pairing is selected or deleted into the final solution (Saddoune et al., 2012; Wei and Vaze, 2018). The branch-on-follow-on strategy requires a pair of legs or duties to be fixed each time, which means for any pairing, covering only one of them is forbidden (Ruther et al., 2017). The general solution process discussed above is illustrated in Fig. 8.

5 Integrated problems

As introduced in Section 1, the scheduling process is usually divided into sub-problems and solved sequentially, and the result of the previous sub-problem is the input of the succeeding sub-problem. Consequently, sub-optimal solutions are obtained in most circumstances. However, in some cases, given output to the previous sub-problem, a feasible solution does not exist to the next sub-problem. Thus, we have to track back and re-solve previous problems with additional constraints until a global feasible schedule is found. Many enhanced models are proposed to consider additional constraints from the succeeding sub-problems to ensure feasibility. Integrated models are also proposed to solve multiple sub-problems simultaneously to improve solution quality.

5.1 Integrated fleet assignment and aircraft routing problem

Four common aircraft maintenance checks are introduced in Section 3.1. Keeping maintenance feasibility is one of the main purposes of ARP. However, the solution to FAP is not always maintenance feasible for the following ARP. A roll-back is inevitable if we cannot find a feasible solution to ARP. Therefore, a general motivation of integrated fleet assignment and aircraft routing models is to guarantee the feasibility of aircraft maintenance.

Barnhart et al. (1998) propose a string-based integrated model of FAP and ARP to ensure maintenance feasibility and capture the through-revenues associated with aircraft connections. The minimum time to perform maintenance is included at the end of the string to ensure maintenance feasibility. They use column generation to solve their string-based model. Haouari et al. (2009) develop a connection-based model and propose a two-stage heuristic approach. Specifically, they build an initial solution greedily in the first phase and improve the solution by solving minimum-cost flow problems iteratively in the second phase. Haouari et al. (2011) present two formulations of the integrated FAP and ARP, one based on flight connections and the other based on aircraft routes. They solve the connection-based model by Benders’ decomposition and solve the route-based model by branch-and-bound. Their computational results show that the latter outperforms the former.

Considering flight departure time rescheduling in the integrated model helps to increase the number of possible connections and reduce the number of required aircraft. Therefore, more through-revenues are captured and aircraft operational costs are saved. Zeghal Mansour et al. (2011) use a column-generation-based heuristic approach to solve their integrated model with retiming consideration. In addition to flight retiming, Sherali et al. (2013a) take more practical considerations into account, including through-flight and demand recapture. They impose a flight-time limitation on each fleet to simplify the maintenance constraints and improve the tractability of their model. Furthermore, they use various valid inequalities to strengthen the formulation. Many researchers reschedule flight departure time according to historical data and usually adopt the deterministic formulation. Kenan et al. (2018) propose a two-stage stochastic model for the integrated fleet assignment and aircraft routing model with flight selection consideration to consider the randomness of passenger demand and flight delay. In their work, flight selection helps to improve robustness via buffer time reallocation.

5.2 Integrated fleet assignment and crew scheduling problem

In general, the fleeting solution decomposes the flight network and the CPP is solved over a subset of flights because each crew is only qualified to fly a specific fleet. This dependency is not captured in the solution of the FAP and thus, the fleet assignment result may be costly to CPP and the result of CPP may be undesirable to the crew. Several studies focus on the integrated FAP and CPP to address this issue.

Klabjan et al. (2002) and Sandhu and Klabjan (2007) integrate FAP and CPP with a plane-count constraint to ensure that the number of aircraft used by crews does not exceed the number of available aircraft. They design two approaches to solve the integrated model, one is a combination of Lagrangian relaxation and column generation, and the other is based on Benders’ decomposition. Their computation results show the algorithm based on column generation performs better on average for four test cases.

Gao et al. (2009) consider station purity and crewbase purity in an integrated model for FAP and CPP to obtain a robust schedule. Thus, more recovery opportunities are introduced into the schedule. For computational tractability, they define crew connections instead of explicit pairings as decision variables to formulate the problem.

5.3 Integrated aircraft routing and crew scheduling problem

Given an airline network, two types of resource flow exist, namely, the flow of the aircraft and the flow of the crew. The two flows cannot always keep pace with each other because of the numerous and complex regulations and optional constraints. For example, minimum connection time is required to ensure the connection of two sequential flights. The minimum connection time for the aircraft is called minimal turn time and the minimum connection time for crew is called minimal sit time. The minimal sit time of the crew (e.g., 45 min) is usually longer than the minimal turn time of the aircraft (e.g., 30 min) unless the crew stays on the same aircraft (in this condition, both are set to 30 min) because the crew needs additional time to travel from one gate to another if they change aircraft. A short connection refers to a connection that is too short for the crew to change aircraft, but long enough for necessary preparations (e.g., 35 min). In other words, a short connection requires the crew to stay on the same aircraft. Short connections are preferred because it helps to save crew duty time on the ground and prevent the flight delay from propagating to more flights. Consequently, to build a more practical integrated model, the concept of short connection has attracted the interest of many studies (Cordeau et al., 2001; Cohn and Barnhart, 2003).

Cordeau et al. (2001) integrate the set-partitioning models of ARP and CPP through the linking constraints, which ensure that a short connection can be covered by a pairing only if it is covered by an aircraft route. The short connection constraints can be formulated as Eq. (5.1). A short connection (i, j) ÎC can also be included in a pairing p if and only if (i, j) is covered by a route r.

Cordeau et al. (2001) use Benders’ decomposition to solve their model. They solve ARP through column generation in the master problem and generate cuts by solving CPP with column generation in the sub-problem.

Because it is the short connection set that links ARP and CPP, Cohn and Barnhart (2003) use a unique and maximal (UM) maintenance-feasible short connection set to represent solutions of ARP and incorporate ARP into CPP (Eq. (5.2)). Uniqueness means including one variable (i.e., x _θ) for each UM short connection set is sufficient, rather than including all feasible routing solutions because different aircraft routing solutions may cover the same short connection set. Maximal set means the set would be infeasible with any additional short connection.

Mercier et al. (2005) introduce another concept called restricted connection similar to the short connection to produce a more robust solution. A restricted connection designates a connection between two flights not flown by the same aircraft and just long enough not to be considered short. Therefore, two flights with a restricted connection can be assigned to a crew even if they are not flown by the same aircraft, and it is likely to cause delays. To improve the robustness of the crew schedule, they penalize the restricted connections in the objective function. Weide et al. (2010) present a similar model with the consideration of the restricted connection. They develop an iterative heuristic approach to make a trade-off between cost and robustness and generate a series of non-dominant solutions. Cacchiani and Salazar-González (2017; 2020) also focus on the flight connections and they penalize the number of aircraft changes in crew pairings in the objective of their integrated models.

Another important consideration for robust scheduling is delay minimization. A flight cannot get ready to take off until both its aircraft and crews are ready. Thus, the delay along with aircraft flow and crew flow in the network has a combined effect on the PD of the flight. Dunbar et al. (2012) develop an iterative approach based on column generation to consider the joint PD. In their approach, the integrated problem is solved iteratively, beginning with ARP linked to output from CPP, and then switching to CPP linked to new output from ARP.

Re-solving ARP and CPP close to the day of operations helps increase aircraft utilization, reduce crew costs, and increase schedule robustness. Ruther et al. (2017) consider such a re-optimizing problem of the aircraft routes and crew pairings. They design the aircraft routes and crew pairings based on more up-to-date information, that is, the current location, maintenance, and flying history of each individual aircraft, and current status of crew. They propose a branch-and-price-based approach and develop two strategies to solve its integrated model and accelerate the solution process.

5.4 Integrated fleet assignment, aircraft routing, and crew scheduling problem

A rich set of literature has focused on formulating FAP, ARP, and CPP within a single model. Clarke et al. (1996) present an enhanced FAM with aircraft and crew considerations. They impose a lower bound on the number of aircraft that overnights at maintenance airports and the number of flights departing from crewbases. Obviously, the feasibility of the maintenance requirements and crewbase constraints is not guaranteed fully. Papadakos (2009) integrates the aforementioned problems with short connection constraints. In addition to short connection constraints, Salazar-González (2014) also minimizes the number of aircraft changes and total connection times in the crew pairings to improve the robustness. Their problem is solved with an iterative heuristic method that generates crew pairings and aircraft routes sequentially at each iteration. With the same motivation of Salazar-González (2014), Cacchiani and Salazar-González (2017) propose two alternative formulations for the integrated problem, one uses path-based variables to describe the aircraft routes and the crew pairings, and the other adopts arc-based variables for the aircraft routes and uses path-based variables to represent the crew pairings. Their results show the arc-path method outperforms the path-path method as well as the heuristic approach developed by Salazar-González (2014). Noticing the aforementioned researches do not model the maintenance requirements explicitly, Shao et al. (2017) include the constraints that ensure the restrictions on the maximal number of takeoffs, number of days and total flying time between two sequential maintenance checks. They also consider other realistic operational considerations, such as itinerary-based demands and crew work rules to capture the interdependencies among FAP, ARP, and CPP. They use a Benders’ decomposition approach to solve the large-scale model and also design several acceleration strategies to enhance the solvability. To realize more profit and better robustness, Cacchiani and Salazar-González (2020) retime flight departure time in their integrated scheduling model to decrease the number of aircraft changes in crew pairings. They test four heuristic algorithms on the data of a regional carrier with up to 296 flights.

5.5 Other considerations

Apart from improving optimality to maximize the total profit, additional considerations are considered on some integrated problems. Pita et al. (2013) consider an integrated flight scheduling and fleet assignment problem under airport congestion. They deal with competition and cooperation among airlines and define the market shares of airlines as a piecewise linear function of flight frequency and use it to formulate passenger spill and recapture. Pita et al. (2014) present an integrated model for SDP and FAP to minimize social cost rather than airline operating cost. Specifically, the social cost is the difference between operating cost and revenues of airlines, airports, and passengers. The cost includes the flight cost and off-base cost of airlines, operating cost of airports, and traveling cost of passengers (i.e., on-board time cost, flight time cost, waiting time cost, and delay cost). The revenues are computed as non-aeronautical revenues of the airport. Based on their socially oriented schedule, a welfare analysis is developed to assist public authorities in the design of subsidized air transport networks in Norway.

6 Conclusions and future research

In this paper, we provide a thorough review on three major airline planning and scheduling problems, including FAP, ARP, and CSP, in sequence. The overarching objective shared among these problems is to determine the best airline and crew schedules effectively while minimizing overall operational costs. In this review, many state-of-the-art mathematical optimization models and solution approaches were proposed and demonstrated to successfully address various real-world challenges arising in individual scheduling problems and integrated airline/crew schedule applications.

However, solving the complete airline scheduling problems efficiently for large-scale airlines remains difficult. Hence, developing efficient solution approaches and incorporating cutting-edge algorithms and methods, such as data mining and machine learning, from related fields, is critical as the demand keeps increasing dramatically for traveling within and across countries.

Future studies should consider uncertainty in the planning and operational stage. Many factors, such as demand, flying time, mechanical failure, and absence of crew, are random in nature. A more realistic and profitable schedule can be developed by capturing this randomness in the planning stage.

Many operational constraints and considerations, for example, crew fatigue and competition from alternative transportation mode, could affect the effectiveness and profitability of the schedule. To manage crew fatigue, the ICAO Standards and Recommended Practices (SARPs) has supported a performance-based approach in addition to the prescriptive approach (ICAO, 2019). In Europe and Asia, especially in short/medium-haul markets, high-speed rails have become more attractive to passengers. Therefore, we should incorporate these factors into the planning stage.

References

[1] Abara J (1989). Applying integer linear programming to the fleet assignment problem. Interfaces, 19(4): 20–28

[2] AEINFO (2016). Aircraft maintenance checks.

[3] Ageeva Y (2000). Approaches to Incorporating Robustness into Airline Scheduling. Dissertation for the Master’s Degree. Cambridge: Massachusetts Institute of Technology

[4] AGIFORS (2019). Delivering operations research and analytics innovation.

[5] AhmadBeygi S, Cohn A, Weir M (2009). An integer programming approach to generating airline crew pairings. Computers & Operations Research, 36(4): 1284–1298

[6] AINonline (2017). Chinese airlines need 5000 pilots per year in next 20 years.

[7] Airbus (2018). Airbus 2018 price list press release.

[8] Antunes D, Vaze V, Antunes A P (2019). A robust pairing model for airline crew scheduling. Transportation Science, 53(6): 1751–1771

[9] Arabeyre J P, Fearnley J, Steiger F C, Teather W (1969). The airline crew scheduling problem: A survey. Transportation Science, 3(2): 140–163

[10] Aviation Enthusiasts (2019a). Aircraft maintenance A check.

[11] Aviation Enthusiasts (2019b). Aircraft maintenance B check.

[12] Barnhart C, Belobaba P, Odoni A R (2003a). Applications of operations research in the air transport industry. Transportation Science, 37(4): 368–391

[13] Barnhart C, Boland N L, Clarke L W, Johnson E L, Nemhauser G L, Shenoi R G (1998). Flight string models for aircraft fleeting and routing. Transportation Science, 32(3): 208–220

[14] Barnhart C, Cohn A (2004). Airline schedule planning: Accomplishments and opportunities. Manufacturing & Service Operations Management, 6(1): 3–22

[15] Barnhart C, Cohn A M, Johnson E L, Klabjan D, Nemhauser G L, Vance P H (2003b). Airline crew scheduling. In: Handbook of Transportation Science. Boston, MA: Springer, 517–560

[16] Barnhart C, Farahat A, Lohatepanont M (2009). Airline fleet assignment with enhanced revenue modeling. Operations Research, 57(1): 231–244

[17] Barnhart C, Hatay L, Johnson E L (1995). Deadhead selection for the long-haul crew pairing problem. Operations Research, 43(3): 491–499

[18] Barnhart C, Kniker T S, Lohatepanont M (2002). Itinerary-based airline fleet assignment. Transportation Science, 36(2): 199–217

[19] Barnhart C, Shenoi R G (1998). An approximate model and solution approach for the long-haul crew pairing problem. Transportation Science, 32(3): 221–231

[20] Barnhart C, Smith B (2012). Quantitative Problem Solving Methods in the Airline Industry: A Modeling Methodology Handbook. Boston, MA: Springer

[21] Başdere M, Bilge Ü (2014). Operational aircraft maintenance routing problem with remaining time consideration. European Journal of Operational Research, 235(1): 315–328

[22] Bélanger N, Desaulniers G, Soumis F, Desrosiers J (2006a). Periodic airline fleet assignment with time windows, spacing constraints, and time dependent revenues. European Journal of Operational Research, 175(3): 1754–1766

[23] Bélanger N, Desaulniers G, Soumis F, Desrosiers J, Lavigne J (2006b). Weekly airline fleet assignment with homogeneity. Transportation Research Part B: Methodological, 40(4): 306–318

[24] Belobaba P, Odoni A, Barnhart C (2009). The Global Airline Industry. West Sussex: John Wiley & Sons

[25] Berge M E, Hopperstad C A (1993). Demand driven dispatch: A method for dynamic aircraft capacity assignment, models and algorithms. Operations Research, 41(1): 153–168

[26] Boeing (2019a). Commercial market outlook 2019–2038.

[27] Boeing (2019b). Pilot & technician outlook 2019–2038.

[28] Burke E K, de Causmaecker P, de Maere G, Mulder J, Paelinck M, Vanden Berghe G (2010). A multi-objective approach for robust airline scheduling. Computers & Operations Research, 37(5): 822–832

[29] Cacchiani V, Salazar-González J J (2017). Optimal solutions to a real-world integrated airline scheduling problem. Transportation Science, 51(1): 250–268

[30] Cacchiani V, Salazar-González J J (2020). Heuristic approaches for flight retiming in an integrated airline scheduling problem of a regional carrier. Omega, 91: 102028

[31] Cadarso L, de Celis R (2017). Integrated airline planning: Robust update of scheduling and fleet balancing under demand uncertainty. Transportation Research Part C: Emerging Technologies, 81: 227–245

[32] Cappanera P, Gallo G (2004). A multicommodity flow approach to the crew rostering problem. Operations Research, 52(4): 583–596

[33] Clarke L, Hane C, Johnson E, Nemhauser G (1996). Maintenance and crew considerations in fleet assignment. Transportation Science, 30(3): 249–260

[34] Clarke L, Johnson E, Nemhauser G, Zhu Z (1997). The aircraft rotation problem. Annals of Operations Research, 69: 33–46

[35] Cohn A M, Barnhart C (2003). Improving crew scheduling by incorporating key maintenance routing decisions. Operations Research, 51(3): 387–396

[36] Cordeau J F, Stojković G, Soumis F, Desrosiers J (2001). Benders’ decomposition for simultaneous aircraft routing and crew scheduling. Transportation Science, 35(4): 375–388

[37] Daskin M S, Panayotopoulos N D (1989). An Llagrangian relaxation approach to assigning aircraft to routes in hub and spoke networks. Transportation Science, 23(2): 91–99

[38] Dawid H, König J, Strauss C (2001). An enhanced rostering model for airline crews. Computers & Operations Research, 28(7): 671–688

[39] Deveci M, Demirel N C (2015). Airline crew pairing problem: A literature review. In: 11th International Scientific Conference on Economic and Social Development—Building Resilient Society. Zagreb, Croatia: Varazdin Development and Entrepreneurship Agency (VADEA), 103–111

[40] Doi T, Nishi T, Voß S (2018). Two-level decomposition-based matheuristic for airline crew rostering problems with fair working time. European Journal of Operational Research, 267(2): 428–438

[41] Dunbar M, Froyland G, Wu C L (2012). Robust airline schedule planning: Minimizing propagated delay in an integrated routing and crewing framework. Transportation Science, 46(2): 204–216

[42] Dunbar M, Froyland G, Wu C L (2014). An integrated scenario-based approach for robust aircraft routing, crew pairing and re-timing. Computers & Operations Research, 45: 68–86

[43] Eltoukhy A E E, Chan F T S, Chung S H (2017). Airline schedule planning: A review and future directions. Industrial Management & Data Systems, 117(6): 1201–1243

[44] Farkas A (1996). The Influence of Network Effects and Yield Management on Airline Fleet Assignment Decisions. Dissertation for the Doctoral Degree. Cambridge: Massachusetts Institute of Technology

[45] Federal Aviation Administration (2019). Emergency equipment: Extended overwater operations.

[46] Feo T A, Bard J F (1989). Flight scheduling and maintenance base planning. Management Science, 35(12): 1415–1432

[47] Froyland G, Maher S J, Wu C L (2014). The recoverable robust tail assignment problem. Transportation Science, 48(3): 351–372

[48] Gall P (2018). The US is facing a serious shortage of airline pilots. The Conversation. CNN Travel

[49] Gamache M, Soumis F, Marquis G, Desrosiers J (1999). A column generation approach for large-scale aircrew rostering problems. Operations Research, 47(2): 247–263

[50] Gao C, Johnson E, Smith B (2009). Integrated airline fleet and crew robust planning. Transportation Science, 43(1): 2–16

[51] Goldman D (2019). Airlines are on pace for their worst year since 2014. CNN Business

[52] Gopalakrishnan B, Johnson E L (2005). Airline crew scheduling: State-of-the-art . Annals of Operations Research, 140(1): 305–337

[53] Gopalan R, Talluri K T (1998). The aircraft maintenance routing problem. Operations Research, 46(2): 260–271

[54] Guo Y, Mellouli T, Suhl L, Thiel M P (2006). A partially integrated airline crew scheduling approach with time-dependent crew capacities and multiple home bases. European Journal of Operational Research, 171(3): 1169–1181

[55] Hane C A, Barnhart C, Johnson E L, Marsten R E, Nemhauser G L, Sigismondi G (1995). The fleet assignment problem: Solving a large-scale integer program. Mathematical Programming, 70(1–3): 211–232

[56] Haouari M, Aissaoui N, Zeghal Mansour F (2009). Network flow-based approaches for integrated aircraft fleeting and routing. European Journal of Operational Research, 193(2): 591–599

[57] Haouari M, Shao S, Sherali H D (2013). A lifted compact formulation for the daily aircraft maintenance routing problem. Transportation Science, 47(4): 508–525

[58] Haouari M, Sherali H D, Zeghal Mansour F, Aissaoui N (2011). Exact approaches for integrated aircraft fleeting and routing at TunisAir. Computational Optimization and Applications, 49(2): 213–239

[59] Haouari M, Zeghal Mansour F, Sherali H D (2019). A new compact formulation for the daily crew pairing problem. Transportation Science, 53(3): 811–828

[60] Hessburg J (2000). What’s this ‘A’ check, ‘C’ check stuff?

[61] Hoffman K L, Padberg M (1993). Solving airline crew scheduling problems by branch-and-cut. Management Science, 39(6): 657–682

[62] IATA (2018). Economic performance of the airline industry. IATA Economics Report

[63] IATA (2019). Air passenger demand 2018—infographic.

[64] ICAO (2019). Fatigue management.

[65] ICAO (2018). Long-term traffic forecasts—passenger and cargo.

[66] INFORMS (2019). About the aviation applications section.

[67] Ioachim I, Desrosiers J, Soumis F, Bélanger N (1999). Fleet assignment and routing with schedule synchronization constraints. European Journal of Operational Research, 119(1): 75–90

[68] Irnich S, Desaulniers G (2005). Shortest path problems with resource constraints. In: Desaulniers G, Desrosiers J, Solomon M M, eds. Column Generation. Boston, MA: Springer, 33–65

[69] Jacobs T L, Smith B C, Johnson E L (2008). Incorporating network flow effects into the airline fleet assignment process. Transportation Science, 42(4): 514–529

[70] Kasirzadeh A, Saddoune M, Soumis F (2017). Airline crew scheduling: Models, algorithms, and data sets. EURO Journal on Transportation and Logistics, 6(2): 111–137

[71] Kenan N, Jebali A, Diabat A (2018). The integrated aircraft routing problem with optional flights and delay considerations. Transportation Research Part E: Logistics and Transportation Review, 118: 355–375

[72] Keysan G, Nemhauser G L, Savelsbergh M W P (2010). Tactical and operational planning of scheduled maintenance for per-seat, on-demand air transportation. Transportation Science, 44(3): 291–306

[73] Khaled O, Minoux M, Mousseau V, Michel S, Ceugniet X (2018). A compact optimization model for the tail assignment problem. European Journal of Operational Research, 264(2): 548–557

[74] Klabjan D, Johnson E L, Nemhauser G L, Gelman E, Ramaswamy S (2001). Airline crew scheduling with regularity. Transportation Science, 35(4): 359–374

[75] Klabjan D, Johnson E L, Nemhauser G L, Gelman E, Ramaswamy S (2002). Airline crew scheduling with time windows and plane-count constraints. Transportation Science, 36(3): 337–348

[76] Kohl N, Karisch S E (2004). Airline crew rostering: Problem types, modeling, and optimization. Annals of Operations Research, 127(1–4): 223–257

[77] Lan S, Clarke J P, Barnhart C (2006). Planning for robust airline operations: Optimizing aircraft routings and flight departure times to minimize passenger disruptions. Transportation Science, 40(1): 15–28

[78] Liang Z, Chaovalitwongse W A (2013). A network-based model for the integrated weekly aircraft maintenance routing and fleet assignment problem. Transportation Science, 47(4): 493–507

[79] Liang Z, Chaovalitwongse W A, Huang H C, Johnson E L (2011). On a new rotation tour network model for aircraft maintenance routing problem. Transportation Science, 45(1): 109–120

[80] Liang Z, Feng Y, Zhang X, Wu T, Chaovalitwongse W A (2015). Robust weekly aircraft maintenance routing problem and the extension to the tail assignment problem. Transportation Research Part B: Methodological, 78: 238–259

[81] Liang Z, Xiao F, Qian X, Zhou L, Jin X, Lu X, Karichery S (2018). A column generation-based heuristic for aircraft recovery problem with airport capacity constraints and maintenance flexibility. Transportation Research Part B: Methodological, 113: 70–90

[82] Lohatepanont M, Barnhart C (2004). Airline schedule planning: Integrated models and algorithms for schedule design and fleet assignment. Transportation Science, 38(1): 19–32

[83] Maenhout B, Vanhoucke M (2010). A hybrid scatter search heuristic for personalized crew rostering in the airline industry. European Journal of Operational Research, 206(1): 155–167

[84] Maher S J, Desaulniers G, Soumis F (2018). The daily tail assignment problem under operational uncertainty using look-ahead maintenance constraints. European Journal of Operational Research, 264(2): 534–547

[85] Mazareanu E (2019). Air transportation—statistics & facts.

[86] Mercier A, Cordeau J F, Soumis F (2005). A computational study of Benders’ decomposition for the integrated aircraft routing and crew scheduling problem. Computers & Operations Research, 32(6): 1451–1476

[87] Papadakos N (2009). Integrated airline scheduling. Computers & Operations Research, 36(1): 176–195

[88] PEA (2019). What do airline pilots earn?

[89] Pilla V L, Rosenberger J M, Chen V, Engsuwan N, Siddappa S (2012). A multivariate adaptive regression splines cutting plane approach for solving a two-stage stochastic programming fleet assignment model. European Journal of Operational Research, 216(1): 162–171

[90] Pilla V L, Rosenberger J M, Chen V C P, Smith B (2008). A statistical computer experiments approach to airline fleet assignment. IIE Transactions, 40(5): 524–537

[91] Pita J P, Adler N, Antunes A P (2014). Socially-oriented flight scheduling and fleet assignment model with an application to Norway. Transportation Research Part B: Methodological, 61: 17–32

[92] Pita J P, Barnhart C, Antunes A P (2013). Integrated flight scheduling and fleet assignment under airport congestion. Transportation Science, 47(4): 477–492

[93] Qantas (2016). The A, C and D of aircraft maintenance.

[94] Rexing B, Barnhart C, Kniker T, Jarrah A, Krishnamurthy N (2000). Airline fleet assignment with time windows. Transportation Science, 34(1): 1–20

[95] Rosenberger J M, Johnson E L, Nemhauser G L (2004). A robust fleet-assignment model with hub isolation and short cycles. Transportation Science, 38(3): 357–368

[96] Rushmeier R A, Kontogiorgis S A (1997). Advances in the optimization of airline fleet assignment. Transportation Science, 31(2): 159–169

[97] Ruther S, Boland N, Engineer F G, Evans I (2017). Integrated aircraft routing, crew pairing, and tail assignment: Branch-and-price with many pricing problems. Transportation Science, 51(1): 177–195

[98] Saddoune M, Desaulniers G, Elhallaoui I, Soumis F (2012). Integrated airline crew pairing and crew assignment by dynamic constraint aggregation. Transportation Science, 46(1): 39–55

[99] Saddoune M, Desaulniers G, Soumis F (2013). Aircrew pairings with possible repetitions of the same flight number. Computers & Operations Research, 40(3): 805–814

[100] Safaei N, Jardine A K S (2018). Aircraft routing with generalized maintenance constraints. Omega, 80: 111–122

[101] Salazar-González J J (2014). Approaches to solve the fleet-assignment, aircraft-routing, crew-pairing and crew-rostering problems of a regional carrier. Omega, 43: 71–82

[102] Sandhu R, Klabjan D (2007). Integrated airline fleeting and crew-pairing decisions. Operations Research, 55(3): 439–456

[103] Sarac A, Batta R, Rump C M (2006). A branch-and-price approach for operational aircraft maintenance routing. European Journal of Operational Research, 175(3): 1850–1869

[104] Seidenman P, Spanovich D J (2018). Airlines reevaluate phased A checks: The changing dynamics of the $13 billion a year line maintenance segment.

[105] Shao S, Sherali H D, Haouari M (2017). A novel model and decomposition approach for the integrated airline fleet assignment, aircraft routing, and crew pairing problem. Transportation Science, 51(1): 233–249

[106] Shebalov S, Klabjan D (2006). Robust airline crew pairing: Move-up crews. Transportation Science, 40(3): 300–312

[107] Sherali H D, Bae K H, Haouari M (2010). Integrated airline schedule design and fleet assignment: Polyhedral analysis and Benders’ decomposition approach. INFORMS Journal on Computing, 22(4): 500–513

[108] Sherali H D, Bae K H, Haouari M (2013a). An integrated approach for airline flight selection and timing, fleet assignment, and aircraft routing. Transportation Science, 47(4): 455–476

[109] Sherali H D, Bae K H, Haouari M (2013b). A Benders’ decomposition approach for an integrated airline schedule design and fleet assignment problem with flight retiming, schedule balance, and demand recapture. Annals of Operations Research, 210(1): 213–244

[110] Sherali H D, Bish E K, Zhu X (2006). Airline fleet assignment concepts, models, and algorithms. European Journal of Operational Research, 172(1): 1–30

[111] Smith B C, Johnson E L (2006). Robust airline fleet assignment: Imposing station purity using station decomposition. Transportation Science, 40(4): 497–516

[112] Souai N, Teghem J (2009). Genetic algorithm based approach for the integrated airline crew-pairing and rostering problem. European Journal of Operational Research, 199(3): 674–683

[113] Sriram C, Haghani A (2003). An optimization model for aircraft maintenance scheduling and re-assignment. Transportation Research Part A: Policy and Practice, 37(1): 29–48

[114] Stojković M, Soumis F (2001). An optimization model for the simultaneous operational flight and pilot scheduling problem. Management Science, 47(9): 1290–1305

[115] Subramanian R, Scheff R P, Quillinan J D, Wiper D S, Marsten R E (1994). Coldstart: Fleet assignment at Delta air lines. Interfaces, 24(1): 104–120

[116] Talluri K T (1998). The four-day aircraft maintenance routing problem. Transportation Science, 32(1): 43–53

[117] Vance P H, Barnhart C, Johnson E L, Nemhauser G L (1997). Airline crew scheduling: A new formulation and decomposition algorithm. Operations Research, 45(2): 188–200

[118] Wei K, Vaze V (2018). Modeling crew itineraries and delays in the national air transportation system. Transportation Science, 52(5): 1276–1296

[119] Weide O, Ryan D, Ehrgott M (2010). An iterative approach to robust and integrated aircraft routing and crew scheduling. Computers & Operations Research, 37(5): 833–844

[120] Yan C, Kung J (2018). Robust aircraft routing. Transportation Science, 52(1): 118–133

[121] Yan S, Tseng C H (2002). A passenger demand model for airline flight scheduling and fleet routing. Computers & Operations Research, 29(11): 1559–1581

[122] Yen J W, Birge J R (2006). A stochastic programming approach to the airline crew scheduling problem. Transportation Science, 40(1): 3–14

[123] Zeghal Mansour F, Haouari M, Sherali H D, Aissaoui N (2011). Flexible aircraft fleeting and routing at TunisAir. Journal of the Operational Research Society, 62(2): 368–380

[124] Zeighami V, Soumis F (2019). Combining Benders’ decomposition and column generation for integrated crew pairing and personalized crew assignment problems. Transportation Science, 53(5): 1479–1499

RIGHTS & PERMISSIONS

Higher Education Press