Solving a large-scale integrated fleet assignment and crew pairing problem

Abstract

Airline schedule planning problems are typically decomposed into smaller problems, which are solved in a sequential manner, due to the complexity of the overall problems. This results in suboptimal solutions as well as feasibility issues in the consecutive phases. In this study, we address the integrated fleet assignment and crew pairing problem (IFACPP) of a European Airline. The specific network and cost structures allow us to develop novel approaches to this integrated problem. We propose an optimization-driven algorithm that can efficiently handle large scale instances of the IFACPP. We perform a computational study on real-world monthly flight schedules to test the performance of our solution method. Based on the results on instances with up to 27,500 flight legs, we show that our algorithm provides solutions with significant cost savings over the sequential approach.

1 Introduction

Airline schedule planning problems have attracted significant attention from the operations research community over the past years, due to their sheer size and inherent complexity. These problems not only provide interesting challenges from a theoretical standpoint, but also offer opportunities for significant economical benefits for airlines. As the scope of these planning problems widens, the potential benefits from effectively solving them increase as well. Hence, simultaneously solving all related planning problems can potentially result in the maximum benefit for the airlines. However, past a certain point, the resulting integrated problem becomes so complex that it is no longer efficiently solvable. In airline planning context, this happens quite often as each individual problem is already hard to solve due its magnitude (thousands of flight legs, crews, etc). Therefore, the traditional approach is to sequentially solve these planning problems.

The first stage in airline schedule planning is the construction of the monthly flight schedule. The flight schedule consists of a list of flights to be operated in a given month. This schedule usually depends on the expected demand for the flight segments as well as the fleet size of the airline. Next, the Fleet Assignment Problem (FP) is solved, where aircraft types are assigned to the scheduled flight legs based on their capacities and operating costs, with the objective of maximizing the net profit. In the next step, maintenance requirements of the aircraft are considered while individual aircraft are assigned to specific routes. This is called the Aircraft Routing Problem.

Next, the airline must assign cockpit and cabin crew for each of the scheduled flights, which is referred to as the Crew Pairing Problem (CPP). Typically a particular cockpit crew is assigned to fly aircraft of only one fleet family, due to qualifications or economic reasons, hence the crew scheduling problem can be decomposed into sub-problems for different fleet types. The objective of the crew scheduling problems is to minimize the crew related costs. The feasibility of a crew schedule depends on rules imposed by government, international organizations (e.g. International Civil Aviation Organization), labor unions, and airline companies themselves. For a global airline that operates tens of thousands of flights in a month and employs thousands of cockpit and cabin crews, even determining a feasible crew schedule is a daunting task. The process consists of two stages. First, in the crew pairing stage, a set of feasible and efficient pairings is generated to cover each flight leg. Next, in the crew assignment stage, these pairings are used for creating monthly rosters to be flown by the available crews.

This sequential approach clearly leads to suboptimal solutions as well as potential feasibility issues. For example, after the flight schedule is created, airlines determine a fleet assignment by assigning an aircraft type to each leg, while considering the aircraft availability at each decision point. Then, these flights are assigned to individual aircraft while making sure that there is a pathwise feasible routing that also satisfies maintenance constraints of the aircraft. At the next stage, the output of the routing problem is used as an input to the crew scheduling problem. As the constraints and cost factors of the crew scheduling problem have not been considered in the previous stage, it is quite likely for airlines to face infeasibility issues or end up with less efficient solutions.

For commercial airlines, fuel costs constitute the largest chunk of the total operating cost, whereas the crew costs are a close second (Gopalakrishnan and Johnson 2005). The fleet assignment decision plays an important role in total fuel costs incurred by an airline just like the crew planning decision affects crew related costs. As the former decision heavily influences the latter decision, we attempt to tackle both problems simultaneously to determine a better solution for the overall planning problems of an airline. Even though individual FPs and CPPs have been studied extensively in the literature, integrated approaches are quite limited; these are summarized in detail in Sect. 2.

In this paper we address the Integrated Fleet Assignment and Crew Pairing Problem (IFACPP) of a European Airline Company (EAC). The associated FP and CPP for this particular case differs from the ones studied in the literature in three important aspects: (1) schedule periodicity, (2) flight network structure, (3) cost structure. These features are not limited to EAC but arise in airlines worldwide. Firstly, the majority of the works in the literature focus on the North American flight network, assume that a daily schedule repeats itself with some minor changes. Thus, it is sufficient to solve a daily problem rather than the monthly problem and then adjust the solution to accommodate for these changes. Due to the irregularities in the flight schedule, employing these techniques proposed in the literature for may not produce efficient solutions for most European airlines and the problem under consideration.

Secondly, the flight network has its own characteristics as well. There is only one crew base (we refer to it as BASE) and more than 80 % of the flights either originate from or terminate at BASE. In addition to this, a significant portion of the flights to several domestic and most international destinations are rotation type flights. For example, if there is a flight from BASE to Rome in the morning on a given day, there is also a flight returning to BASE later that day, as there exists no other flights from Rome to any other destination and the aircraft (hence the crew) will not stay in Rome for an additional day.

Finally, the cost structure as well as the number of hubs and flight patterns are considerably different than most of the works studied in the literature, mainly those related to the North American flight networks. In EAC, like most European airlines, the crews receive fixed monthly salaries, thus the objective of the CPP stage is to minimize the costs of layovers (crews resting overnight in locations other than their bases) and deadheadings (crews being transported on a flight as passengers). In most North American airlines the crew cost structure is based on complex rules that depend on flying hours, time away from base, etc. Based on these characteristics of the problem, we attempt to develop a specific solution approach to the IFACPP under consideration.

Our objective is to solve the monthly IFACPP, which involves approximately 27,000 flights, two aircraft families, over 100 aircraft and airports. We do this, in part by relying on the CPP solution approach developed by Erdogan et al. (2015). We develop a heuristic approach to the FP. Our model completely integrates the FP and CPP, but neglects aircraft maintenance constraints of aircraft routing component. As in Sandhu and Klabjan (2007), in the case where aircraft maintenance requirements are satisfied due to the structure of the underlying flight network, our model also integrates the routing problem. In our implementation, we employ a combination of heuristic and exact methods, including greedy heuristics, local search methods, matheuristics, assignment models, set covering models, and finally an integer programming model. The heuristics allow computational efficiency for a problem of this complexity and size, and exact methods working in combination with the heuristics improve the quality of the solution. Our major contribution is the development of a computationally efficient solution to the monthly integrated problem. Although there are a small number of studies on “monthly” or “integrated” problems, to the best of our knowledge our study is the first to tackle both aspects simultaneously. We show that, by taking into account the special structure of the problem we are able to generate good solutions to such a large sized problem, and that by addressing the integrated problem better results are obtained than addressing the individual problems sequentially. Our approach is not limited to the airline schedule planning problem at EAC, it can be applied to other airlines with similar cost and network structure.

