Computers & Operations Research 34 (2007) 2251 – 2265

www.elsevier.com/locate/cor

An integrated aircraft routing, crew scheduling and

flight retiming model
Anne Mercier∗ , François Soumis
École Polytechnique de Montréal and GERAD, C.P. 6079, Succ. Centre-Ville, Montréal, Canada H3C 3A7

Available online 15 November 2005

Abstract
In the integrated aircraft routing, crew scheduling and flight retiming problem, a minimum-cost set of aircraft routes and crew
pairings must be constructed while choosing a departure time for each flight leg within a given time window. Linking constraints
ensure that the same schedule is chosen for both the aircraft routes and the crew pairings, and impose minimum connection times
for crews that depend on aircraft connections and departure times. We propose a compact formulation of the problem and a Benders
decomposition method with a dynamic constraint generation procedure to solve it. Computational experiments performed on test
instances provided by two major airlines show that allowing some flexibility on the departure times within an integrated model
yields significant cost savings while ensuring the feasibility of the resulting aircraft routes and crew pairings.
䉷 2005 Elsevier Ltd. All rights reserved.

Keywords: Aircraft routing; Crew scheduling; Flight retiming; Integrated planning; Time windows; Benders decomposition; Column generation

0. Introduction

Airlines usually use a sequential procedure to plan their operations (see, e.g. [1]). By solving a flight scheduling
problem, they first create a schedule that specifies each flight leg to be flown during a given period and sets departure
and arrival times for each of those legs. Then, the fleet assignment is performed to assign an aircraft type to each flight
leg to maximize anticipated profits while taking into account the number of available aircraft. For each aircraft type, an
aircraft routing problem is then solved to determine the sequence of flight legs to be flown by each individual aircraft
so that each leg is covered exactly once while ensuring appropriate aircraft maintenance. With the aircraft routes on
hand, the airline then builds crew rotations or pairings by solving a crew scheduling problem for each aircraft type.
A pairing is a sequence of duty periods separated by overnight rests, and a duty period is a sequence of flight legs
separated by smaller rest periods, called sits (or connections). The objective of the crew scheduling problem is to
determine a minimum-cost set of pairings so that every flight leg is assigned a qualified crew and every pairing satisfies
the set of applicable work rules. For example, each duty period in a pairing must respect limits on total work time, total
flight time and total number of landings. In the last step of the planning process, pairings are finally combined to form
personalized monthly schedules that are assigned to employees by solving a crew bidding problem or a crew rostering
problem.

∗ Corresponding author.

0305-0548/$ - see front matter 䉷 2005 Elsevier Ltd. All rights reserved.
doi:10.1016/j.cor.2005.09.001
2252 A. Mercier, F. Soumis / Computers & Operations Research 34 (2007) 2251 – 2265

While a sequential procedure greatly simplifies the process, Cordeau et al. [2], Klabjan et al. [3] and Cohn and
Barnhart [4] have shown that integrating the aircraft routing and crew scheduling problems can generate solutions that
are significantly better than those obtained by solving the problems sequentially. Because the minimum connection
time required between two successive flight legs covered by the same crew depends on whether the same aircraft is
used on both legs, aircraft routing decisions have an impact on the set of feasible pairings. Consequently, a sequential
planning procedure is likely to yield suboptimal solutions. A connection that is too short to be made by a crew when
the two associated legs are not flown by the same aircraft is said ot be short. In this paper, we consider an additional
level of integration by adding some flight scheduling decisions to the integrated aircraft routing and crew scheduling
problem. More precisely, the departure time of each flight leg is allowed to deviate slightly from the planned schedule.
Obviously, the same departure time has to be chosen for both the aircraft and the crews, and this complicates the
problem. However, an integrated approach can take advantage of the added schedule flexibility to a greater extent since
the departure times are chosen by taking into account the benefits to both the aircraft routings and the crew pairings.
This would not be possible with a sequential solution process in which modifying the schedule in one step could
have unforeseen consequences on the next step. When only small modifications from the original flight schedule are
considered, it is reasonable to assume that flight demand does not change significantly (see, e.g. [3,5,6]).
Several modeling and solution approaches have been proposed to separately address the aircraft routing and crew
pairing problems. The former problem was studied, among others, by Daskin and Panayotopoulos [7], Feo and Bard
[8], Clarke et al. [9], Gopalan and Talluri [10] and Talluri [11]. Numerous contributions regarding the different variants
of the crew scheduling problem can also be found in the operations research literature. For an overview, the reader
is referred to the recent survey of Barnhart et al. [12]. Issues related to the introduction of maintenance and crew
considerations in the fleet assignment problem were discussed by Clarke et al. [13], Rushmeier and Kontogiorgis [14]
and Barnhart et al. [15]. Finally, other interesting contributions with respect to the integration of the planning process
are the approaches presented by Desaulniers et al. [5] and Barnhart et al. [16] for the combined fleet assignment and
aircraft routing problem.
In recent years, there has been a growing interest in the integration of aircraft routing and crew scheduling problems.
Cordeau et al. [2] have introduced a model that integrates the complete aircraft routing and crew pairing formulations to
which is added one linking constraint for each short connection. To handle these linking constraints, a solution approach
based on Benders decomposition is used. The solution process iterates between a master problem that solves the aircraft
routing problem, and a subproblem that solves the crew pairing problem. Short connections are fixed by the master
problem and the subproblem constructs minimum-cost crew pairings using only the fixed set of short connections.
Because of their particular structure, both of these problems are solved by column generation. On a set of test instances
based on data provided by a Canadian airline, the integrated approach reduced variable crew costs by 9.4% with respect
to the sequential planning process commonly used in practice.
The latter model was further enhanced by Mercier et al. [17] who have introduced a generalized formulation in
which solution robustness is improved by penalizing connections that are likely to introduce delays if they are not
performed by the same aircraft. The authors also show that reversing the order of the solution sequence, i.e., solving
the crew pairing problem in the Benders master problem as opposed to the aircraft routing problem, yields important
improvements over the approach of Cordeau et al. [2]. Most costs in the integrated problem are associated with the
crew pairings and, by reversing the natural solution sequence, the aircraft routing subproblem is mostly transferring
feasibility information to the master problem and very little optimality (or cost) information. This results in a significant
decrease in the number of Benders cuts generated. The identification of Pareto-optimal cuts was also shown to be useful
in further improving the speed of convergence.
Cohn and Barnhart [4] have also proposed an integrated model, but instead of incorporating the aircraft routing
formulation in the model, variables representing complete solutions to the aircraft routing problem are used in an
extended crew pairing model. This obviously reduces the number of constraints, but may lead to a very large number of
additional variables. The authors show that only a subset of the feasible aircraft routing solutions needs to be included in
the model, i.e., one column for each unique and maximal maintenance-feasible short connection set. These columns can
be generated individually and sequentially, in a preprocessing step, by solving a series of aircraft routing problems with
additional constraints and a modified objective function. They also propose to solve the extended crew pairing problem
by a branch-and-price algorithm in which both crew pairing and aircraft routing solutions are generated dynamically.
Klabjan et al. [3] have presented a partially integrated approach that solves the crew pairing problem first, but includes
additional constraints that count the number of available aircraft on the ground at any time. Under the assumption that
 A. Mercier, F. Soumis / Computers & Operations Research 34 (2007) 2251 – 2265 2253

