Integrated fleet assignment and aircraft routing based on delay propagation

Abstract

Airlines’ expensive resources, especially aircraft, are to be optimally scheduled to cover flights of timetables. However, the irregular flight, due to bad weather, mechanical fault and so on, is inevitable. Moreover, flight delays become more severe with the rapid development of the air transport industry in China and have huge irregular flight cost. In order to alleviate flight delays impact on the flight plan, we present a double objective multi-commodity network flow model of flight delay propagation-based aircraft scheduling and minimize the total delay propagation and airline operation cost as the optimization objective. Branch-and-price solution and column generation algorithm are used to solve the problem. Computational results obtained by using data from a major domestic airline show that our approach can reduce delay propagation significantly, thus improving on-time performance and robustness of aircraft scheduling, and decreasing the total cost simultaneously.

1 Introduction

The purpose of this paper is helping the airlines draw up its robust aircraft scheduling by taking into account flight delay and propagation. This is a tactical problem when from one week up to a month in advance. Aircraft scheduling, usually including the fleet assignment and aircraft routing, is the core of airline plan. Many scholars have conducted considerable research on it. Barnhart et al [1], Sandhu and Klabjan [2], Haouari et al [3] established the integration model of fleet assignment and aircraft routing. Rexing et al [4], Bélanger et al [5] built the fleet assignment model by setting the time window. Lohatepanont and Barnhart [6] and Sherali et al [7] established the integration model of flight timetable and fleet assignment. Mercier and Soumis [8] established the integration model of aircraft routing and crew rostering. In fact, airline plans are frequently disrupted and incur significant irregular flight costs. A more robust plan can reduce the occurrence rate and impact degree of the disruptions, thereby reducing operation costs. Lan et al [9] formulated aircraft routings as a mixed-integer programming problem with stochastically generated inputs and developed a new approach to minimize the number of passenger misconnections by retiming the departure times of flight legs within a small time window, their approach can reduce delay propagation significantly and improve on-time performance. Mou and Zhang [10] proposed robust aircraft assignment model based on the delay probability, but they only considered the case of one-fleet, and there were no restrictions on the number of the aircraft. Their results showed aircraft utilization rate was significantly lower. Dunbar et al [11] considered the flight delay propagation, and used dynamic column generation algorithm to solve aircraft routing problem. Zhu et al [12] established multi-commodity network flow models of integrated multi-fleet assignment and aircraft routing.

In this paper, we present a double objective multi-commodity network flow model with integrated fleet assignment and aircraft routing. It is an extension for robust aircraft maintenance routing model in literature [9]. One objective is to minimize propagated delay, and the other is to minimize the fleet assignment cost. Adding fleeting decisions results in more feasible strings, and potentially leads to improved solutions with reduced delay propagation. At last, branch-and-bound solution and column generation algorithm are used to solve the problem.

2 Flights connection and delay analysis

2.1 Flights connection

Because each aircraft usually flies a sequence of flight legs (domestic routes in China), which is called flight strings. Delay of one flight leg might propagate along the aircraft route to downstream flight legs and cause further delays and disruptions. If the slack time between two connecting flights and the aircraft routing are reasonable, we can reduce the delays and disruptions.

Figure 1 illustrates robustness of flight scheduling under flight delay and effect of exchange aircraft routing. MCT refers to min connect time between connecting flights by one aircraft. In a given situation, flight leg f ₁ and f ₃, f ₂ and f ₄ are in different aircraft routings respectively, but their aircraft types or family are identical, which means their aircraft routings are exchangeable. Suppose flight leg f ₁ delays in a higher probability. The average delay is in the point of flight leg f ₁′, which is much larger than the slack time between flight leg f ₁ and f ₃, and delay propagation always happens. If the delay of flight leg f ₁ is too long, it will even lead to the cancellation of flight leg f ₃. As a result, the passengers in flight leg f ₃ and other connecting flights are disrupted. Another hypothesis is that flight leg f ₂ almost does not delay. The aircraft routing can be changed when flight leg f ₁’s delay happens and is over the slack, which means connecting flight leg f ₁ with f ₄, and connecting flight leg f ₂ with f ₃. In this case, the robustness of flight plan will be improved, and the flight delay will be reduced without significantly increasing operational costs.

Figure 1

Original aircraft routing and new aircraft routing.

2.2 Flight delay propagation