The outline of the paper is as follows. In Sect. 2, we summarize the existing studies in current literature. In Sect. 3, we provide the problem definition. In Sect. 4, we describe the solution approach, and in Sect. 5, we present the results of our computational study for 5 instances each with approximately 27,000 legs. Finally, in Sect. 6, we provide our conclusions.

2 Literature review

Both FP and CPP have been studied widely in the literature. For both problems, it is a common assumption of the literature that the flight schedule repeats daily, thus most models are developed to tackle the daily problem. When extending the daily schedules to weekly or monthly schedules, the exceptions to the repeating daily schedules are handled afterwards.

In FP, given a flight schedule and a set of aircraft, the objective is to assign each flight to an aircraft type so that the profit is maximized. These aircraft types may have different capacities, availabilities and operating costs. Assigning an aircraft with a capacity higher than demand will result in unsold seats, while assigning an aircraft with a capacity smaller than needed on a flight will result in lost customers. The operating costs (including fuel, landing fees etc.) also depend on the type of aircraft assigned to the flight. FP has been largely treated as a multi-commodity network flow problem with cover, flow balance, and aircraft availability constraints. We refer the reader to Abara (1989), Daskin and Panayotopoulos (1989), Berge and Hopperstad (1993), Subramanian et al. (1994). Typically, the daily schedule is represented as a closed-loop space-time network, where a directed arc corresponds to the movement of an aircraft on a flight leg, and each arrival and departure at an airport is depicted by a node for each valid aircraft type. Aircraft waiting on ground is depicted by an arc between successive nodes in time. Overnight stays are depicted by wrap-around arcs from the last node to the first node at each airport. For a survey of FP models see Gopalakrishnan and Johnson (2005).

The traditional fleet assignment model [an adaptation of Hane et al. (1995)] is stated below.

$$\begin{aligned} \max&\sum _{f \in F}\sum _{\ell \in L}p_{f\ell } x_{f\ell } \end{aligned}$$

(1)

$$\begin{aligned} \text {s.t.}&\sum _{f \in F} x_{f\ell }=1&\quad \forall \ell \in L \end{aligned}$$

(2)

$$\begin{aligned}&\sum _{o \in S} x_{fost}+y_{fst^-t}-\sum _{d \in S}x_{fsdt}-y_{fstt^+}=0&\quad \forall {fst}\in N \end{aligned}$$

(3)

$$\begin{aligned}&\sum _{\ell \in O(f)}x_{f\ell }+\sum _{s\in S}y_{fst_nt_1}\le A_f&\quad \forall f\in F \end{aligned}$$

(4)

$$\begin{aligned}&x \in \{0,1\} \end{aligned}$$

(5)

$$\begin{aligned}&y\ge 0 \end{aligned}$$

(6)

where the parameters and decision variables are defined as follows:

S::

the set of airports in the network

F::

the set of aircraft (fleet) types%, indexed by f,

L::

the set of flight legs scheduled, indexed by $\ell$ or odt, where $o,d\in S$, and t is the take off time at o or the ready time for the next take-off at d

N ::

the set of nodes in the network, indexed by fst, where $f\in F$, $s \in S$, and t denotes the take off or landing time at s,

O(f) ::

the set of arcs for fleet type $f\in F$ that cross the aircraft count time-line,

$p_{f\ell }$::

the profit of assigning fleet type f to leg $\ell$, $f \in F, \ell \in L$,

$A_f$::

the number of available aircraft of each aircraft type f, $f\in F$,

$t^-$::

the time preceding t in the event time-line.

$t^+$::

the time following t in the event time-line.

$t_n$::

the time of the last node in the time-line before the aircraft count time-line

$t_1$::

the time of the successor to the last node in the time-line before the aircraft count time-line

The decision variables are x and y, where, $x_{f\ell }=1,$ if aircraft type f covers leg $\ell$; $f\in F,\ell \in L$; and 0, otherwise. $y_{fstt'}$ is the flow of aircraft on the ground arc from node ${fst} \in N$ to node ${fst'} \in N$ at airport $s\in S$ in aircraft type f’s network, for $f\in F$, where $t'=t_1\le t=t_n$ for wrap-around arcs, and $t' > t$ otherwise.

The objective function (1) maximizes the profit of assigning aircraft types to flight legs. Constraints (2) ensure that each flight in the schedule is assigned exactly one aircraft type, constraints (3) conserve the flow of aircraft (an aircraft that takes off must land), and constraints (4) ensure that the total number of aircraft assigned cannot exceed the number available in the fleet.

For a network of hundreds of airports and thousands of legs, this problem becomes very challenging to solve. Indeed, Gu et al. (1994) have shown this problem to be NP-hard for three aircraft types, even without the availability constraints. To this end, there have been efforts at reducing the problem size by using preprocessing techniques such as node aggregation and creation of islands. In node aggregation, irrespective of the exact time of arrival or departure, consecutive arrivals and the subsequent consecutive departures can share a single node such that each arrival at the aggregated node can be feasibly connected to any departure at this node, see e.g. Hane et al. (1995). In the case of sparse flight activities where no aircraft are on the ground during certain periods of time, these ground arcs with zero value can be deleted to create islands, e.g. see Rushmeier and Kontogiorgis (1997).

Aside from the basic fleet assignment model, several variations and extensions (such as integrating aircraft maintenance, discretized time windows, weekly assignments with homogeneity etc.) have been studied in the literature. The methods used to tackle these problems include solving the linear programming (LP) relaxation of the mixed integer model and applying rounding heuristics and using branch-and bound search techniques for remaining variables (Rushmeier and Kontogiorgis 1997), Lagrangean relaxation (Daskin and Panayotopoulos 1989), branch-and-price solution schemes (Hane et al. 1995; Bélanger et al. 2006), large-scale neighborhood search (Ahuja et al. 2007). We refer the reader to Sherali et al. (2006) for a more comprehensive survey of fleet assignment models.