maintenance is performed at night when all aircraft are on the ground, these constraints generally ensure the feasibility
of the resulting maintenance aircraft routing problem. In addition, the model allows the departure time of each flight
leg to be moved within a small time window so as to further reduce crew costs. A rapid depth-first search method
generates a subset of pairings that are based on the original schedule and some modified feasibility parameters. For
example, the minimum connection time is decreased by the time window width to allow pairings that would be feasible
with modified leg departure times. While generating a pairing, if it is impossible to retime the legs in accordance with
the true feasibility parameters, the pairing is rejected. To speed up the algorithm, only one feasible retiming of legs per
pairing is considered. Next, a crew pairing problem with plane count constraints is solved by considering only the valid
generated pairings. Because the time windows can modify the set of ground arcs, it is difficult to model the plane count
constraints exactly and they are thus approximated. On test instances involving up to 450 flight legs, this approach
has produced crew solutions with significantly lower costs then the solutions obtained with the traditional sequential
method. It is, however, less likely to yield a feasible maintenance aircraft routing problem in an international context
where maintenance does not necessarily take place at night.
In the case of the fleet assignment problem, a number of papers have considered the idea of integrating flight scheduling
decisions to increase flexibility and ultimately find better solutions (see, e.g. [5,6,18]). However, we are not aware of
any model for the fully integrated aircraft routing and crew scheduling problem that also includes flight scheduling
decisions. The contributions of this paper are to introduce such a model, to explain how it can be solved efficiently
and to evaluate the benefits that result from the increased flexibility related to the departure times. In particular, we
show that a straightforward extension of the integrated aircraft routing and crew scheduling model proposed by Mercier
et al. [17] yields an intractable formulation, but that a compact reformulation of the problem coupled with dynamic
constraint generation allow the solution of large-scale instances in reasonable computing times.
The remainder of the article is organized as follows. The next section introduces some notation and a mathematical
formulation of the problem while Section 2 presents the solution methodology. Computational experiments that show
the benefits of solving an integrated model including flight retiming are reported in Section 3. Conclusions and directions
for future work are discussed in the final section.

1. Mathematical formulation

In this paper, we assume that the fleet assignment problem has been solved so that the aircraft type assigned to
each flight leg is known. In this context, the integrated aircraft routing, crew scheduling and flight retiming problem
decomposes into one problem for each aircraft type. Given a set of flight legs to be flown by the aircraft of a specific
type, the problem is then to determine a modified schedule and a minimum-cost set of aircraft routes and crew pairings
such that each flight leg is covered by one aircraft and one crew, and side constraints are satisfied.

1.1. Model

Our formulation addresses the daily problem which is common in the crew scheduling literature. Consider a set L
of daily flight legs to be flown by a single aircraft type. Each flight leg i ∈ L is defined by origin and destination
stations, and departure and arrival times. A finite number of possible changes to the original departure time of a leg
is used to model schedule flexibility. Let Ui be the set of possible departure times of leg i ∈ L. For example, if the
original departure time of leg i is 12h00, then Ui = {11h55, 12h00, 12h05} could be a set of possible departure times for
this leg.
Given two flight legs i, j ∈ L, the connection between these legs is said to be short if it is feasible but the difference
between the departure time of leg j and the arrival time of leg i is smaller than the minimum sit time for crews. In this
case, the legs can be covered, in sequence, by the same crew only if both legs are also covered by the same aircraft.
Otherwise, insufficient time is available for the crew to make the connection. Let S be the set of leg pairs for which
the connection between them is short for at least one possible combination of departure times. For each (i, j ) ∈ S,
let Sij be the set of pairs of departure times p ∈ Ui and q ∈ Uj for which the connection between leg i and leg j
is short.
The problem is modeled with a path formulation. Each aircraft route must respect a limit on the total number of days
separating two visits at a maintenance station. Each duty period in a pairing must respect limits on total work time, total
2254 A. Mercier, F. Soumis / Computers & Operations Research 34 (2007) 2251 – 2265

flight time and total number of landings. In addition, the number of duty periods in a pairing must not exceed a certain
limit. These path feasibility constraints are modeled through the use of resources and are handled directly by dynamic
programming in a column generation framework (see, e.g. [19]). The aircraft and the crew paths are generated with
time-space networks. Each node of these networks correspond either to the departure of a flight leg, or to its arrival.
Aircraft networks contain two types of arcs: flight arcs and connection arcs. In the crew networks, each arc represents
either a flight, a deadhead flight, or a feasible connection between two flights, between two deadhead flights or between
one of each. Deadheads permit crew members to travel as passengers on certain flights. They are useful to reposition
crews to a different city where they are needed to cover a flight leg. They can also be used to ensure that the crew can
return to its base at the end of a pairing. For each leg i ∈ L, |Ui | copies of the corresponding flight arc are included
in the networks (one for each possible schedule) and the leg covering constraints will ensure that only one of them is
used per leg.
Let F be the set of feasible aircraft paths and let K denote the set of feasible crew paths. For every path  ∈ F
or  ∈ K , define binary constants b i that take value 1 if leg i ∈ L belongs to this path and binary constants biu that