2.2a Propagated delay: Usually, flight delay is divided into independent delay and propagated delay. The propagated delay occurs when the aircraft to be used for a flight leg is delayed from its prior flight leg. This delay is a function of flight strings. The independent delay occurs for some reasons, such as bad weather, aircraft fault, which are not a function of strings. We also call this delay non-propagated delay. The sum of the two is arrival delay of flight.

Figure 2 shows the departure, arrival and delay of two continuous flight legs. The solid arrows represent the original schedule for two flight legs i and j. The dotted arrows represent the actual departures and arrivals of these flight legs. PAT represents planned arrival time, and AAT represents actual arrival time. PDT represents planned departure time, and ADT represents actual departure time. If PCT _i,j is the planned connection time between flight leg i and flight leg j, Slack _i,j is the slack time of these flight legs. That is

$$ PCT_{i,j} = PDT_{j} - PAT_{i} $$

(1)

$$ Slack_{i,j} = PCT_{i,j} - MCT. $$

(2)

Figure 2

Departures, arrivals and delays of two continuous flight legs.

TDD represents total departure delay, comprised of independent departure delay (IDD) and propagated delay (PD). TAD represents total arrival delay, also comprised of two parts, namely propagated delay (PD) and independent arrival delay (IAD). PD _i,j , the delay propagated from flight leg i to flight leg j, if both legs are flown in one aircraft routing, they can be represented as follows:

$$ PD_{i,j} = \hbox{max} (TAD_{i} - Slack_{i,j} ,0) $$

(3)

$$ TAD_{j} = PD_{i,j} + IAD_{j} . $$

(4)

Both propagated delay and total arrival delay are functions of routing. Thus, while historical values for propagated delay and total arrival delay can be computed for each flight leg in existing routings, no values are available for routings that have not been previously realized. However, because independent arrival delay is not a function of routing, independent arrival delay can be calculated for each flight leg by tracking actual routings of each individual aircraft. The total arrival delays and propagated delays of flight legs in any routing can then be generated, as described below:

• 1. Determine propagated delays for each string of flight legs i, j in the historical data according to the expression (3).

• 2. Determine independent arrival delay of each flight from historical data by the expression (4).

• 3. Determine total arrival delay and propagated delay for each flight leg of any routing, given the independent arrival delay for each flight leg:

• 3a. For the first flight leg i on each string, TAD _i  = IAD _i ;

• 3b. For subsequence flight legs j in the routing, PD _i,j  = max(TAD _i  − Slack _i,j , 0) and TAD _j  = PD _i,j  + IAD _j .

2.2b Delay probability distribution: According to analysis of historical delay data, we can get the result that flight delay approximates lognormal distribution. The lognormal distribution density function of delay propagation is

$$ f(x) = \frac{1}{{(x - \theta )\sigma \sqrt {2\pi } }}e^{{\frac{{(\ln \frac{x - \theta }{m})^{2} }}{{2\sigma^{2} }}}} $$

(5)

σ is shape parameter, θ is location parameter, and m is scale parameter. The distribution parameters can be calculated through existing historical data and the information of new aircraft route by the maximum likelihood estimation method (MLE). That is

$$ \overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{m} = \exp (\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{\mu } ) $$

(6)

$$ \overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{\delta } = \sqrt {\frac{{\sum\nolimits_{i = 1}^{N} {(\ln (x_{i} ) - \overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{\mu } )^{2} } }}{N - 1}} $$

(7)

$$ \overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{\mu } = \frac{{\sum\nolimits_{i = 1}^{N} {\ln (x_{i} )} }}{N}. $$

(8)

In order to simplify the expression, suppose y represents PD _i,j , x represents TAD _i , c represents Slack _i,j . That is

$$ y = \hbox{max} (x - c,0) $$

(9)

x is a probability function that submits to the hypothesis of lognormal distribution. Because c is a constant, which can be obtained from the position parameter. Therefore, y can be written as

$$ y = g(x) = \hbox{max} (x,0) $$

(10)

$$ E(PD_{i,j} ) = E(g(x)) = \int_{ - \infty }^{\infty } {g(x)f(x){\rm d}x = \int_{0}^{\infty } {x\frac{1}{{(x - \theta )\sigma \sqrt {2\pi } }}} } e^{{\frac{{(\ln \frac{x - \theta }{m})^{2} }}{{2\sigma^{2} }}}} {\rm d}x. $$

(11)

Therefore, the expected value of the propagated delay can be written as:

$$ E(y) = \left(1 - \varphi \left(\frac{{\ln (\frac{ - \theta }{m})}}{\sigma }\right)\right)\left(\theta + me^{{\frac{1}{2}\sigma^{2} }} \right) $$

(12)

$$ {\text{and}}\quad \varphi (k) = \int_{ - \infty }^{k} {\frac{{e^{{\frac{{x^{2} }}{2}}} }}{{\sqrt {2\pi } }}} {\rm d}x. $$

(13)

3 Robust aircraft scheduling model based on the propagated delay

3.1 Modeling

First, parameters and variables of the model are as follows:

F::

The set of flight legs: each flight leg (i ∊ F) contains the plan departure time (i.pdepT) and arrival time (i.parrT), actual departure time (i.adepT) and arrival time (i.aarrT), departure airport (i.depA) and arrival airport (i.arrA); F ⁺: The set of flight legs originating at a maintenance station; F ⁻: The set of flight legs terminating at a maintenance station

S::

The set of feasible strings (s ∊ S): S ⁺ _i : the set of strings beginning with flight leg i; S ⁻ _i : the set of strings ending with flight leg i

K::

The set of aircraft types: each aircraft type (k ∊ K) contains the number of seats (k.seat), the maintenance station (k.base) and the number of maintenance station (k.basenum), minimum connection time (k.mct), the operation cost per hour (k.cost), the PD cost per hour (k.pdcost)

pd ^s _i,j ::

The delay propagated from flight leg i to flight leg j when flight leg i and flight leg j are in strings

G ^k::

The set of ground arcs for aircraft type k, which ensures the aircraft flow balance

x ^k _s ::

Binary decision variables, when the string s is selected and executed by aircraft type k, x ^k _s  = 1, otherwise, x ^k _s  = 0

a ^s _i ::

Binary decision variables, when flight leg i is in string s, a ^s _i  = 1, otherwise, a ^s _i  = 0

z ^k− _i,d ::

Ground variables, refers to the number of aircraft type k on the ground before flight leg i departs

z ^k+ _i,d ::

Ground variables, refers to the number of aircraft type k on the ground after flight leg i departs

z ^k− _i,a ::

Ground variables, refers to the number of aircraft type k on the ground before flight leg i arrives

z ^k+ _i,a ::

Ground variables, refers to the number of aircraft type k on the ground after flight leg i arrives

r ^k _s ::

The number of times string s crosses the count time, when aircraft type k is used

c ^k _s ::

The cost of flight string s flown by aircraft type k, which contains operating costs and opportunity costs (such as passenger spill cost)

p ^k _g ::

The number of times ground arcs g ∊ G ^k cross the count time

y ^k _g ::

Ground variables, which are used to count the number of aircraft belonging to type k at maintenance stations

β::

Maximum daily aircraft utilization

μ::

Maximum flight leg number of flight strings

The robust aircraft scheduling model (RASM) is written as follows:

$$ \hbox{min} E(\sum\limits_{k \in K} {\sum\limits_{s \in S} {(\sum\limits_{(i,j) \in s} {pd_{i,j}^{s} } )x_{s}^{k} } } ) $$

(14)

$$ \hbox{min} \sum\limits_{k \in K} {\sum\limits_{s \in S} {c_{s}^{k} x_{s}^{k} } } $$

(15)

$$ \sum\limits_{k \in K} {\sum\limits_{s \in S} {a_{i}^{s} x_{s}^{k} } } = 1\quad \forall i \in F $$

(16)

$$ \sum\limits_{{s \in S_{i}^{ + } }} {x_{s}^{k} } - z_{i,d}^{k - } + z_{i,d}^{k + } = 0\quad \forall i \in F^{ + } ,\forall k \in K $$

(17)

$$ - \sum\limits_{{s \in S_{i}^{ - } }} {x_{s}^{k} } - z_{i,a}^{k - } + z_{i,a}^{k + } = 0\quad \forall i \in F^{ - } ,\forall k \in K $$

(18)

$$ \sum\limits_{s \in S} {r_{s}^{k} x_{s}^{k} + \sum\limits_{g \in G} {p_{g}^{k} y_{g}^{k} } } \le k.num\quad \forall k \in K $$

(19)

$$ y_{g}^{k} \ge 0\quad \forall g \in G,k \in K $$

(20)

$$ x_{s}^{k} \in \left\{ {0,1} \right\}\quad \forall s \in S,k \in K. $$

(21)