Crew pairing problem is generally considered as the hardest of the airline planning problems and has been extensively studied in the literature. Usually, the CPP is modeled as a set partitioning problem where the rows represent flights to be covered and the columns represent the candidate crew pairings. The objective is to minimize the total cost of pairings while covering each flight.

We now provide a basic mathematical representation of the CPP.

$$\begin{aligned} \min&\sum _{j\in P} c_j x_j&\end{aligned}$$

(7)

$$\begin{aligned} \text {s.t.}&\sum _{j\in P} a_{\ell j}x_j = 1, \, \quad \forall \ell \in L&\end{aligned}$$

(8)

$$\begin{aligned}&x_j \in \{0, 1\},&\end{aligned}$$

(9)

where the parameters and decision variables are defined as follows:

P::

the set of all feasible pairings,

$c_j$::

the cost of pairing j,

$a_{\ell j}$::

1, if pairing j covers flight $\ell$, and 0 otherwise,

L ::

the set of all flights that must be covered in the period of time under consideration.

The decision variable $x_{j}$, takes the value of 1 if pairing j is selected, and 0 otherwise.

Numerous solution methodologies have been developed for CPP. Many of these approaches rely on pairing generation and pairing selection strategies. In early works heuristic approaches were employed to generate a subset of the pairings (e.g.   Arabeyre et al. 1969, Gershkoff 1989, Anbil et al. 1991) that were then used in the set partitioning problem. The downside of this approach is that it is not possible to quantitatively assess the quality of the solution. Pairings are frequently generated using either with an enumerative algorithm or shortest path approximation approach on a graph network that can be represented either as a flight segment network or a duty network (Paleologo and Snowdon 2007). In these, branch-and-price techniques have been used frequently (Ryan 1992; Barnhart et al. 1994; Vance et al. 1997; Barnhart et al. 1998b; Desrosiers et al. 1998; Butchers et al. 2001; Dück et al. 2011). However, pricing algorithm may take prohibitively long time for very large instances.

Many works in the literature address the daily CPP problem with instance sizes of up to 1000–2000 daily flights, there are others that address the weekly (e.g. Butchers et al. (2001) for instances from 300 to 900 legs), monthly (e.g. Kasirzadeh et al. (2015) for instances from 1013 to 7765 legs, and  Subramanian and Sherali (2008) for instances from 2000 to 16,000 legs) problem. Large-sized monthly crew pairing instances are usually addressed by a three-phase approach in the industry. Initially, assuming the daily schedule repeats, a daily problem is solved. Then in the second phase the a weekly solution is derived from the daily solution and finally exceptions in the monthly schedule are handled starting from an initial solution obtained in the weekly problem. This approach enables handling large instances in shorter computational times and favors regularity in the solution. However, when flight schedules are not regular this approach yields poor solutions. Indeed, Saddoune et al. (2013) develop a solution method on a rolling horizon basis that performs better than this multi-phase approach.