ijpq
take value 1 if leg i ∈ L is assigned schedule u ∈ Ui in this path. Let also n be equal to 1 if leg i ∈ L with schedule
p ∈ Ui and leg j ∈ L with schedule q ∈ Uj are performed in sequence in path . Let also c be the cost of sending
one unit of flow along path . For every aircraft path  ∈ F , let f be the number of aircraft required to cover path
. The value of f may be greater than one since aircraft paths can span more than one day and every leg has to be
covered daily. Let also  be a binary variable that represents the flow on aircraft path . For every crew path  ∈ K ,
let e be the number of duties in the path. A binary variable  is defined for every crew path , and binary constants
diu take value 1 if leg i ∈ L with schedule u ∈ U is performed as a deadhead in crew path . Finally, constants F and
i
 represent the number of available aircraft and a limit on the total number of duties in all crew pairings, respectively.
D

Table 1 provides a summary of the notation used in the formulation.

The integrated aircraft routing, crew scheduling and flight retiming model, (M1), can be stated as follows:

 
Minimize c  + c  (1)
∈K ∈F

subject to i
b  = 1 (i ∈ L) (2)
∈ F


f  F (3)
∈ F


i
b  = 1 (i ∈ L) (4)
∈ K


e  D (5)
∈K
 
iu
d  − iu
b  0 (i ∈ L, u ∈ Ui ) (6)
∈ K
∈ K

 
iu
b  − iu
b  = 0 (i ∈ L, u ∈ Ui ) (7)
∈ K
∈ F

 ijpq
 ijpq
n  − n  0 ((i, j ) ∈ S, (p, q) ∈ Sij ) (8)
∈ K
∈ F

 ∈ {0, 1} ( ∈ F ) (9)

 ∈ {0, 1} ( ∈  ). K
(10)
 A. Mercier, F. Soumis / Computers & Operations Research 34 (2007) 2251 – 2265 2255

Table 1
Summary of notation

L Set of legs
Ui Set of possible departure times for leg i
S Set of pairs of legs for which the connection between them is short for at least one schedule combination
Sij Set of pairs of departure times p ∈ Ui and q ∈ Uj for which the connection between leg i and leg j is short
F Set of feasible aircraft paths
K Set of feasible crew paths

 Binary variable representing the flow on crew path 

 Binary variable representing the flow on aircraft path 

i
b Equal to 1 if leg i belongs to path 
iu
b Equal to 1 if leg i with schedule u belongs to path 
c Cost of sending one unit of flow along path 
diu Equal to 1 if deadhead i with schedule u belongs to path 
e Number of duties in crew path 
f Number of aircraft required to cover aircraft path 
ij
n Equal to 1 if leg i and leg j are performed in sequence in path 
ijpq
n Equal to 1 if leg i with schedule p and leg j with schedule q are
performed in sequence in path
F Number of available aircraft
D Total number of duties allowed in all crew pairings

The objective function (1) minimizes the sum of all crew scheduling and aircraft routing costs. An approximate crew
cost function including piecewise linear waiting costs and deadhead costs is used. Because each flight leg must be
covered by exactly one crew, a large portion of total crew costs is fixed. Hence, the only relevant costs considered
in these experiments are those that can be reduced by a better planning of crew pairings. Variable expenses are
incurred for connections whose duration exceeds a given threshold because crews must then be credited work time
even though they are not actually working. Additional accommodation expenses are also incurred when the rest period
between successive duties does not take place at the crewbase. For the aircraft routing problem, airlines sometimes
take into consideration through values that represent the extra revenues obtained by assigning the same aircraft to
a pair of consecutive flight legs (i.e., a through) so that passengers flying from the origin of the first leg to the
destination of the second leg do not have to change aircraft. Constraints (2) and (4) require each leg to be covered
by exactly one aircraft and one crew, respectively. Constraint (3) imposes a limit on the number of available aircraft
and constraint (5) limits the total number of duties worked. By restricting the number of duties worked, one can
increase their duration and make unattractive short duties which would incur charges for the airline. The minimum
paid flying time for crews is not included in our approximate crew cost function but sensitivity analysis showed that
it is properly replaced by (5). Constraints (6) ensure that the same schedule is chosen for the working crew and the
traveling crew (deadhead), if any. Similarly, constraints (7) ensure that, for every leg, the same schedule is chosen
for the aircraft and the crew. Finally, constraints (8) guarantee that a crew does not change aircraft if, for the chosen
schedule, the connection time is too short. These last two groups of constraints ((7) and (8)) link the aircraft and the
crew problems.

1.2. A simpler formulation

Model (M1) contains a large number of short connection linking constraints (8) which make the problem hard to
solve. Indeed, there are potentially |Ui | · |Uj | constraints of this type for each leg pair (i, j ) ∈ S since the connecting
flight legs can each have many possible departure times. One can reduce the number of such constraints by aggregating
them so as to keep only one linking constraint per short connection. In fact, by constraints (2), (4), (9) and (10), only
one departure time is chosen for every flight leg in the aircraft paths and only one departure time is chosen for every
flight leg in the crew paths. In addition, by constraints (7), every leg is associated with the same departure time in both
2256 A. Mercier, F. Soumis / Computers & Operations Research 34 (2007) 2251 – 2265

Fig. 1. Example of some violated unaggregated constraints.

the crew and the aircraft paths. Therefore, the same combination of departure times is chosen for two given connecting
flight legs in both the crew and the aircraft paths. This implies that the path variables can take a non-zero value in
only one of the unaggregated linking constraints (8) related to a given short connection. These constraints can thus be
rewritten as

 ij
 ij