The objective function (14) is to minimize the expected total propagated delay of selected strings, and (15) is to minimize the total cost. Constraint (16) is covering constraints that ensure each flight leg is in exactly one string for one aircraft type. Constraints (17) and (18) are flow balance constraints that ensure the numbers of each aircraft type arriving at and departing from a location are equal. Constraint (19) is the count constraints to ensure that the total number of each aircraft type in use at the count line does not exceed the number of aircraft in the fleet. Constraints (20) and (21) force the number of aircraft on the ground to be non-negative and the number of aircraft assigned to a string to be 1 or 0. Because variable y ^k _g is a sum of binary x ^k _s variable, the integrate constraints on the y ^k _g variable can be relaxed.

3.2 Model solution

3.2a Model simplification: As above, the model is the dual objective function in order to obtain the solution, which can be transformed into a single objective programming problem and then solved. First we can calculate the optimal solution C _min of objective function (15) under the constraints of (16)–(21). Supposing the relative proportion in the total cost increase is not more than η in the case of considering expected propagated delay. We can transform the formula (15) into constraints condition as follows:

$$ \sum\limits_{k \in K} {\sum\limits_{s \in S} {c_{s}^{k} x_{s}^{k} } } \le (1 + \eta )C_{\hbox{min} } . $$

(22)

At the same time, the model is a stochastic discrete optimization problem without random variables in the constraints, and objective function (14) that can be written as

$$ \begin{aligned} \hbox{min} E(\sum\limits_{k \in K} {\sum\limits_{s \in S} {(\sum\limits_{(i,j) \in s} {pd_{i,j}^{s} } )x_{s}^{k} } } ) & = \hbox{min} \begin{array}{*{20}c} {} \\ \end{array} \sum\limits_{k \in K} {\sum\limits_{s \in S} {x_{s}^{k} } } \times E\left( {\sum\limits_{(i,j) \in s} {pd_{i,j}^{s} } } \right) \\ & = \hbox{min} \begin{array}{*{20}c} {} \\ \end{array} \sum\limits_{k \in K} {\sum\limits_{s \in S} {(x_{s}^{k} } } \times \sum\limits_{(i,j) \in s} {E[pd_{i,j}^{s} ]} ). \\ \end{aligned} . $$

(23)

The simplified RASM(S-RASM) can be rewritten as

$$ \hbox{min} \sum\limits_{k \in K} {\sum\limits_{s \in S} {(x_{s}^{k} } } \times \sum\limits_{(i,j) \in s} {E[pd_{i,j}^{s} ]} ) $$

(24)

$$ \sum\limits_{k \in K} {\sum\limits_{s \in S} {c_{s}^{k} x_{s}^{k} } } \le (1 + \eta )C_{\hbox{min} } $$

(25)

And constraints (16)–(21)

3.2b Solving the model: E[pd ^s _i,j ] can be computed offline for each pair of successive flight legs i and j using the approach detailed in dissertation [1]. Then, our model is a deterministic mixed-integer linear program problem with a large number of 0–1 variables, and the number of variables is much larger than the number of constraints. It is impractical to enumerate all feasible strings explicitly, so column generation at each node of the branch-and-bound is an ideal solution approach for solving this model. Each column in the column generation approach corresponds to a flight string by an aircraft. Figure 3 reveals the solving steps.

Figure 3

Flow chart of solution.

Specific solving steps are shown as follows:

• 1. Change the dual objective into a single objective function

We can obtain C _min by solving objective function (15) under constraints (16)–(21). Column generation is used to solve the linear programming (LP) relaxation of the RASM problem. Form the restricted master problem (RMP), that is, the RASM LP with only a subset of the variables.

Let π _i be the dual variable associated with constraint (16) for flight leg i, λ ^k _i be the dual variable corresponding to the flow balance constraints (17) and (18) for string s beginning or ending with flight leg i, ɛ ^k be the dual variable corresponding to the count constraint (19). The reduced cost of a string s beginning with flight leg b and ending with flight leg e is

$$ \delta_{s} = c_{s}^{k} - \sum\limits_{i \in F} {a_{i}^{s} } \pi_{i} - \lambda_{b}^{k} + \lambda_{e}^{k} - r_{s}^{k} \varepsilon^{k} . $$

(26)

• 2. Solving the pricing problem of S-RASM