Another approach used to solve the CPP is heuristics. Metaheuristics like simulated annealing (Emden-Weinert and Proksch 1999), tabu search (Cavique et al. 1999), genetic algorithms (Chen et al. 2013; Levine 1996; Ozdemir and Mohan 2001), ant colony algorithms (Deng and Lin 2011), particle swarm optimization (Azadeh et al. 2012, 2013) have been employed, as well as hybrid algorithms that combine that combine heuristics with exact optimization methods (e.g. Panayiotis et al. 2000, Aydemir-Karadag et al. 2013, Erdogan et al. 2015). Advantages of heuristics include speed and the size of instances that can be handled, whereas the quality of the solutions obtained can only be empirically demonstrated. We refer the reader to Desrosiers et al. (1998), Barnhart et al. (2003a, (2003b), Gopalakrishnan and Johnson (2005), Kasirzadeh et al. (2015) and references therein for a more comprehensive review.

Recently there have been attempts that aim to integrate several of the airline problems. There have been efforts in jointly solving the flight scheduling problem and FP. For example, Rexing et al. (2000) develop a version of the basic FP model that assigns a time window to each flight, which makes it possible to optimize departure times. Lohatepanont and Barnhart (2004) start from a base schedule and introduce modifications to the base schedule. Different demand parameters and demand correction terms are estimated and revised iteratively. In addition to a modified schedule, they determine an associated fleet assignment. Sherali et al. (2010) develop a model that integrates flight scheduling and fleet assignment using itinerary-based demands, for which they apply Benders decomposition to a mixed integer programming model augmented with several classes of valid inequalities and Sherali et al. (2013) address a similar problem that also includes flexible flight times, optional legs, and multiple fare-classes.

Clarke et al. (1996) address a variant of the FP with maintenance and crew considerations. They include constraints and modeling aspects in the basic fleet assignment model that retain its solvability and improve solution quality. Desaulniers et al. (1997) consider a daily aircraft routing and scheduling problem, for which a heterogeneous fleet has to be assigned to a set of legs with departure time windows. They present two formulations, one based on set partitioning and the other on a multi-commodity network flow model. Exploiting the equivalence between the two formulations, they propose branching strategies. Barnhart et al. (1998a) address the integrated fleeting and routing problem for which they present a string-based model and branch-and-price algorithm, where strings refer to a set of connecting flights starting and ending at maintenance stations. More recently, Haouari et al. (2011) propose two exact algorithms to the integrated fleeting and routing problems. Their algorithms are based on a tailored Benders decomposition algorithm that includes Benders cuts, maximal clique constraints and combinatorial cuts that help eliminate symmetry; and column generation (i.e. branch and price) algorithm with branching on the path variables.

In another track of integrated airline schedule planning problems, the integrated routing and CPP has been studied. For example, Cordeau et al. (2001) have utilized linking constraints to ensure that for short connection times, crew does not change aircraft. The authors solve the problem using Benders decomposition, where the algorithm iterates between a master routing problem and a crew pairing sub-problem. Klabjan et al. (2002) have partially integrated routing and crew pairing problems. They solve the crew scheduling problem before the aircraft routing and assume that flight departure times are not fixed, but must be performed within a time window. To ensure feasibility of the routing problem, they add additional constraints to the crew scheduling model. Cohn and Barnhart (2003) solve an integrated routing and crew pairing problem where they include variables for complete routing solutions. This eliminates the need to include the routing formulation in the model, reducing the number of constraints while increasing the number of variables. They show that only a subset of the feasible solutions need to be included in the model. Mercier et al. (2005) improve the model of Cordeau et al. (2001) by introducing the concept of restricted connections, which enable more robust solutions to the integrated routing and crew pairing problem. They compare two implementations of the Benders decomposition approach and improve the speed of convergence. Mercier and Soumis (2007) include time windows to this formulation. In a similar manner, Papadakos (2009) attempts to integrate routing and crew pairing and proposes a method based on Benders decomposition and accelerated column generation.

There have also been efforts towards solving the IFACPP. Barnhart et al. (1998c) address the daily IFACPP, but instead of simultaneously solving the two problems, they include a relaxation of the crew scheduling problem within the fleet assignment model. This relaxation does not impose pairing feasibility rules, such as maximum duties in a pairing, maximum time away from base, but covering flight legs is required. Sandhu and Klabjan (2007) also address the daily IFACPP. Their solution approaches rely on Benders decomposition and Lagrangian relaxation. While they ignore aircraft maintenance routing, they ensure plane count feasible aircraft routings. When maintenance requirements are satisfied due to the structure of the underlying network, their model fully integrates these three problems. Gao et al. (2009) develop an integrated fleet and crew robust planning method on a daily schedule. Instead of directly modeling explicit duties or pairings, they model crew connections within the integrated model. This helps them keep the model tractable. For robustness, they limit the number of fleet types and crew bases that are allowed to serve each airport.

As the above summary shows the FP and CPP have been studied widely in the literature. While there are significant contributions in terms of methods, the sheer size of the EAC problem makes most of them inapplicable. Recently, there have been more work done to address larger problems, as in Subramanian and Sherali (2008), where they address the monthly problem in a rolling horizon basis. Again the structural differences in the problems, both in terms of the cost function and the flight network, make it natural to look for alternative solution approaches. Furthermore, solving the integrated problem, IFACPP, offers greater opportunities. The existing literature on IFACPP is limited and mainly addresses the daily problem. Extending these methods to handle a monthly problem of the EAC’s size is not feasible. Given the size and nature of the network and objective function we implement a method that is a combination of heuristic and exact methods. This combined effort allow us to achieve computational efficiency and improved quality in our results.

3 Problem definition

In this section, we provide a formal definition of our problem. Our instances have two aircraft families (Airbus 320 and Boeing 737) that fly short- and medium-haul flights. The flight schedule includes approximately 27,000 flights per month to more than 100 destinations. Each aircraft family consists of several aircraft types with different capacities and operating costs. For the fleet assignment component, we aim to maximize the expected profit of assigning aircraft to flight legs. For each leg and aircraft type there is an associated expected profit, that accounts for expected revenues and cost of operating the aircraft. We note that there are fleet assignment models in the literature that capture the impact of itinerary based demand, rather than the leg based demand model we have presented. These models are better able to capture the impact of spill and recapture of demand. Such itinerary based demand and pricing models have resulted with superior fleet assignment/capacity solutions. See for example,  Barnhart et al. (2002) and Wang et al. (2013) for itinerary based fleet assignment models, Atasoy et al. (2014) for an integrated scheduling, fleeting and pricing model with itinerary based demand, Sherali et al. (2010) for an integrated flight scheduling and fleet assignment model with itinerary based demands. For the crew pairing component, we aim to minimize the costs of assigning crews to flight legs. In the integrated problem we maximize the total profit from both components of the problem.

As we address IFACPP, we make assignments for individual aircraft instead of just to an aircraft family or an aircraft subtype. This allows us to capture the CPP more accurately as connection times depend on whether the crew continue on the same aircraft or change aircraft. In doing so, we actually solve the routing problem as well, except for the maintenance requirements of the aircraft. If due to the underlying network structure, aircraft maintenance requirements are satisfied, our model also integrates the routing problem along with fleet assignment and crew pairing problems.

Next, we present the mathematical model of our integrated problem.

$$\begin{aligned} \max \sum _{a\in A}\sum _{j\in L}{\varPi }_{aj}x_{aj}-\sum _{p\in P}\gamma _{p}y_{p} \end{aligned}$$

(10)

s.t.

$$\begin{aligned}&\sum _{a\in A}x_{aj} =1\quad \forall j\in L \end{aligned}$$

(11)

$$\begin{aligned}&\sum _{p\in P_{j}}y_{p} =1\quad \forall j\in L \end{aligned}$$

(12)

$$\begin{aligned}&\sum _{\{k\in L{ \cup \{t}_{a}{ \}}:o(k)=d(j)\}}u_{ajk} =x_{aj}\quad \forall {a\in A},\quad \forall j\in L \end{aligned}$$

(13)

$$\begin{aligned}&\sum _{\{k\in L{ \cup \{s}_{a}{ \}}:d(k)=o(j)\}}u_{akj} =x_{aj}\quad \forall {a\in A}, \quad \forall j\in L \end{aligned}$$

(14)

$$\begin{aligned}&\sum _{\{j\in L:d(s_{a})=o(j)\}}{ u}_{as_{a}j} { \le 1\quad \forall a\in A} \end{aligned}$$

(15)

$$\begin{aligned}&\sum _{\{j\in L:d(s_{a})=o(j)\}}{ u}_{as_{a}j} { =}\sum _{j\in L} { u}_{ajt_{a}}{ \quad \forall a\in A} \end{aligned}$$

(16)

$$\begin{aligned}&\sum _{f\in F}w_{pf} =y_{p}\quad \forall p\in P \end{aligned}$$

(17)

$$\begin{aligned}&y_{p}+\sum _{a\in A_{f}}x_{aj} \le 1+w_{pf},\quad \forall j\in L,\text { } \quad \forall p\in P_{j}, \quad \forall f\in F \end{aligned}$$

(18)

$$\begin{aligned}&x_{aj},w_{pj},y_{p},u_{ajk} \in \{0,1\}, \end{aligned}$$

(19)

where the parameters and decision variables are defined as follows:

Sets

F::

Set of aircraft types (fleet types),

P::

Set of all feasible pairings

$P_{j}$::

Set of pairings covering leg j actively, $P_{j}\subset P$

L::

Set of all legs

A::

Set of all aircraft

$A_{f}$::

Set of aircraft of family f

$L_{2}$::

$\{(j,k):j,k\in L$ and compatible (feasible connection time/location)$\}$.

Parameters

${\varPi }_{aj}$::

Expected net profit of assigning aircraft a to leg j

$\gamma _{p}$::

Cost of pairing p

o(j)::

Origin airport of flight $j\in L$

d(j)::

Destination airport of flight $j\in L$

$s_{a}$::

Auxiliary flight that represents the start of the route flown by aircraft $a\in A$ (if any). The destination of this auxiliary flight is the origin airport of aircraft $a\in A$

$t_{a}$::

Auxiliary flight that represents the end of the route flown by aircraft $a\in A$ (if any). This auxiliary flight is compatible with all flights.

Decision variables

$x_{aj}$::

binary variable, 1 if aircraft a is assigned to flight j, $a\in A$, $j \in L$

$u_{ajk}$::

binary variable, 1 if aircraft a is assigned to flight k immediately after flight j, $a\in A,$ $(j,k) \in L_2$

$y_{p}$::

binary variable, 1 if pairing p is chosen

$w_{pf}$::

binary variable, 1 if pairing p is assigned to family f

The objective function (10) maximizes the total profit of IFACPP. Constraints (11) enforce that each leg is assigned to an aircraft, and constraints (12) ensure that each leg is covered actively by a pairing. Constraints (13) and (14) dictate that if $x_{aj}=1$ then flight j has exactly one successor and one predecessor, respectively. Constraints (15) require that there can be at most one departure from the auxiliary start flight for each aircraft. Similarly, constraints (16) require that an auircraft that has departed must end its route at the auxiliary end flight. Constraints (17) state that each pairing is assigned to exactly one aircraft type if selected. Constraints (18) ensure that if a leg is to be covered by a pairing, then this pairing is assigned to the corresponding aircraft type. Finally, constraints (19) are the integrality constraints.

As we have 27,500 legs and 128 aircraft, the number of just the $u_{ajk}$ binary variables exceeds 94 billion. It is possible to reduce this number by considering the compatibility of the legs, however it is not possible to reduce this number to an acceptable value. Hence, the model above only provides a mathematical explanation of our problem and it is not possible to solve this model using standard solvers or methodologies. This is our motivation in designing a time efficient solution approach to the integrated problem. In Sect. 4, we describe this approach in detail.

4 Solution method

In this section, we describe our integrated approach for solving IFACPP. Our approach first employs a procedure that solves FP and CPP sequentially. Note that a very good solution for the FP phase may produce undesirable results for the CPP. Devising a mechanism that signals this information back to the FP phase, we may modify the solution in the FP phase to obtain better solutions in the CPP phase. With this in mind, we redesign our solution methodology for the FP phase to receive and process information on the subsequent CPP solution. This results in an iterative solution to IFACPP. Performing a number of iterations, and recording the solutions at each iteration, we apply a final selection procedure to simultaneously determine solutions for both FP and CPP, which have the best aggregate objective function value.

The real challenge in solving the FP is due to the precedence relationships, each flight assigned to an aircraft must be compatible with both the preceding and the succeeding flights. We first identify a “good” initial solution, using FP Initialization (FP_0) algorithm, that generates chains of flight legs with a greedy heuristic, then assigns these chains to the available aircraft to maximize the total profit of the FP phase by solving an assignment problem. The profit in the FP phase is calculated as the revenues from the ticket sales minus the operating cost of the aircraft on the given flight legs. Starting with this initial solution, we improve the solution using a mix of local search, iterated local search and exact optimization algorithms. This results in a solution that includes assignments to individual aircraft. For the CPP we utilize an algorithm (LNS1), developed by Erdogan et al. (2015), which uses a combination of metaheuristics and exact optimization methods to solve the CPP in an iterative manner.

The procedures followed to solve the IFACPP are depicted in Fig. 1. Each procedure is described in detail below.

Fig. 1

Summary of solution approach

FP initialization

To initialize the fleet assignment procedure, we start with a time sorted leg list. Starting with the first leg, we create chains of flights that can be performed consecutively. We generate these chains in a greedy manner, that is, after adding the leg which arrives at time $t_a$ to the chain, we obtain the “ready time” as $t_a+r$, where r is the minimum turn time, which is 30 min. Next, we identify the first fight leg that departs from that particular airport at or after the ready time and add that flight leg to the chain and we continue in this manner. If there is no flight departing from that particular airport up until a certain time (14 h for domestic and 48 h for international locations), then there are no more feasible legs to be added to this chain and we start a new chain from the first unassigned leg in the time sorted leg list. Once all legs are included to a chain, we concatenate feasible chains, to reduce the number of chains to the number of available aircraft. This concatenation step is different than adding legs to a chain in a greedy manner. Here we include the possibility of repositioning of an aircraft and concatenate two previously generated chains if one aircraft can feasibly perform one after the other while accounting for the deadheading flight time from the arrival location of the last flight of the first chain to the departure location of the first flight of the second chain. As in the previous routine, concatenation process is also greedy hence a chain is concatenated to the earliest feasible chain. Note that the chains are not required to start and terminate at the same airport as the initial condition (locations of aircrafts, crews, etc.) at the beginning of each month might be different from one another.

FP local search (sub-chain based)

Next, we implement a local search algorithm that updates the initial fleet assignment solution, by switching a portion of the chains created before to generate more profitable chains and reassigning to the aircraft. Given two chains, there may exist several switching points where we can cut the chains and create new chains from these switching points. Identifying all possible switching points between any pair of chains is a computationally expensive procedure, nevertheless, still doable. However due to the extensive computational time, this procedure takes too long to converge to a good solution. Therefore, instead of applying this model right after the initialization step, we perform an intermediate local search based on “sub-chains”, which are sequences of flight legs that start and end at the BASE. The motivation for using these sub-chains is the fact that most of these switching points occur at the BASE due to the flight network characteristics. Therefore, we cut the long chains into sub-chains. We assume that these sub-chains are not further decomposable in the switching process. We obtain new chains by switching these sub-chains between compatible long chains. We illustrate this with a small example. Suppose there are two chains, 1–2–3–4–5–6, and a–b–c–d–e–f–g–h, with sub-chains 1–2–3, 4–5–6, a–b–c–d and e–f–g–h. Then, the pair (3, d) is a potential switching point. Then we create new chains by exchanging these sub-chains within the long chains to create new chains. In this small example, the new chains would be 1–2–3–e–f–g–h and a–b–c–d–4–5–6. Note that a pair of chains might have several switch points depending their compatibility. From 128 chains created in the previous step, we generate approximately 4000 sub-chains. Hence, when we use sub-chains instead of the flight legs, we increase the granularity in the hope that the procedure converges much faster due to less number of combinations. We identify all possible switching points for all pair of chains and calculate the benefit of all possible switches using the previously assigned aircraft and sort these possible switches with respect to their marginal benefits. Next, we continue with switching the portions of the chains and reassigning these to the aircraft until we cannot find any profitable switches to perform (previously modified chains can no longer be used in the switching process). Repeating this step for a certain number iterations ($n_{sub}$) quickly brings the problem to a “better” fleet assignment solution compared to the initial solution of FP_0. The details of this procedure are as follows:

FP iterated local search

At this point, we have a “good” solution to the FP, and we start a more detailed iterated local search. In essence, as a subroutine we use a local search algorithm that performs the switching procedure discussed above on a leg basis, instead of mini chains. Using the same example, we illustrate this “leg-based switch”. Recall that we have two chains, 1-2-3-4-5-6, and a-b-c-d-e-f-g-h, with sub-chains 1-2-3, 4-5-6, a-b-c-d and e-f-g-h. Then, in “mini chain-based” switch, the pair (3, d) is the only potential switching point. However, assuming the compatibility of the legs the pairs (2, b) and (5, g) might be other potential switching points besides (3, d) as now we are allowed to break mini chains. Clearly, this leg-based switch is computationally more challenging compared to the previous case as the number of potential switch points are much higher and they may occur at some airport other than the BASE. We carry out these iterations until we reach a local maximum point where we cannot improve the solution anymore. After reaching this local maximum, we perturb the solution by randomly breaking $\alpha$ of the chains and creating new chains by patching these broken chains to other chains. Starting with this perturbed solution, we repeat the leg based local search algorithm for a certain number of iterations ($n_{iter}$). The reason for implementing this perturbation is to avoid to be stuck at local optima.

Iterating this step $n_{iter}$ times yields an improved solution to FP.

FP polishing

To obtain a final solution to the FP, we implement a final polishing step. In this step, we take all the chains created during the $n_{iter}$ iterations of FP_ILS, and upon deleting duplicate chains, we solve a set partitioning problem (SPP) with side constraints so that each leg is covered once by the selected chains and each selected chain is assigned to an aircraft to maximize the profits. The details of this polishing step is as follows:

SPP_0:

$$\begin{aligned} \max \sum _{c\in \hat{C}}\sum _{a \in A}{\varPi }_{ca}x_{ca} \end{aligned}$$

(20)

subject to

$$\begin{aligned} \sum _{c\in C_j}\sum _{a \in A}x_{ca}= & {} 1,\quad \forall j\in L, \end{aligned}$$

(21)

$$\begin{aligned} \sum _{a\in A} x_{ca}\le & {} 1, \quad \forall c \in \hat{C}, \end{aligned}$$

(22)

$$\begin{aligned} \sum _{a\in A, c \in \hat{C}}x_{ca}\le & {} N_A \end{aligned}$$

(23)

$$\begin{aligned} x_{ca}\in & {} \{0,1\},\quad \forall c\in \hat{C},a\in A, \end{aligned}$$

(24)

where

$C_j$::

set of chains covering leg l, $C_j\subset \hat{C}$,

${\varPi }_{ca}$::

expected net profit of assigning aircraft a to chain c,

$x_{ca}$::

binary decision variable, 1 if aircraft a is assigned to chain c, $a\in A$.

The objective function (20) requires maximizing the total expected profit by assigning aircraft to chains while the partitioning constraints (21) enforces that exactly one chain is assigned to each leg. Constraints (22) states that each aircraft is assigned at most to one chain. Constraint (23) ensures that the number of available aircraft is not exceeded.

Our overall process to determine an FP solution is summarized as follows:

CPP

We solve the CPP based on the fleet assignments found in FP phase. To solve the CPP, we implement the LNS1 algorithm of Erdogan et al. (2015) for both aircraft families. In LNS1, Erdogan et al. (2015) use a combination of metaheuristics and exact optimization methods to solve the CPP in an iterative manner. The procedure finds a feasible solution in a greedy manner and then randomly removes a fraction of its pairings. Thus, the solution to CPP becomes infeasible as a subset of legs now becomes uncovered. For each uncovered leg, a minimum-cost pairing is identified via a depth-first branch-and-bound algorithm. The pairing thus derived is included in the solution and the process is reiterated until a feasible solution $S^{\prime }$ to CPP is obtained. Then, the process is restarted with $S^{\prime }$ being the new working solution. After a number of iterations, as an intermediate step, an SPP is solved with the pairings obtained in all previous solutions to update the current working solution and the process continues iteratively from this updated solution. We refer the reader to Erdogan et al. (2015) for more details.

We solve FP and CPP sequentially using $FP+$ and LNS1 procedures to obtain an overall solution for the integrated problem sequentially. Since our FP solution gives assignments to aircraft (instead of aircraft types) constraints like connection time, which depend on whether crew changes aircraft, are correctly represented in the CPP stage. The solution obtained in this sequential manner will serve as a benchmark for evaluating our integrated solutions. Next, we describe two procedures that we developed to solve the IFACPP, the first is an iterative procedure that takes the implications of the solution of one stage to the other and iteratively updates the solution of each stage. This solution is expected to provide better results than the sequential approach as considerations from each stage is reflected in the other. The second approach addresses IFACPP through a new formulation of the problem, which can be summarized as a simplified version of the model (10)–(18) that relies on the solutions obtained during the iterative procedure. With this model we simultaneously solve the FP and CPP stages. We first describe the iterative approach.

Iterative FP and CPP

In order to iteratively solve FP and CPP, we require a feedback mechanism from CPP phase to FP phase, indicating that some of the fleeting decisions actually lead to costly crew pairings. Although we can identify costly pairings immediately, we cannot determine the exact cause that made those pairings costly. However, one can safely assume that the flight legs covered by a pairing influence the cost of the pairing. Hence, we first identify costly pairings (deadheading plus layover costs) and then divide the pairing cost to the number of active legs in that pairing. Here, active legs, refer to the legs that the crew is not deadheading. Then, we sort all legs for both aircraft families in descending order of their costs, and reassign the most costly $\beta$ legs of each family to the other family. We continue with the FP_ILS procedure after this CPP phase. We repeat this iterative process $n_{it}$ times.

Simultaneously solving FP and CPP

Our motivation for analyzing the integrated problem is to obtain FP and CPP solutions that produce the best result for IFACPP. The iterative process, described above, transfers information from the CPP phase back to the FP phase in order to increase the compatibility of solution in phases, thus results with an increase in the overall profitability of the airline. Even though higher benefits are achieved through this iterative process, we still solve FP and CPP separately, and this limits the overall improvement. To overcome this limitation, we develop a simultaneous solution procedure that handles both FP and CPP at the same time. During the iterative process, we collect several FP and CPP solutions, namely chains and pairings. In this simultaneous procedure, we develop new integer programming formulation that selects and assigns chains and pairings so that each leg is covered by exactly one chain and one pairing and make sure that those two belong to the same aircraft family. This new model can be viewed as a “double” set partitioning problem for the flight legs with additional constraints, hence is a difficult problem to solve especially considering the size of the problem. The best known algorithm to solve this problem has an exponential complexity. Using the same notation as in (10)–(19) and (20)–(24) for defining the sets and parameters, the new mathematical model is as follows:

$$\begin{aligned} {\textit{IP}}: \max \sum _{a\in A} \sum _{c\in C} {\varPi }_{ca} x_{ca}-\sum _{p\in P}\gamma _p (y_{p1} + y_{p2}) \end{aligned}$$

(25)

s.t.

$$\begin{aligned} \sum _{c \in C_{j}} \sum _{a\in A} x_{ca}&=1\quad \forall j \in L \end{aligned}$$

(26)

$$\begin{aligned} \sum _{c \in C} x_{ca}&\le 1 \quad \forall a \in A \end{aligned}$$

(27)

$$\begin{aligned} \sum _{p \in P_{j}} (y_{p1} + y_{p2})&=1\quad \forall j \in L \end{aligned}$$

(28)

$$\begin{aligned} \sum _{p \in P_{j}} y_{p1} - \sum _{c \in C_{j}} \sum _{a\in A_{1}} x_{ca}&= 0\quad \forall j \in L \end{aligned}$$

(29)

$$\begin{aligned} \sum _{p \in P_{j}} y_{p2} - \sum _{c \in C_{j}} \sum _{a\in A_{2}} x_{ca}&= 0\quad \forall j \in L \end{aligned}$$

(30)

$$\begin{aligned} x_{ca}, y_{pf} \in \{0,1\}.&\end{aligned}$$

(31)

Decision variables

$x_{ca}$::

binary variable, 1 if aircraft a is assigned to chain c, $a\in A$

$y_{pf}$::

binary variable, 1 if pairing p is selected to be covered by an aircraft of family $f =\{1,2\}$

The objective function (25) maximizes the total profit of IFACPP. Constraints (26) ensure that each leg is covered by a chain. Constraints (27) ensure that an aircraft is assigned to at most one chain. Constraints (28) guarantee that a leg is covered actively by a pairing of either aircraft families. Constraints (29) and (30) respectively ensure that if a leg is covered by a pairing of family f, then the corresponding chain should be also assigned to an aircraft that belongs to family f. In fact, Constraints (30) are redundant as long as Constraints (29) are present.

Finally, the details of the procedure are as follows:

5 Computational study

We have tested our solution method on five instances of data sets acquired from publicly available data of EAC. We consider two aircraft families (Airbus 320 and Boing 737) that fly short- and medium-haul flights. We focus on these two aircraft families as they are frequently used for serving the same destinations due to similarity of their range and capacities. The flight schedules for the five instances consist of 26,260, 26,501, 27,139, 27,348 and finally 27,360 legs. There are six and eight aircraft types (including different seating configurations and different operating costs) within the Airbus 320 and Boeing 737 families, respectively. There are a total of 128 aircraft available.

We do not have information about the initial location of aircraft and crew at the beginning of the planning period of our instances. We resolve this by adding a 1-week warm-up. This allows us to reach a feasible starting point for solving the IFACPP. We also add a 1-week cool-down period at the end of the month. As we include 1 week of warm-up in the beginning and 1 week of cool-down period at the end of each month, we solve a 42-day problem instead of a one-month problem for each instance, hence these numbers correspond to a 6-week planning horizon. When reporting results, we only include results related to the flights within the particular month. Other than the change in number of legs in the instances, based on the month, we see that some new destinations are added and some others see significant changes in the number of flights schedules to and from those airports. The increase in the number of flights to/from an airport can be as high as 70 % as the season changes. The average increase in the number of flights to/from an airport with changed number of total flights is 31 %.

In the FP phase, for profit and cost parameters, we use representative figures that reflect true values in terms of proportions and magnitudes. For aircraft operating costs we relied on available industry data for different aircraft types, although these costs may not be exact costs incurred by EAC they would be representative in terms of order of magnitude and relative proportions with each other. Similarly, in the CPP phase, representative values are used for deadheadings as well as layover costs. The number of deadheadings and layovers are based on the number of people in the crew, e.g. a layover of a crew of two people counts as two layovers. All the computational experiments are carried out on a 64-bit Windows Server with two 2.4 GHz Intel Xeon CPU’s and 24 GB RAM. The algorithms are implemented using C$++$, and CPLEX Concert Technology.

As the computational study is carried out on the publicly available data of EAC, we do not have a real-life benchmark to compare our solutions with. To serve as a basis of comparison, we first generate solutions using our methods to solve FP and CPP sequentially. These serve as benchmarks in evaluating our integrated solutions. We also compare our results from different integrated methods in terms of solution quality and computational time.

In Table 1, we present the benchmark results, which is obtained by solving the FP and CPP phases sequentially for instances 1 through 5. The column “FP” presents the profits of the FP Phase (obtained by solving FP$+$). In reporting these profits, we deduct the cost of covering each leg with the least profitable aircraft, as this is a fixed cost and does not depend on the solution. “CPP” presents the costs of the CPP Phase (obtained by solving LNS1) and “Profit” presents the difference between these two values. Finally, the column “CPU Time” presents solution times. In our experimentation, in the FP stage, we chose the iteration limits, $n_{sub} = 200$, $n_{iter} = 200$. In the CPP stage, we have set $k_{max} = 100$, $s_{max} = 25$, and $\alpha = 0.7$ for LNS1. For the details of these parameters, we refer the reader to Erdogan et al. (2015). Here it is worth noting the big scale difference between FP and CPP. The costs of deadheading and layovers constitute approximately 1 % of the profits in the FP. This is due to the fact that crew related costs, like salaries, are not reflected in the objective function of CPP, due to the nature of the problem in EAC.

Table 1 The profits in the FP phase (in US$), the operating costs in the CPP phase (in US$), and the corresponding CPU times (in seconds) of the sequential solution approach

Table 2 presents the results obtained by iteratively solving the FP and CPP for instances 1 through 5. Here the number of iterations, $n_{it}$, is set to 10, and the number of legs switched to other family, $\beta$, is 30. The columns are similar to those of Table 1 except that we add two columns showing the dollar change in “Profit” and “CPP Cost”, these are denoted by “$\triangle$ Profit” and “$\triangle$ CPP Cost”. Note that negative changes in CPP cost reflect better CPP solutions. By the construction of the mechanism, the solution of the FP phase cannot improve in the iterative solution; we only impose extra restrictions (such as a flight leg cannot be assigned to a particular family), which in turn decrease the profits of the FP phase. However, we also expect the operating costs of the CPP Phase to improve and expect that the improvement will be high enough to compensate the losses in the FP phase with respect to the benchmark solution, and hence the overall profits will be higher. As we observe from Table 2, this is the case for instances 3 and 4. In these two instances, the overall profits increase with a significant reduction of CPP costs over the benchmark solution. Indeed, in all instances there is a significant decrease in CPP costs compared to the CPP costs in the sequential approach, an average of $325,981, corresponding to a 12 % decrease, with the highest decrease being 25 %. However in some instances, the overall profits are lower than our benchmark solutions. In these instances the savings from CPP phase were not sufficient to offset the loses in FP phases. The CPU times are presented in the last column. Even though these values are approximately 10 times that of the sequential solution, given that the planning period of the IFACPP is one month, they are still acceptable.

Table 2 The results, the improvements over the benchmark (in US$) and the CPU times (in seconds) of the iterative solution of FP and CPP

Finally, Table 3 presents the results obtained by simultaneously solving the FP and CPP for instances 1 through 5. As can be observed from Table 3, with the simultaneous solution approach for IFACPP, we obtain better results compared to the benchmark solution for all five instances. The average improvement of the CPP Cost is around $263,271, corresponding to a 10 % decrease in cost, with the highest decrease being 27.45 %. The average overall improvements in profits is 2.4 millions. These results prove that solving FP and CPP in an integrated manner can generate significant benefits over the sequential solution approach. We claim that the results will be more significant for airlines where CPP costs also include crew salaries.

Table 3 The results, the improvements over the benchmark (in US$) and the CPU times (in seconds) of the simultaneous solution of FP and CPP

In order to assess the sensitivity of the algorithms to the algorithm parameters we ran a sensitivity analyses on $n_{sub}$ in the FP chains update procedure, $n_{iter}$ in the FP Iterated Local Search procedure, $n_{it}$ and $\beta$ in the Iterated FP and CPP procedure. For all parameters it was seen that the results converged for large enough iterations. Indeed for $n_{sub}>50$ the result of procedure FAP_LS stayed constant. For $n_{iter}>50$ the change in FP_ILS was less than $0.3\,\%$. For $n_{it}$ the change in profit was less than $0.25\,\%$ and for $\beta$ the change in profit was less than 0.15 %. The progress of the algorithms with respect to different parameter values can be seen in Fig. 2.

Fig. 2

Sensitivity of results with respect to algorithm parameters. a FAP_LS results w.r.t. $n_{sub}$. b FAP_ILS results w.r.t. $n_{iter}$. c Iterated FP and CPP results w.r.t. $n_{it}$. d Iterated FP and CPP results w.r.t. $\beta$

Finally, to better gauge the quality of our solution we compared the profit we obtain for the IFACPP via our solution approach with an upper bound. We implemented an upper bound using a multi-commodity network flow problem formulation for the Fleet Assignment component and ignored the crew pairing cost. We solved an LP relaxation of the multi-commodity network flow problem. Based on this the average deviations from the upper bound for the five instances is 8.1 %. The deviations from the upper bound is as follows for the five instances (Table 4).

6 Conclusion

In this paper, we study the integrated fleet assignment and crew pairing problem and propose both iterative and simultaneous solution approaches to improve the profitability of the airline compared to the traditional sequential approach. Our model completely integrates the FP and CPP, but neglects aircraft maintenance constraints of aircraft routing component. In the case where aircraft maintenance requirements are satisfied due to the structure of the underlying flight network, our model also integrates the routing problem. Indeed, in the addressed case, routine maintenance checks are achieved during the night when a large portion of aircraft are grounded in the Base.

The particular variant of the IFACPP we study in this paper arises in many airlines, in particular in airlines where crews are paid based on a fixed salary. The aperiodicity of the flight schedule, a feature common in many European airlines, requires addressing the monthly problem, which makes the problem size significantly big. We show that by taking into account the network structure, in this case a single base with many point to point flights, we are able to generate good solutions in reasonable time.

Table 4 Deviation from upper bound

Our major contribution is the development of a computationally efficient solution to the monthly integrated problem. We solve the monthly problem with approximately 27,000 flight legs and over 100 destinations using heuristic and exact methods in combination. We perform a computational study on monthly flight schedules of a European Airline using publicly available data and representative revenue and cost figures. Based on the results on five different instances, we observe that our algorithm provides solutions with significant cost savings in CPP Phase and improve the overall profits compared to the sequential approach.