n  − n  0 ((i, j ) ∈ S). (11)
∈K ∈F

Although the integer aggregated model, (M2), obtained by replacing (8) with (11) is equivalent to the original formu-
lation, its linear relaxation does not prevent the model to choose for crews fractions of short connections that are taken
by aircraft, but with different schedules. The aggregated formulation could therefore lead to a larger integrality gap or
introduce a greater number of fractional variables in the LP solution. The detailed short connection linking constraints
(8) impose that the flow on each short connection arc in the crew networks be smaller than or equal to the flow on
the corresponding arc in the aircraft networks. In contrast, the aggregated formulation only requires that the sum of
the flows on all arcs corresponding to a given short connection (for all schedule combinations) be smaller or equal in the
crew networks. Fig. 1 shows an example where a solution to the linear relaxation of the aggregated model violates some
of the unaggregated constraints (8). For ease of exposition, this example only considers two possible departure times
for two connecting flight legs where the connection between leg A and leg B is short for all four possible schedule
combinations.
One can see in Fig. 1 that two detailed constraints are violated with this solution. For instance, 0.2 crew makes the
short connection between [Leg A—Schedule 1] and [Leg B—Schedule 1] while no aircraft makes the same connection.
Nevertheless, one can easily observe that the MIP obtained by relaxing integrality on either crew or aircraft variables
in (M2) is equivalent to (M1). If the aircraft variables, for example, are not restricted to take integer values, the flow on
the leg arcs would still be integer because of constraints (7), which restrict the flow on the aircraft arcs to be equal to
the flow on the crew arcs. Consequently, as in the integer formulation of (M2), only one possible schedule combination
can be taken between two flight legs.
 A. Mercier, F. Soumis / Computers & Operations Research 34 (2007) 2251 – 2265 2257

2. Solution methodology

2.1. Benders decomposition

The model includes both crew pairing and aircraft routing path variables. Benders decomposition (see [20]) can be
used to reformulate the problem to separate the two types of variables at the expense of an increase in the number of
constraints.
Let  be the set of solutions (paths) satisfying the crew constraints (4), (5), (6) and (10). For given integer values
¯  ( ∈ K ) ∈ , the MIP relaxation of the aggregated model (obtained by relaxing integrity on variables  in (M2))
reduces to the following primal subproblem involving only aircraft variables:


Minimize c  (12)
∈F

subject to i
b  = 1 (i ∈ L) (13)
∈ F


f  F (14)
∈ F

 
iu
b   iu
b ¯  (i ∈ L, u ∈ Ui ) (15)
∈ F
∈ K

 ij
 ij
n   n ¯  ((i, j ) ∈ S) (16)
∈ F
∈ K

 0 ( ∈ F ). (17)

One can notice that the set of equalities (7) has been replaced with inequalities (15) in the subproblem. This form is
equivalent but easier to solve because it reduces the feasible set of the dual.
Let  = (i | i ∈ L),  0,  = ( iu 0 | i ∈ L, u ∈ Ui ) and μ = (
ij 0 | (i, j ) ∈ S) be the dual variables associated
with constraints (13)–(16), respectively. The dual of (12)–(17) is the following dual subproblem:

      ij
Maximize i + F  + iu
b ¯  iu + n ¯ 
ij (18)
i∈L i∈L u∈Ui ∈ K (i,j )∈S ∈
K

    ij
subject to i
b i + f  + iu
b iu + n
ij c ( ∈ F ) (19)
i∈L i∈L u∈Ui (i,j )∈S

 0 (20)

iu 0 (i ∈ L, u ∈ Ui ) (21)

ij 0 ((i, j ) ∈ S). (22)

Assuming that c 0 for all  ∈ F , the dual subproblem is always feasible since the null vector 0 satisfies constraints
(19)–(22). Furthermore, if it is also bounded, it makes the primal subproblem feasible and bounded as well. Let 
denote the polyhedron defined by constraints (19)–(22), and let P and R be the sets of extreme points and extreme
rays of , respectively. One can see that  does not depend on the crew problem since the crew elements ¯  are present
only in the objective function (18). P and R could then be enumerated a priori.
2258 A. Mercier, F. Soumis / Computers & Operations Research 34 (2007) 2251 – 2265

Introducing the additional free variable z0 , the MIP relaxation of (M2) can thus be reformulated as the following
Benders master problem:

Minimize c  + z0 (23)
∈K
     ij
subject to z0 − iu
b iu  − n
ij 
i∈L u∈Ui ∈K (i,j )∈S ∈K

 i +  F  ((, , μ, ) ∈ P ) (24)
i∈L
     ij
− iu
b iu  − n
ij 
i∈L u∈Ui ∈K (i,j )∈S ∈K

 i +  F  ((, , μ, ) ∈ R ) (25)
i∈L

i
b  = 1 (i ∈ L) (26)
∈ K


e  D (27)
∈K
 
iu
d  − iu
b  0 (i ∈ L, u ∈ Ui ) (28)
∈ K
∈ K

 ∈ {0, 1} ( ∈ K ). (29)

Feasibility constraints (25) ensure that the values given to the crew variables  ( ∈ K ) lead to a bounded dual
subproblem. When bounded, the purpose of the dual subproblem is to evaluate the aircraft routing problem for a
specific set of short connections and a specific schedule for every leg. The value of z0 is thus restricted to be larger
than or equal to the optimal value of the dual subproblem by optimality constraints (24). Since the Benders cuts are
generated from the polyhedron of the dual subproblem, integrality on the primal subproblem variables has to be relaxed.
However, an algorithm in three phases ensuring that an integer solution to the problem is obtained is described in the
next section.
In general, model (23)–(29) contains more constraints than the MIP relaxation of (M2) but most optimality and
feasibility cuts are inactive in an optimal solution. Hence, these constraints need not be enumerated exhaustively but
can instead be generated dynamically by iterating between a relaxed master problem and the subproblem. The relaxed
master problem contains constraints (26)–(29) as well as subsets of Benders cuts (24) and (25). The optimal solution
of the relaxed Benders master problem is used to set up constraints (15) and (16) in the primal subproblem at every
iteration. If the primal subproblem is feasible, the value of the dual variables associated with constraints (13)–(16)
determine an extreme point of P . Otherwise, an extreme ray of R violating one of the constraints (25) is identified.
When through values are not considered, as it is often the case in the literature (see, e.g., [21]), the aircraft routing
problem reduces to a feasibility problem and optimality cuts become irrelevant. Hence, exactly one feasibility cut is
added to the relaxed Benders master problem at each iteration and the process continues until its optimal solution yields
a feasible primal subproblem.