Column generation is also used to solve the linear programming (LP) relaxation of the S-RASM problem. Let $d_{s} = \sum\nolimits_{(i,j) \in s} {E\left[ {pd_{i,j}^{s} } \right]}$ represent the total propagated delay along string s, τ be the dual variable corresponding to constraint (25). Then, the reduced cost of a string s beginning with flight leg b and ending with flight leg e is

$$ \rho_{s} = d_{s} - \sum\limits_{i \in F} {a_{i}^{s} } \pi_{i} - \lambda_{b}^{k} + \lambda_{e}^{k} - r_{s}^{k} \varepsilon^{k} - \tau c_{s}^{k} . $$

(27)

The sub-problem can be formed as follows:

$$ \hbox{min} \rho_{s} $$

(28)

$$ \left\{ {i.arrA = j.depA\& i.parrT + k.mct \le j.pdepT|a_{i}^{s} = a_{j}^{s} = 1\& i < j} \right\},\quad \forall i,j \in F $$

(29)

$$ \sum\limits_{i \in s} {a_{i}^{s} (i.parrT - i.pdepT) \le \beta } ,\quad \forall s \in S $$

(30)

$$ \sum\limits_{i \in F} {a_{i}^{s} x_{s}^{k} \le \mu } ,\quad \forall s \in S,k \in K. $$

(31)

The pricing sub-problem of string-based maintenance routing model can be cast as a constrained shortest path problem in a connection network [1]. For our model, however, the pricing problem cannot be cast as a shortest path problem. The reason is that $d_{s} = \sum\nolimits_{(i,j) \in s} {E\left[ {pd_{i,j}^{s} } \right]}$ cannot be assigned to each connection arc (the arc connecting the arrival of one flight leg with the departure of another flight leg at an airport) because the propagated delay for each pair of flight legs depends on the string to which they belong.

To illustrate that the problem cannot be treated directly as a constrained shortest path problem, we built a space–time network shown as figure 4A, B, C refer to airports, and A and C are maintenance bases. f ₁, f ₂, f ₃, f ₄ refer to flight legs, and c ₁₂, c ₂₃, c ₃₄ refer to flight leg connection arc. Assuming there are two flight strings s ₁: f ₃ − c ₃₄ − f ₄ and s ₂: f ₁ − c ₁₂ − f ₂ − c ₂₃ − f ₃ − c ₃₄ − f ₄.

Figure 4

An example of space–time network.

For flight strings s ₁, if flight f ₃ delays 35 min, as f ₃ is the first flight leg, it means IAD ₃ = TAD ₃ = 35 min. If the slack time Slack ₃₄ = 15, then propagated delay for flight leg f ₄ will be $pd_{34}^{{s_{1} }} = 20$. If flight leg f ₃ and f ₄ belong to flight string s ₂, and the propagated delay $pd_{23}^{{s_{2} }} = 10$ from flight leg f ₂ to f ₃, then the total arrival delay for f ₃ is TAD ₃ = 10 + 35 = 45 minutes. We can obtain the propagated delay $pd_{34}^{{s_{2} }} = 10 + 20 = 30$ min from flight leg f ₃ to f ₄, visibly, $pd_{34}^{{s_{1} }} \ne pd_{34}^{{s_{2} }}$. Thus, we solve the pricing problem approximately without explicitly evaluating the reduced cost for each possible string. We construct a connection network by allocating $\Delta _{s} = - \sum\nolimits_{i \in F} {a_{i}^{s} \pi_{i} - \lambda_{b}^{k} + \lambda_{e}^{k} - r_{s}^{k} \varepsilon^{k} - \tau c_{s}^{k} }$ to the corresponding flight arcs and connection arcs. We then solve shortest path problems for all OD pairs of the network. If all Δ _s  ≥ 0, then no columns have negative reduced cost, because d _s  ≥ 0 by definition. Thus, no columns will be added and the LP problem has been solved to optimality. For each shortest path with negative cost, we add d _s to its reduced costs and if the resulting sum is less than zero (Δ _s  + d _s  < 0), then the corresponding column is added to RMP. The augmented RMP is re-solved and the process repeats until a stopping criterion specifying the maximum number of iterations or the minimum objective function improvement is met.

• 3. Solving IP solution

If the solution is not fractional, the current S-RASM problem is solved. If the solution is fractional, a special branching strategy called “branch on follow-ons” [1] can be used to obtain the integer solution. Because there are multi-fleets in our model, the twice branching may be summarized as follows:

For the first branch, on the left branch, force flight leg i to be assigned to the aircraft type $\hat{k}$. On the right branch, do not allow flight leg i to be assigned to the aircraft type $\hat{k}$. To ensure that flight leg i is not in strings by aircraft type $\hat{k}$, eliminate from the connection network of aircraft type $\hat{k}$ all nodes referring to flight leg i (or assign a big enough positive value to corresponding nodes).

For the second branch, identify a fractional string s ₁ with $0 < x_{{s_{1} }}^{k} < 1$ for each aircraft type k, and select another string s ₂ (one exists) containing flight leg i ₁ in s ₁ but not i ₂ in s ₁. Define S ^k _l (S ^k _l  ⊂ S) as the set of strings assigned to aircraft type k with each string containing flight leg i ₁ followed by flight leg i ₂. On the left branch, force flight leg i ₁ to be followed by flight leg i ₂ with $\sum\nolimits_{{s \in S_{l}^{k} }} {x_{s}^{k} } = 1$. To ensure that the pricing sub-problem generates strings satisfying this rule, eliminate from the connection network of aircraft type k (1) all arcs connecting flight leg i ₁ with any flight leg other than flight leg i ₂, and (2) all arcs connecting flight leg i ₂ with any flight leg other than flight leg i ₁. On the right branch, do not allow flight leg i ₁ to be followed by flight leg i ₂, that is, $\sum\nolimits_{{s \notin S_{l}^{k} }} {x_{s}^{k} } = 1$. To ensure the pricing sub-problem generates only strings satisfying this rule, eliminate from the network of aircraft type k all arcs connecting flight leg i ₁ with flight leg i ₂.

4 Case analysis

Select the data from Zhu et al [12], which has 48 aircraft belonging to five kinds of fleets (aircraft type), flying 252 flight legs between 54 airports daily. Fleet information is shown in table 1, and flight leg information is shown in table 2 (only two flight legs listed).

Table 1 Fleet information.

Table 2 Example of flight leg information.

Maximum daily utilization of aircraft in each fleet is 12 h, which means β = 12. Flight string of each aircraft per day is limited to 8, which means μ = 8. Our solution algorithm was implemented in ILOG OPL Studio on PC (2*CPU PM4, 2.93 GHz, 2 GB RAM).

Calculation results are shown in table 3 to table 6. In table 3, column “Old PD” indicates the propagated delay by the minute in original schedule, column “New PD” indicates the propagated delay by the minute for our RASM solution, column “PD Reduced” and “PD cost Reduced” indicate the reduction of propagated delay by the minute and by the dollar resulting from our new schedule respectively, and column “% of PD reduced” indicates the percentage reduction in propagated delay. On average, the RASM reduces total propagated delay by 40.95% compared with the original schedule used by the airline.

Table 3 Results of propagated delay.

The cost comparison of three cases is summarized in table 4. The first row represents the actual cost by airline operation, the second row represents the cost of integrated model in paper [12], and the third row represents the cost by our RASM. The RASM reduces total cost by 11.75% compared with the original schedule used by the airline, and 9.96% compared with the integrated model in paper [12].

Table 4 Results of propagated delay.

The distributions of propagated delays for both the original schedule and our RASM schedule are summarized in table 5. The notation “(a, b]” indicates that the propagated delay is greater than a minutes and less than or equal to b minutes. As the table shows, the new schedule reduces the number of delayed flight legs for each possible range.

Table 5 Distribution for propagated delay.

The distributions of total arrival delays for both original and new schedule are summarized in table 6.

Table 6 Distribution for total arrival delay and on-time performance.

5 Conclusions

In this paper, taking into account the influence of flight propagated delay, we establish a multi-objective integrated model of fleet assignment and aircraft routing. Then the model is converted into single-objective function by transforming the secondary objectives into constraints. An algorithmic solution is presented based on column generation and branch-and-price. Computational results obtained using data from the fourth-largest airline show that our approach can reduce delay propagation significantly, thus improving on-time performance and robustness of airline schedule. At the same time, the total cost, including the irregular flight cost, decreases by 11.75% compared with the original schedule used by the airline.

Our robust aircraft scheduling model (RASM) is established to minimize propagated delay as the sole robustness objective function. More robustness objectives for multi-fleet aircraft scheduling can be put in the mathematical formulation, such as station purity in paper [13]. In addition, the flight strings in this paper are on a daily basis, but the actual aircraft maintenance routings are generally on a three-day (or four-day) basis. In terms of that, further study for our RASM should be more practical.