2.1.1. Three-phase algorithm

Mercier et al. [17] have described a heuristic solution method in which both the crew pairing master problem and
the aircraft routing subproblem are solved by column generation. The method works in three phases. In Phase I, all
integrality requirements are relaxed and the relaxation is solved to optimality by Benders decomposition and column
generation. Retaining all generated cuts, Phase II reintroduces integrality constraints on the master problem crew
 A. Mercier, F. Soumis / Computers & Operations Research 34 (2007) 2251 – 2265 2259

Fig. 2. Algorithmic flowchart.

variables and solves the resulting mixed-integer problem by generating additional cuts. In this phase, the integer master
problem must be solved at each iteration of the Benders decomposition algorithm. In Phase III, integrality constraints
are finally added on the subproblem aircraft variables and the integer subproblem is solved once with the values of the
master problem variables being held fixed. Because linking constraints in the primal subproblem force the aircraft to
use the short connections selected for crews in the master problem, the integer primal subproblem may be infeasible in
Phase III for the given solution of the master problem, even if the original problem is feasible. A step is therefore added
after the third phase to verify the feasibility of the integer subproblem and, if needed, go back to the second phase to
2260 A. Mercier, F. Soumis / Computers & Operations Research 34 (2007) 2251 – 2265

solve the integer master problem with an additional constraint forbidding the same subset of short connections to be
chosen. To obtain integer solutions in the master problem and in the subproblem, a heuristic branching strategy is used.
Branching is performed on the path variables and decisions can be made simultaneously on more than one variable to
accelerate the search.

2.1.2. Dynamic constraint generation

Due to the increased number of constraints and variables in the model to include possible schedule changes, the
algorithm developed by Mercier et al. [17] does not succeed in solving the model efficiently. In fact, the computational
experiments presented in Section 3 show that the straightforward extension of the method does not converge within 36 h
of computing time for the larger instances, even when the aggregated model is used. The integrated model including
flight retiming is thus solved with a modified version of the three-phase approach. The new approach includes a dynamic
constraint generation procedure.
The large number of deadhead coordination constraints (6) in the model contributes to the inefficiency of the solution
method, but without deadhead flights, the majority of the instances would either become infeasible or the crew costs
would increase significantly. However, since the proportion of potential deadhead flights actually used in the solutions
is small, constraints (6) can be generated dynamically to reduce the computational effort required to solve the Benders
master problem. When this approach is used, all constraints (6) are relaxed in the master problem at the beginning
of Phase I and, after each iteration of the Benders decomposition algorithm, all violated constraints are added to the
master problem. Recall that the purpose of the Benders subproblem is only to evaluate the aircraft routing problem (or
verify its feasibility) for a specific set of short connections and a specific schedule for every leg. The subproblem thus
generates valid Benders cuts even if a relaxation of the master problem is used to supply crew pairings and potential
schedules.
When the aggregated model is used, the algorithm can also add, throughout Phase I, the violated detailed short
connection linking constraints (8) to the model in an effort to improve the LP solution value. Adding constraints in the
primal subproblem during the solution process does not affect the validity of the previously generated Benders cuts.
Indeed, restricting the primal subproblem relaxes the dual subproblem. As a result, Benders cuts added in previous
iterations were generated from possibly interior points (rays) of the dual, but nonetheless feasible dual points (rays)
of the complete model. In other words, the missing dual values (associated with the detailed linking constraints) were
assumed to be 0 in the previous iterations. Recall that this step is not needed in Phase II since the MIP relaxation of
(M2) is not a relaxation of the integer formulation of (M1) because of constraints (7).
Fig. 2 gives the complete algorithmic flowchart of the proposed solution method.

3. Computational experiments

In this section, we present computational experiments that were carried out on a set of seven instances based on data
provided by two major airlines. Three possible departure times for every leg, 5 min apart, were used to test the flight
retiming aspect and make comparisons with the model in which the schedule is fixed. These modifications from the
original flight schedule are considered small enough not to change flight demand.

3.1. Description of data sets

The test instances come from daily fleet assignment solutions provided by the airlines. Some characteristics of the
different instances are given in Table 2. This table indicates, for each instance, the number of daily legs and the total
number of possible short connections (|S|). In column |S  |, we indicate the number of connections that are short for at
least one combination of departure times when small retimings are considered (±5 min). The percentage increase in
the number of possible short connections with the retimings is given in the last column of the table.
One can see from Table 2 that the flight retiming model contains, on average, 58.4% more possible short connections
than the model with fixed departure times. Small schedule modifications can thus have a strong impact on the number
of pairings satisfying all the work rules and on the number of maintenance-feasible aircraft routes. Allowing new paths
that would otherwise be infeasible can significantly reduce crew costs while reducing the number of necessary aircraft.
 A. Mercier, F. Soumis / Computers & Operations Research 34 (2007) 2251 – 2265 2261

Table 2
Characteristics of test instances
Instance Legs |S| |S  | Increase (%)

D95A 198 87 127 46.0

B757A 184 114 151 32.5
B767R 152 83 168 102.4
A320D 258 182 272 49.5
D9SA 523 502 725 44.4
D9SB 508 659 961 45.8
B767S 510 370 697 88.4

Average 58.4

3.2. Summary of computational experiments

To evaluate the efficiency of the three-phase algorithm on the integrated model with flight retiming, we first tried to
solve the model where all the detailed short connection linking constraints and all the deadhead schedule coordination
constraints are included from the start (model (M1)). For more than half of the instances, this straightforward extension
could not find a solution even after 36 h of computing time. To improve the efficiency of the algorithm, we tried to
solve the compact aggregated model, first with all the deadhead coordination constraints (model (M2)), and then with
the latter constraints generated dynamically (model (M2a)). Finally, we tried solving the compact model with the
deadhead coordination constraints generated dynamically again but also with the violated detailed short connection
linking constraints generated as needed throughout Phase I (model (M2b)). Our algorithms were coded in C++ and
use GENCOL1 for column generation. All experiments were performed on a Pentium 4, 2 GHz computer, using a
single processor.
Table 3 presents a comparison of the CPU time and computational effort needed to perform all three phases with the
different approaches. We indicate, for the four approaches and all seven instances, the time spent in each of the three
phases as well as the number of cuts generated in the first two phases and the number of forbidden short connection
subset cuts added after Phase II to get a feasible integer subproblem (SPIP Cuts). We also indicate, when appropriate,
the total number of deadhead schedule coordination constraints added (DH Cuts) and the total number of detailed short
connection linking constraints added (SCLC Cuts). Cost IP indicates the cost of the integer integrated solution at the
end of Phase III. Since the branch-and-bound strategy is heuristic, the optimality of the solution is not guaranteed.
The master problem also includes an integrality gap. The reported gap is therefore the maximum optimality gap and is
computed as the percentage difference between Cost IP and Cost LP. Finally, the CPU time efficiency of the methods
are compared. For example, CPU ratio vs M1 reported for (M2a) is the total CPU time of (M1) divided by the total
CPU time of (M2a).
When considering Phase I CPU times, one observes that the approach using the compact aggregated formulation
(M2) always produced an LP solution faster than the one using the unaggregated model (M1). In addition, the LP value
does not deteriorate with the aggregated model. Although the number of linking constraints is greatly reduced in the
aggregated Benders subproblem, the improvements are mainly attributed to a decrease in the number of Benders cuts
generated and not to the improved solution time of the subproblem itself. It thus seems that the aggregated subproblem
generates stronger Benders cuts than the unaggregated one. While this may be surprising, it can be explained by the
fact that the aggregated model has a smaller dual feasible region which helps to generate stronger cuts. The comparison
of the time spent in finding an integer solution can be misleading because of the heuristic branch-and-bound method.
For all instances, (M2) nevertheless solved the integer problem faster than (M1), by a factor of at least 5.10, on average,
and an additional instance could be solved within the time limit. This CPU decrease is in fact underestimating the real
ratio of decrease since (M1) was sometimes stopped before getting a solution.
Putting the deadhead schedule coordination constraints in the crew master problem only when they are violated (model
(M2a)) further improves the performance of the three-phase algorithm. This refinement can decrease the average total

1 GENCOL is an optimization software that was developed at GERAD in Montreal.

2262 A. Mercier, F. Soumis / Computers & Operations Research 34 (2007) 2251 – 2265

Table 3
Complete results: integrated problem with flight retiminga

D95A B757C B767R A320D D9SA D9SB B767S Average

Cost LP 20,626 47,821 37,492 80,272 66,840 80,229 172,728

M1
CPU Ph.I > 36 h 41.51 87.40 153.49 > 36 h > 36 h > 36 h
CPU Ph.II 19.44 7.26 8.80
CPU Ph.III 34.34 20.72 1.85
CPU Total > 36 h 95.29 115.38 164.14 > 36 h > 36 h > 36 h
Cuts Ph.I 68 69 78
Cuts Ph.II 6 0 0
SPIP Cuts 2 2 0
Cost IP 48,973 37,543 80,848
Gap 2.35% 0.14% 1.93% 1.47%

M2
CPU Ph.I 158.80 27.81 9.25 46.62 > 36 h > 36 h > 36 h
CPU Ph.II 17.08 27.05 2.68 29.42
CPU Ph.III 0.17 3.65 14.58 0.32
CPU Total 176.05 58.51 26.51 76.36 > 36 h > 36 h > 36 h
Cuts Ph.I 95 34 3 31
Cuts Ph.II 2 12 0 4
SPIP Cuts 0 1 0 0
Cost IP 20,748 48,520 37,543 81,828
Gap 0.59% 1.44% 0.14% 1.90% 1.02%
CPU ratio vs M1 > 12.27 1.63 4.35 2.15 > 5.10

M2a
CPU Ph.I 32.30 8.75 10.61 14.64 316.63 272.10 58.01
CPU Ph.II 9.98 3.79 1.44 7.51 12.89 181.67 > 36 h
CPU Ph.III 0.14 2.97 14.63 1.17 32.08 868.93
CPU Total 42.42 15.51 26.68 23.32 361.60 1322.70 > 36 h
Cuts Ph.I 17 8 6 11 16 9 4
Cuts Ph.II 2 1 0 1 0 3 >3
SPIP Cuts 0 0 0 0 0 1
DH cuts 0 7 3 10 0 2
Cost IP 20,688 48,348 37,543 80,407 67,405 81,123
Gap 0.30% 1.09% 0.14% 0.17% 0.84% 1.10% 0.61%
CPU ratio vs M2 4.15 3.77 0.99 3.27 > 5.97 > 1.63 > 3.30

M2b
CPU Ph.I 29.83 7.61 12.17 13.19 436.09 269.90 37.26
CPU Ph.II 10.32 0.99 1.27 1.78 21.74 364.99 671.12
CPU Ph.III 0.44 2.28 5.90 4.18 43.00 711.63 211.34
CPU Total 40.59 10.88 19.34 19.15 500.83 1346.52 919.72
Cuts Ph.I 18 12 6 6 20 9 3
Cuts Ph.II 2 0 0 0 0 5 0
SPIP Cuts 0 0 0 0 0 1 0
SCLC cuts 9 7 8 11 2 24 28
Cost IP 20,748 48,112 37,555 80,388 66,845 81,157 176,975
Gap 0.59% 0.60% 0.17% 0.14% 0.01% 1.14% 2.40% 0.72%
CPU ratio vs M2a 1.05 1.43 1.38 1.22 0.72 0.98 > 2.35 > 1.34
CPU ratio vs M1 > 53.22 8.76 5.97 8.57 > 4.31 > 1.60 > 2.35 > 12.11
a All CPU times are in minutes.
 A. Mercier, F. Soumis / Computers & Operations Research 34 (2007) 2251 – 2265 2263

CPU time by another factor of at least 3.30 when compared to the basic aggregated model (M2) and two additional
instances could be solved. In addition to reducing the solution time of the crew pairing problem, the numerical results
show that this relaxation of the Benders master problem also has the effect of reducing the number of iterations of the
Benders decomposition algorithm.
Furthermore, the dynamic generation of the violated detailed short connection linking constraints in the course of
Phase I (model (M2b)) can also decrease the average total CPU time. This refinement is essential to be able to solve all
the larger instances. Recall that the LP values of (M2) are equal to the LP values of (M1) on these instances. Therefore,
adding the detailed short connection linking constraints cannot improve the LP values, but it can still speed up Phase
II since restoring integrality on the crew path variables in this phase implies the satisfaction of the detailed linking
constraints in the subproblem, on account of constraints (7). Indeed, one can observe that the number of generated
Benders cuts in Phase II of (M2b) is always lower than or equal to the number generated with (M2a), except for instance
D9SB. For instance D9SB, some variability may have come from the generation of an SPIP cut to get a feasible integer
subproblem. Yet, it is worth noting that the number of Benders cut generated in the first run of Phase II (before the
SPIP cut) was again lower with (M2b). When this approach is compared to the straightforward extension (model (M1)),
the total CPU time is decreased, on average, by a factor of more than 12. One can finally notice that the performance
improvements do not come at the price of lower solution quality. When comparing (M2b) to any other method, if the
average maximum optimality gap is computed only on the instances solvable with the two methods, the gap is always
lower when using (M2b).
It is worth noting that we also tried to generate Pareto-optimal Benders cuts (see, e.g., [22]) but the time needed to
solve the auxiliary problem used to generate non-dominated cuts was always greater than the time saved by having a
reduced number of iterations of the Benders decomposition procedure.
To evaluate the benefits of having some flexibility in the schedule, the results of (M2b) (the most efficient approach)
were compared with the results obtained when solving the integrated model with a fixed schedule (model (M0)).
Table 4 compares the computational effort needed as well as the quality of the solutions obtained (in terms of costs).
We indicate for both approaches the time spent in each of the three phases as well as the number of cuts generated in the
first two phases and the number of forbidden short connection subset cuts added after Phase II to get a feasible integer
subproblem (SPIP Cuts). Cost LP indicates the cost of the solution found at the end of Phase I and Cost IP indicates
the cost of the integer solution at the end of Phase III. The maximum optimality gap reported is computed with respect
to the corresponding LP value. The quality of the solutions are compared by means of the LP cost percentage decrease
(Cost LP % dec.), the IP cost percentage decrease (Cost IP % dec.) and the reduction in the number of aircraft needed
(Aircraft nb. dec.). Finally, the CPU times used by the methods are compared (CPU ratio vs M0).
These results show that for all instances, the model with flight retiming produced an integer solution of lower cost
and with a smaller number of aircraft than the solution produced by the model with fixed departure times. Crew costs,
which include waiting costs and deadhead costs, are decreased, on average, by 8.30% when the departure time of the
flights can be moved forward or backward by just 5 min. Since these crew costs account, on average, for about 20% of
total crew costs (which include a large fixed cost for the actual flight time), the integrated model with flight retiming
can reduce the total crew costs by an average of 1.60% in our instances. At the same time, with these small schedule
modifications, the number of aircraft needed to respect the maintenance requirements can be reduced, on average, by
almost 2. One can notice that the instances for which the crew costs are decreased by a smaller percentage are also the
instances for which the number of aircraft was reduced more. Globally, these small schedule modifications can thus
significantly reduce airline costs. Of course, the CPU ratios show that the integrated problem with flight retiming is
much harder to solve, but the times can still be considered reasonable for tactical planning.
Finally, it is worth mentioning that the benefits displayed in the above table are solely attributable to the intro-
duction of flight retiming in the integrated aircraft routing and crew scheduling problem. One could be interested in
comparing the results from the integrated aircraft routing, crew scheduling and flight retiming problem with a se-
quential procedure also incorporating flight retiming. On the one hand, it can be observed that the number of Benders
feasibility cuts is always positive in Phase I of (M2b). A sequential procedure with flight retiming that solves the
crew pairing problem first would thus always lead to an infeasible aircraft routing problem. On the other hand, if
the aircraft routing problem was solved first, the flight scheduling decisions would be made on a feasibility prob-
lem and not with the objective of minimizing crew costs. As a result, the cost decrease would not be as important.
Finally, all benefits attributable to the integration of aircraft routing and crew scheduling (see e.g., [2–4]) would be
left out.
2264 A. Mercier, F. Soumis / Computers & Operations Research 34 (2007) 2251 – 2265

Table 4
Computational effort and solution quality: with and without flight retiminga

D95A B757C B767R A320D D9SA D9SB B767S Average

M0
CPU Ph.I 0.52 0.47 0.23 1.03 5.38 7.72 2.33
CPU Ph.II 0.23 3.29 0.12 0.73 0.14 16.59 2.92
CPU Ph.III 0.02 0.35 0.23 0.01 1.83 25.07 3.00
CPU Total 0.77 4.11 0.58 1.77 7.35 49.38 8.25
Cuts Ph.I 11 14 0 20 9 11 4
Cuts Ph.II 0 2 0 1 0 2 0
SPIP Cuts 0 1 0 0 0 3 0
Cost LP 25,036 49,355 39,690 83,057 80,480 85,481 177,676
Cost IP 25,403 50,420 40,638 83,367 80,480 86,317 178,980
Gap 1.44% 2.11% 2.33% 0.37% 0.00% 0.97% 0.73% 1.14%

M2b
CPU Ph.I 29.83 7.61 12.17 13.19 436.09 269.90 37.26
CPU Ph.II 10.32 0.99 1.27 1.78 21.74 364.99 671.12
CPU Ph.III 0.44 2.28 5.90 4.18 43.00 711.63 211.34
CPU Total 40.59 10.88 19.34 19.15 500.83 1346.52 919.72
Cuts Ph.I 18 12 6 6 20 9 3
Cuts Ph.II 2 0 0 0 0 5 0
SPIP Cuts 0 0 0 0 0 1 0
Cost LP 20,626 47,821 37,492 80,272 66,840 80,229 172,728
Cost IP 20,748 48,112 37,555 80,388 66,845 81,157 176,975
Gap 0.59% 0.60% 0.17% 0.14% 0.01% 1.14% 2.40% 0.72%
Cost LP % dec. 17.61% 3.11% 5.54% 3.35% 16.95% 6.14% 2.78% 7.93%
Cost IP % dec. 18.32% 4.58% 7.59% 3.57% 16.94% 5.98% 1.12% 8.30%
Aircraft nb. dec. 1 2 1 4 1 2 2 1.83
CPU ratio vs M0 52.71 2.65 33.34 10.82 68.14 27.27 111.48 43.77
a All CPU times are in minutes.

4. Conclusion

This paper has introduced a model and a solution methodology for the integrated aircraft routing, crew scheduling
and flight retiming problem. The methodology combines Benders decomposition, column generation and a dynamic
constraint generation procedure. On test instances containing up to 500 daily legs, the approach yields solutions that
significantly decrease crew costs while also reducing the number of aircraft and still ensuring appropriate aircraft
maintenance. This would not be possible with a sequential solution process. When compared to a straightforward
extension of the solution methodology previously developed by Mercier et al. [17], by aggregating some of the short
connection linking constraints in the Benders subproblem and by generating some other constraints dynamically, the
new approach decreases by a factor of more than 12, on average, the time needed to solve the integrated model with
flight retiming without deteriorating the solution quality.

Acknowledgements

This work was supported by the Québec Government (Fonds pour la Formation de Chercheurs et l’Aide à la
Recherche), and the Natural Sciences and Engineering Research Council of Canada. This support is gratefully acknowl-
edged. Thanks are also due to AD OPT Technologies for providing the data used in the computational experiments.

References

[1] Yu G, editor. Operations research in the airline industry. Boston: Kluwer; 1998.
[2] Cordeau J-F, Stojković G, Soumis F, Desrosiers J. Benders decomposition for simultaneous aircraft routing and crew scheduling. Transportation
Science 2001;35:375–88.
 A. Mercier, F. Soumis / Computers & Operations Research 34 (2007) 2251 – 2265 2265

[3] Klabjan D, Johnson EL, Nemhauser GL. Airline crew scheduling with time windows and plane count constraints. Transportation Science
2002;36:337–48.
[4] Cohn AM, Barnhart C. Improving crew scheduling by incorporating key maintenance routing decisions. Operations Research 2003;51:
387–96.
[5] Desaulniers G, Desrosiers J, Dumas Y, Solomon MM, Soumis F. Daily aircraft routing and scheduling. Management Science 1997;43:841–55.
[6] Rexing B, Barnhart C, Kniker T. Airline fleet assignment with time windows. Transportation Science 2000;34:1–20.
[7] Daskin MS, Panayotopoulos ND. A Lagrangian relaxation approach to assigning aircraft to routes in hub and spoke networks. Transportation
Science 1989;23:91–9.
[8] Feo TA, Bard JF. Flight scheduling and maintenance base planning. Management Science 1989;35:1415–32.
[9] Clarke LW, Johnson EL, Nemhauser GL, Zhu Z. The aircraft rotation problem. Annals of Operations Research 1997;69:33–46.
[10] Gopalan R, Talluri KT. The aircraft maintenance routing problem. Operations Research 1998;46:260–71.
[11] Talluri KT. The four-day aircraft maintenance routing problem. Transportation Science 1998;32:43–53.
[12] Barnhart C, Cohn AM, Johnson EL, Klabjan D, Nemhauser GL, Vance PH. Airline crew scheduling. In: Hall RW, editor. Handbook of
transportation science. 2nd ed., Boston: Kluwer; 2003. p. 517–60.
[13] Clarke LW, Hane CA, Johnson EL, Nemhauser GL. Maintenance and crew considerations in fleet assignment. Transportation Science
1996;30:249–60.
[14] Rushmeier RA, Kontogiorgis SA. Advances in the optimization of airline fleet assignment. Transportation Science 1997;31:159–69.
[15] Barnhart C, Lu F, Shenoi R. Integrated airline schedule planning. In: Yu G, editor. Operations research in the airline industry. Boston: Kluwer;
1998. p. 384–403.
[16] Barnhart C, Boland NL, Clarke LW, Johnson EL, Nemhauser GL, Shenoi RG. Flight string models for aircraft fleeting and routing. Transportation
Science 1998;32:208–20.
[17] Mercier A, Cordeau J-F, Soumis F. A computational study of Benders decomposition for the integrated aircraft routing and crew scheduling
problem. Computers & Operations Research 2005;32:1451–76.
[18] Levin A. Scheduling and fleet routing models for transportation systems. Transportation Science 1971;5:232–55.
[19] Desaulniers G, Desrosiers J, Ioachim I, Solomon MM, Soumis F, Villeneuve D. A unified framework for deterministic time constrained vehicle
routing and crew scheduling problems. In: Crainic TG, Laporte G, editors. Fleet management and logistics. Boston: Kluwer; 1998. p. 57–93.
[20] Benders JF. Partitioning procedures for solving mixed-variables programming problems. Numerische Mathematik 1962;4:238–52.
[21] Klabjan D. Large-scale models in the airline industry. In: Solomon MM, Desaulniers G, Desrosiers J, editors. Column generation. New York:
Springer; 2005. p. 163–95.
[22] Magnanti TL, Wong RT. Accelerating Benders decomposition: algorithmic enhancement and model selection criteria. Operations Research
1981;29:464–84.