A Study on Disrupted Flight Recovery Based on Logic-Based Benders Decomposition Method

Abstract

Aiming at the disrupted flight recovery problem, this paper established a mixed-integer programming model based on the resource assignment model to minimize the recovery cost. To deal with the large-scale examples, the Logic-Based Benders decomposition algorithm is designed to divide the problem into a master problem and sub-problems. The algorithm uses MIP in the master problem to determine flight cancellations and aircraft replacements. In the sub-problems, MIP or CP is used to determine the departure time of delayed flights. Later, incorporating sectional constraints into the main problem and iterating until an optimal solution is obtained. Furthermore, the added cutting plane constraint in the iterations of the Benders decomposition algorithm are strengthened to eliminate more inferior solutions. By comparing the results of CPLEX, the Logic-Based Benders decomposition algorithm, and the enhanced Benders decomposition algorithm, it is verified that the improved Benders decomposition algorithm can solve large-scale examples more efficiently with a faster time and fewer iterations.

1. Introduction

The air transportation industry is an emerging transportation basic industry in the 20th century. As the speed of society and the pace of people’s lives continue to accelerate, the air transportation industry has developed rapidly, and disrupted flights are also becoming increasingly prominent. Disrupted flights refer to flights that cannot be executed according to the original flight plan. The reasons for the disrupted flight are usually bad weather, flow control, aircraft failure, airport closure, and passengers unable to board the aircraft in time [1]. When the flight is not normal, the airline dispatcher needs recover the flight plan, crew scheduling, passenger transit connection, and ground support, so that the flight can be restored as soon as possible, and the cost of the airline should be reduced as much as possible [2]. Since the outbreak of COVID-19, the total traffic volume of air transportation has shown a sharp decline. However, with the gradual improvement in the epidemic and the liberalization of policies, the development of the civil aviation industry has ushered in a recovery. In this context, how to make the flight schedule return to normal as soon as possible is the key issue for airlines to improve their core competitiveness and enhance passenger satisfaction [3].

Many solutions to disrupted flight recovery are based on the aircraft scheduling model, often involving the only single resource of aircraft recovery [4]. Teodorovic and Guberinic built the model for the first time with the minimum passenger delay as the objective function, and adjusted on the disturbed route network [5]. Because the model is relatively simple, its algorithm cannot guarantee the efficiency of solving large-scale problems, many scholars have improved the model and algorithm on this basis. Teodorovic and Stojkovic attempted to take into account the crew, aircraft and maintenance plans, modeling using lexicographic optimization techniques for stratified optimization techniques, regardless of aircraft dispatch [6]. Teodorovic summarized the recovery strategies for disrupted flight recovery problem: canceling or delaying flight, or replacing aircraft [7]. Liang summarized three main problems for disrupted flight recovery: fleet allocation, aircraft routing, and crew scheduling, as well as summarized the general formulas and commonly used solution methods [8]. Bertsimas aimed at the problem of air traffic flow management, a new integer programming (IP) model is proposed. The model covers all phases of each flight [9]. From 1990s to the present, situations involving multiple aircraft models, randomness, and large-scale delays have gradually become the focus of research. Yan and Young tried to extend the model into a multi-model aircraft route recovery model, and regarded it as a minimum cost flow problem [10]. Afterwards, Yan and Tu constructed a multi-commodity flow model for aircraft route recovery [11]. As for the setting of the aircraft disrupted time, due to its random characteristics, scholars further deepened it. For the uncertainty of the aircraft disrupted time, Thengvall and Yu provided the aviation schedule recovery for the first time in a way that allowed airlines to deviate minimally from the original aircraft route [12]. When large-scale delays occur, the airport capacity setting is also crucial. Álvaro and Fernando were based on the Bayesian network method, this paper proposes a method to predict and evaluate the operation state of the airport arrival system, so as to improve the arrival process of the airport [13]. Álvaro also combines the delay and capacity indicators at different stages of airport operations to simulate the causal relationship between airport arrival performance indicators and meteorological events, quantify the impact of weather on airport arrival conditions, and predict the evolution of airport operating scenarios [14]. Liang considered the aircraft recovery problem with airport capacity constraints and maintenance flexibility, and proposed a column generation heuristic method to solve it [15,16,17,18,19]. Ji considered the flight priority and airport capacity constraints and proposed a built-in flight feasibility verification algorithm to improve the rescheduling algorithm [20].

Under the above background, scholars have conducted a lot of research on flight scheduling problem, and the current solution methods are divided into three categories: data-driven method, optimization method, and hybrid method. Data-driven method refers to the method that uses a large amount of data and data analysis technology to discover rules, so as to make decisions and predictions, such as machine learning [21,22], artificial intelligence [23], business analysis [1], among others. Most of them are used in the prevention of delays, and are rarely used in the field of flight recovery after delay occurs. The optimization method is to find the optimal solution or close to the optimal solution through mathematical modeling and algorithm design. The hybrid approach combines the data-driven approach with the optimization approach. At present, the conventional method to solve the problem of disrupted flight recovery is the optimization method [24]. Jarrah uses continuous shortest circuit method to construct the flight recovery model to minimize the flight recovery cost [4]. Cao and Kanafani, based on Jarrah’s model, established a network model with a minimum recovery cost for flight delay and flight cancellation, and turned the problem into a quadratic programming problem to obtain a better solution [25,26]. Bertsimas and Lulli established a new IP model which is presented for a large-scale example of solving the air traffic flow management problem, which covers all phases of each flight, namely take-off, flight, and landing [9]. Yan and Yang constructed a dynamic network model and used Lagrangian relaxation with the subgradient method to solve the flight recovery problem [27]. Le and Gao, based on the network, transformed the disrupted flight recovery problem into a vehicle routing problem with a time window to carry out comprehensive recovery for the crew and passengers [28]. Yan and Tu established a multi-commodity network flow model with the minimum recovery cost, took different aircraft models as different categories of commodities, and adopted a simple method and a Lagrange method to solve it [29]. Thengvall set targets according to users’ preferences, proposed a network model with side constraints, and used an a rounding heuristic algorithm to solve it [12]. Huang based theirs on a copy evaluation method which uses a primal-dual approach to analyze and measure the quality of flight and maintenance copies [30]. Subsequently, many heuristic algorithms have been used to solve the flight recovery problem, such as the Genetic Algorithm (GA) [31,32] and the Greedy randomized adaptive search procedure (GRASP) [32], among others.

From the above analysis, it can be seen that most optimization methods use heuristics or intelligent algorithms to solve the problem. However, as a NP-hard problem for disrupted flight recovery, the heuristic algorithm cannot guarantee the quality of the solution, and the research on the exact solution is obviously insufficient. As an exact solution algorithm, the Benders decomposition algorithm can divide large problems into small subproblems, thus reducing the complexity in time and space, and can deal with more complex and diversified disrupted flight recovery problem. Cordeau and Stojkovi divide the disrupted flight recovery problem into the main problem of aircraft recovery and the subproblem of crew pairing using the Benders decomposition algorithm, and calculate the integer solution by the heuristic branch and bound method [33]. Khiabani established a comprehensive recovery model of aircraft and crew, and used the Benders decomposition algorithm to obtain a more accurate solution [34]. McCarty and Cohn proposed a hybrid algorithm based on the Benders decomposition method and heuristic algorithm, which divided the decision process into two stages and used the heuristic algorithm to solve the flight recovery problem under irregular operations [35]. On the other hand, as an efficient method to solve combinatorial optimization problems, constraints programing (CP) is increasingly applied to planning and resource allocation. Hooker proposed the Logic-Based Benders decomposition algorithm (LBBD) based on the extension of the Benders algorithm [36]. It can solve the planning and scheduling problems, and propose a solution framework combining constraint programming (CP) and mixed integer programming (MIP), so as to combine the advantages of both to better solve large-scale problems.

To sum up, there are few studies on the exact solution of flight recovery problems in recent years, most of which are solved by heuristic and intelligent algorithms. The existing exact solution is mainly to establish the mathematical model of MIP, but MIP is limited by the solving scale and cannot solve large-scale problems, so it cannot verify the optimization of some large-scale problems. In this paper, a modified LBBD algorithm is proposed, which uses the strategy of canceling flights, delaying flights, and replacing aircraft, and adds the time connection constraint and space connection constraint [37] to establish the MIP model based on the resource assignment model. The outline of this paper is organized as follows. The description and hypothesis of the problem are introduced in Section 2. The model formulations and the main contents of LBBD algorithm are introduced in Section 3 and Section 4, respectively. Section 5 represents the results of algorithm. Finally, the conclusions are presented in Section 6.

2. Problem Description

Usually, when making flight plans, airlines will assign multiple continuous flights to the same aircraft. The collection of all flights executed by the same aircraft is called flight train, and an aircraft may temporarily break down and need to be maintained at a fixed airport [38]. Figure 1 depicts the implementation of flights and their corresponding aircraft and airports in a flight plan under disrupted conditions, including 9 flights, 1 maintenance mission, 4 aircraft, and 5 airports. The left solid lines and right dotted lines in the figure, respectively, represent the start and end of the recovery phase of the entire aircraft. The upward arrow on the left represents the earliest time when the aircraft begins to execute the flight, and the downward arrow on the right represents the latest time when the aircraft ends the flight. The solid rectangle represents a flight: the left endpoint of the rectangle represents the starting airport of the flight, the right endpoint of the rectangle represents the destination airport of the flight; the dotted rectangle represents the maintenance task, and the left endpoint of the rectangle tells the airport where the maintenance mission is located. As can be seen from the figure, aircraft 1, aircraft 2, and aircraft 4 perform two flights; aircraft 3 performs three flights; and the destination airport of the previous flight in the flight string is the starting airport of the next flight, indicating the continuity of flights performed by the same aircraft; and aircraft 4 is also carrying out maintenance tasks at the airport DEF, whilst the maintenance time conflicts with the flight time of the first flight of the aircraft 4.

The recovery options set in this paper are as follows: flight delay, flight cancellation, and aircraft replacement. This paper assumes the causes of disrupted flight airport closures and aircraft performing additional maintenance tasks. When an emergency such as bad weather occurs, some airports may have to be closed for a period of time. During this period, flights related to the airport will inevitably be affected, resulting in flights not being executed according to the original flight plan. In addition, aircraft maintenance tasks conflict with flight execution. The two adjacent flights after the adjustment of the station time is unreasonable and other reasons will also affect the normal execution of the flight. This paper does not consider the needs of the crew, so the modification of the aircraft route is not limited by the availability of the crew and aircraft model. Since the recovery window is set for only one day, the flights involved must arrive and depart on the same day to prevent disruption to the next day’s flight schedule. Accordingly, the assumptions of this paper are as follows:

• The status of each flight can only be executed or canceled. If there is an aircraft replacement, the flight will be operated by another aircraft at the original scheduled departure time or after the departure time is adjusted. The aircraft is only exchanged between the same models so that it can adapt to the demand for passenger traffic.
• Each flight can only be delayed or canceled once, and the actual departure time cannot be earlier than the initial time, and the delay time must be less than the specified maximum delay time.
• For two adjacent flights, the arrival airport of the former flight must be the same as the departure airport of the latter flight, and they must have sufficient preparation time between the two adjacent flights.
• The last flight must arrive earlier than the curfew time.
• Each flight can only be carried out by one aircraft.
• If the airport is closed, flights are not allowed to leave or arrive at the airport during this period. If the aircraft requires additional maintenance due to component failure, no flight assignments can be assigned to the aircraft during its scheduled maintenance.

3. Disrupted Flight Aircraft Recovery Model

3.1. Problem Constrains

In this paper, the flight will encounter two abnormal situations: airport closure and aircraft maintenance. Due to any number of unforeseen reasons, some airports need to be closed within a given period of time. Flights are not allowed to leave or arrive at this airport during this time. Additionally, some aircrafts that require additional maintenance due to component failure will be required to remain at the airport for a given period of time because, since the maintenance is unscheduled, it may overlap with some of the off-line flights assigned to it, and therefore, no flight duties can be assigned to the aircraft during the scheduled maintenance process.

Since the flight recovery problem in this paper must be solved in practice, the following constraints must be observed during the recovery process. First of all, each flight can only be delayed or canceled once, and the departure time after the delay must not be earlier than the original time, and the delay time must be less than the maximum delay time. In addition, for two adjacent flights, the arrival airport of the former flight must be the same as the departure airport of the latter flight, and a sufficient preparation time must be allowed between each adjacent flight. Finally, the arrival time of the latest arrival flight must be earlier than the curfew time of the destination airport to ensure that the schedule after the published recovery period can be enforced to avoid disruption extending into the next day. In addition, a flight can only be carried out by one aircraft to ensure the continuity of flight execution. In addition, the aircraft scheduled for maintenance services will not perform any flights.

In this paper, for the aircraft recovery problem of disrupted flight, consider the cost of flight delay, cancellation, and aircraft replacement. There is a positive correlation between delay cost and delay time. In addition, certain flights may be cancelled due to a lack of available aircraft or due to scheduling conflicts with aircraft maintenance tasks, resulting in corresponding cancellation costs. Finally, in the process of flight recovery, some aircraft may be unable to carry out the original scheduled flights due to malfunctions, and these flights can be assigned to other available aircraft, which are called aircraft replacement. The cost of aircraft replacement is smaller than the cost of flight cancellation, so it is a good choice of recovery strategy. Because the restrictions mentioned above must be observed, all constrains are hard constraints, and the model must satisfy the hard constraints to ensure the feasibility of the solution.

3.2. Mathematical Formulation

To accurately describe the problem, a mixed integer programming formulation is constructed. This model aims to minimize the delay cost, cancellation cost, and the flight replacement cost. The physical meanings of the sets, subscripts, parameters, and decision variables used in the mathematical model are as follows.

Subscripts	Definition
$i$	Aircraft subscript, $i\in I$
$f$	Flight subscript, $f\in F$
$s$	Airport subscript, $s\in S$
$m$	Maintenance task subscript, $m\in M$
$r$	Sequential subscripts of flights in the aircraft path, $r\in R$
Sets	Definition
$I$	Available aircraft collection
$F$	Flight collection in normal flight plan
$S$	All airport collection
$M$	Aircraft maintenance task set
$S^C$	Airport collection closed due to failure
$S^M$	Airport collection where maintenance tasks are located
$I^M$	The collection of aircraft where the maintenance mission is located
$F_i$	Represents the set of all flights performed by aircraft $i$, and the set of all uncanceled flight tasks is obtained by solving the main problem
Parameters	Definition
${sd}_f$	The original planned departure airport of flight $f$, ${sd}_f\in S$
${sa}_f$	The original planned landed airport of flight $f$, ${sa}_f\in S$
$i_f$	The original planned aircraft of flight $f$, ${ip}_f\in I$
${td}_f$	The original planned departure time of flight $f$
${ta}_f$	The original planned arrival time of flight $f$
${tb}_s$	Closing start time of airport $s$ due to fault shutdown
${te}_s$	Closing end time of airport $s$ due to fault shutdown
$b_m$	Starting time of maintenance $m$
$e_m$	Ending time of maintenance $m$
$s_m$	Located airport of maintenance $m$
$i_m$	The aircraft of maintenance $m$
$st$	The earliest time when all aircraft $i$ started executing flight
$et$	The latest time for all aircraft $i$ to finish the flight
$s_i$	The airport where the first flight of the aircraft $i$
$G$	A larger positive integer
$R$	The number of flights
$D$	The maximum delay time of flight
$S$	The transit time of the two consecutive flights
Decision variables	Definition
$t_f$	Actual departure time of flight $f$
$v_i$	The number of flights actually executed by aircraft $i$
$x_{fi}$	0–1 variable, if flight $f$ is actually assigned to aircraft $i$ to execute, then $x_{fi}=1$, otherwise $x_{fi}=0$
$y_f$	0–1 variable, if flight $f$ is canceled, then $y_f=1$, otherwise $y_f=0$
$p_f$	0–1 variable, if the actual execution of the flight $f$ is not equal to the original planned execution of the aircraft, then $p_f=1$, otherwise $p_f=0$
$k_{f,i,r}$	0–1 variable, if the flight $r$ actually executed by aircraft $i$ is flight $f$, then $k_{f,i,r}$ = 1, otherwise $k_{f,i,r}=0$
$\alpha ,\beta ,\gamma$	0–1 variable, used to define the status of flights and airports under the same conditions, if a certain situation exists, then they equal to 1, otherwise equal to 0

The mathematical model for disrupted flight recovery established in this paper is as follows:

$$\mathit{Minimize}{\omega }_1\sum _{f\in F}\sum _{i\in I}{x}_{fi}\left(t_f-{td}_f\right)+{\omega }_2\sum _{f\in F}{y}_f+{\omega }_3\sum _{f\in F}{p}_f$$

(1)

$${\sum }_{i\in I}{x}_{fi}+y_f=1 \forall f\in F$$

(2)

$$G\ast y_f+D-t_f+{td}_f\ge 0 \forall f\in F$$

(3)

$$G\ast y_f+t_f-{td}_f\ge 0 \forall f\in F$$

(4)

$$G\ast y_f+t_f-st\ge 0 \forall f\in F$$

(5)

$$G\ast y_f+et-t_f-({ta}_f-{td}_f)\ge 0 \forall f\in F$$

(6)

$$G\ast y_f+G\ast (1-\alpha )+t{b}_x-t_f\ge 0 \forall f\in F,\forall s\in s^c,{sd}_f=s$$

(7)

$$G\ast y_f+G\ast \alpha +t_f-{te}_s\ge 0 \forall f\in F,\forall s\in s^c,{sd}_f=s$$

(8)

$$G\ast y_f+G\ast (1-\beta )+t{b}_s-t_f-{ta}_f+{td}_f\ge 0 \forall f\in F,\forall s\in s^c,{sa}_f=s$$

(9)

$$G\ast y_f+G\ast \beta +t_f+{ta}_f-{td}_f-{te}_s\ge 0 \forall f\in F,\forall s\in s^c,{sa}_f=s$$

(10)

$$G\ast {(1-x}_{f{i}_m})+G(1-\gamma )+b_m-(t_f+{ta}_f-{td}_f)\ge 0 \forall f\in F,\forall m\in M,{\forall i}_m=I^M$$

(11)

$$G\ast {(1-x}_{f{i}_m})+G\ast \gamma +t_f-e_m\ge 0 \forall f\in F,\forall m\in M,{\forall i}_m=I^M$$

(12)

$${y_f+x}_{f{i}_f}+p_f=1 \forall f\in F,\forall i_f\in I$$

(13)

$$v_i={\sum }_{f\in F}{x}_{fi} \forall i\in I$$

(14)

$${\sum }_{r\in R}r\ast k_{f,i,r}\le v_i \forall i\in I,\forall f\in F$$

(15)

$$x_{fi}={\sum }_{r\in R}{k}_{f,i,r} \forall i\in I,\forall f\in F$$

(16)

$$k_{f,i,r}+k_{\overline{f},i,r+1}\le 1 \forall i\in I,\forall f,\overline{f}\in F,\forall r\in R-1,{sa}_f\ne {sd}_{\overline{f}}$$

(17)

$$G(2-k_{f,i,r}-k_{\overline{f},i,r+1})+t_{\overline{f}}-(t_f+{ta}_f-{td}_f)\ge S \forall i\in I,\forall s\in S,\forall r\in R-1,\forall f,\overline{f}\in F,{sa}_f={sd}_{\overline{f}}$$

(18)

$$k_{f,i,1}=0 \forall i\in I,\forall f\in F,{sa}_f\ne s_i$$

(19)

Equation (1) is an objective function that requires the minimization of the weighted sum of the costs, and the cost in the objective function consists of three parts. The first part is the flight delay time cost, the second part is the flight cancellation cost, and the third part is the flight exchange cost; Equation (2) is the flight coverage constraint, indicating that each flight is either executed or canceled; Equation (3) indicates that, if the flight is executed, the flight delay time cannot be greater than the maximum delay time; Equation (4) indicates that if the flight is executed, the actual departure time of the flight shall not be earlier than the original planned departure time; Equation (5) indicates that, if the flight is executed, the actual departure time of the flight is not earlier than the earliest departure time, when all aircraft begin to perform the flight; Equation (6) indicates that, if the flight is executed, the actual landing time of the flight is not later than the latest time at which all aircraft end the flight; Equations (7) and (8) indicate that, if the flight is executed and the planned departure airport is closed, the actual departure time of the flight is before the airport closing start time or after the airport closing period; Equations (9) and (10) indicate that, if the flight is executed and the flight’s planning landing airport is the closed airport, the actual arrival time of the flight is before the airport closing start time or after the airport closing end time. Equations (11) and (12) indicate that the departure time of the flight by the corresponding maintenance aircraft must be before the maintenance begins, and the flight arrival time must be after the maintenance end time; Equation (13) indicates that the flight is either canceled, or the aircraft is scheduled to be executed as originally planned, or the aircraft is executed; Equations (14) and (15) calculate the number of flights performed by the aircraft; Equation (16) defines the range and conditions of the decision variable $k$; Equation (17) is the space articulation constraint, indicating that the same aircraft performs two flights. For the adjacent flight, the arrival airport of the previous flight must be the departure airport of the latter flight; Equation (18) is the time connection constraint, indicating that the two consecutive flights executed by the same aircraft have enough transit time. Equation (19) indicates that the airport where the aircraft begins must match the airport at which the first mission begins.

4. Logic-Based Benders Decomposition Algorithm

When the scale of the problem increases gradually, the results of the problem cannot be obtained directly using CPLEX, so it is necessary to design LBBD algorithm to solve the problem. LBBD algorithm is an accurate algorithm, which divides a complete problem into two parts: the main problem and the subproblem. The solution of MP is not constrained by the variables in the subproblem: MP is solved first, and the solution of MP is brought to SP as a parameter to solve the remaining variables. The solution results of SP will be fed back to MP in a cross-sectional way to improve the quality of the solution and reduce the space of the solution, the above process will be iteratively solved until the objective function values of MP and SP are the same, and the optimal solution of the problem is obtained. The specific logic of algorithm is shown in Figure 2 and Figure 3.

According to the research problem, the overall model is divided into two problems: (1) The main problem is the flight schedule recovery problem, considering flight cancellation and replacement, and establishes MIP model; (2) The subproblem only considers flight delay, calculates flight delay cost, and establishes the CP model. From the solution of MP, we can obtain the set $F_i$, representing the set of all uncancelled flight tasks performed by aircraft $i$. Since only partial constraints are considered in the main problem, we obtain the lower bound ($LB$) of the solution. By substituting the obtained parameters into SP, the delay cost is obtained, and the recovery cost $C$ includes the delay cost and the cancellation cost. Finally, the total recovery cost is obtained, which is the upper bound ($UB$) of the whole problem. The effective cut generated by the SP solution is added to the next MP as a constraint, and its function is to remove the bad solution from the solution set of MP to narrow the solution range of MP. The cut selection rule is to compare the $C$ in each iteration SP with the current $UB$. When $C\ge UB$, the aircraft $i$ assigned by the flight task will be added to the cut set $I_h$, which represents the cut of the $h$ generation aircraft serial number. The cut constraint is shown in Formula (21), which represents the flight performance. The same combination of flight tasks will not be assigned to the same aircraft again. The complete LBBD solution process is as follows:

Step 1: Set the number of iterations to 0, solve MP without cut constraints to obtain the initial solution $x_{fi}$, obtain the flight cancellation and aircraft replacement costs, as well as the initial LB, and set the initial $UB$ equal to $\infty$. Step 2: Determine the variables in SP. If $x_{fi}=1$, then flight $f$ is executed, and the set $F_i$ of all flights executed by the aircraft $i$ that are not canceled can be obtained. The above variables are brought into SP as parameters to solve, and the optimal solution to SP is obtained. Compare $UB$ and recovery cost $C$, if $UB>C$, $\mathrm{then} UB=C$, and $\mathrm{the} UB$ of the solution is obtained. If $C\ge UB$, then add the flight $i$ to the cut set $I_h$. Step 3: Update iteration number $h=h+1$, add the cut constraint to MP to solve, and see the output results. If the MP has no feasible solution, then jump to step 4. According to the LBBD algorithm, if the MP has a feasible solution, a new lower bound LB of the original problem is obtained. Update $LB$, if $LB<UB$, then go back to step 2 until $LB=UB$. Step 4: If $LB=UB$, the best solution we found is the optimal, and the flight schedule and flight recovery cost are obtained.

4.1. Main Problem Design

According to the parameters and decision variables defined above, the main problem does not consider the flight delay time, but only considers whether the flight is canceled, whether the aircraft is replaced, and establishes the corresponding integer programming model as follows:

$$\mathit{Minimize}{\omega }_2\sum _{f\in F}{y}_f++{\omega }_3\sum _{f\in F}{p}_f$$

(20)

(2)(13)–(15)(17)–(19)

$${\sum }_{f\in F_i}(1-k_{f,i,r})\ge 1 \forall i\in I_h,\forall r\in R$$

(21)

4.2. Subproblem Design

Two types of variables are introduced for the CP model. The first set of variables are interval variables which represent an interval of time that needs to be scheduled. The variable contains a start value, an end value, and an interval. The interval length is the operation time of the task $i$. Among them, $startOf\left(a\right)$ represents the start time of the interval variable, $endOf\left(a\right)$ represents the end time of the interval variable, and $sizeOf\left(a\right)$ represents the interval length of the interval variable. The variable $presenceOf\left(a\right)$ is used to define the optional state of the interval variable. If the interval variable is present, is equal to 1. Otherwise, it is equals to 0. The second type of variables is interval sequence variables. They are defined by a series of interval variables whose values represent the ordering of the interval variables in the set.

Three types of global constraints are introduced for the CP formulation. The first constraint $noOverlap\left(a\right)$ is a non-overlapping constraint. It can be used in combination with interval sequence variables. This special constraint ensures that the interval variables within the interval sequence variable will not overlap, and the end time of each interval variable is earlier than or equal to the start time of the next interval variable. The second constraint $alternative(a,\{b_1,b_2,\cdots b_n\left\}\right)$ is an optional constraint. It is used to create a constraint between an interval variable and a set of optional interval variable, where $a$ has and can only correspond to one interelectable variable derived from $\{b_1,b_2,\cdots b_n\}$. The third constraint $endBeforeStart(a,b)$ is a priority relationship constraint. It is used to describe the priority relationship between two interval variables. This means that the end time of interval $a$ must be before the start time of the interval $b$. This can ensure the priority relationship between two adjacent flights.

After solving the main problem, the flight sequence of the flights executed by each aircraft can be determined. Therefore, in the subproblem constrained programming model, the decision variable is changed into a parameter input. The interval decision variable represents the flight mission of flight. The subproblem comprises the MIP model and CP model.

MIP model designed in this paper is as follows:

$$\mathit{Minmize}{\omega }_1\sum _{f\in F}\sum _{i\in I}{x}_{fi}\left(t_f-{td}_f\right)$$

(22)

(3)–(12)(16)

CP model designed in this paper is as follows:

$$Minimize{\omega }_1\sum _{f\in F}presenceOf({Task}_f)\ast (startOf({Task}_f)-{ta}_f)$$

(23)

$${startOf({Task}_f)-td}_f\ge 0 \forall f\in F$$

(24)

$$startOf({Task}_f)-st\ge 0 \forall f\in F$$

(25)

$$endOf({Task}_f)-et\ge 0 \forall f\in F$$

(26)

$$180-startOf({Task}_f)+{td}_f\ge 0 \forall f\in F$$

(27)

$${tb}_s-startOf({Task}_f)\ge 0||startOf({Task}_f)-{te}_s\ge 0 \forall f\in F,\forall s\in S^c,s={sd}_f$$

(28)

$${tb}_s-endOf({Task}_f)\ge 0||endOf({Task}_f)-{te}_s\ge 0 \forall f\in F,\forall s\in S^c,s={sa}_f$$

(29)

$$endOf({Task}_f)\le b_m||startOf({Task}_f)\ge e_m \forall f\in F,\forall m\in M,{ip}_f=i_m$$

(30)

$$startOf({Task}_{\overline{f}})-endOf({Task}_f)\ge 30 \forall i\in I,\forall r\in R-1,{\forall f,\overline{f}\in F,k}_{f,i,r}=k_{\overline{f},i,r+1}=1$$

(31)

Equations (22) and (23) are the objective functions, which require the flight delay cost to be the minimum; Equation (24) indicates that the actual departure time of the flight must not be earlier than the original planned departure time; Equation (25) indicates that the actual flight departure time is not earlier than the moment when all aircraft begins to execute the flight; Equation (26) indicates that the actual landing time of the flight is not later than the latest time when all the aircraft finish the flight; Equation (27) indicates that the flight delay time cannot be greater than 180 min; Equations (28) and (29) indicate that, if the planned departure of the flight is to close the airport, the actual departure time of the flight must be before the airport closure start time or after the airport closure period; Equation (30) indicates that, if the aircraft maintenance mission is executed, the departure time of all flights must be after the maintenance end time or the landing time must be before the maintenance start time; Equation (31) is the time connection constraint, indicating that the two consecutive flights executed by the same aircraft have an overtime of no less than 30 min.

4.3. Strengthen Benders Cut

In the process of the Benders decomposition algorithm, the Benders cut has an important impact on the efficiency and quality of the solution. The above-mentioned cut is relatively weak, and it is necessary to enhance the cut to reduce more inferior solutions to obtain better solution results and efficiency. The specific operation is as follows: set the recovery cost $C$, and propose flight $\mathrm{f}$ from $F_i$; the remaining tasks are solved by substituting them into sub-problem. If $C\ge UB$ is obtained, this means that removing $\mathrm{f}$ will not improve the sub-problem result. Then, remove $f$ from the flight set $F_i$, and repeat the operation until $C<UB$ and the remaining ones form the flight set ${\overline{F}}_i$. The cut generated in this way can reduce more inferior solutions in main problem and reduce the number of iterations. The LBBD with an improved cut obtained in this way is designated as LBBD(S). The cut strengthening Formula (21) becomes (32).

$${\sum }_{f\in {\overline{F}}_i}(1-k_{f,i,r})\ge 1 \forall i\in I_h,\forall r\in R$$

(32)

5. Experiments

In this section, in order to evaluate the solution effect of the proposed decomposition model and the Benders decomposition algorithm, this paper sets up different scales of disrupted flight situations. The MIP model is solved with IBM ILOG CPLEX, and the LBBD algorithm and LBBD(S) algorithm are solved with Python using the IBM ILOG CPLEX 12.6.1. The setting of the subproblem in the LBBD algorithm is divided into two situations: the MIP solution and CP solution. The setting of the subproblem in the LBBD(S) algorithm is the CP solution. All examples are run on a personal computer with the Intel(R) Core(TM) i5-11320H3.20GHz CPU processor. The data come from the flight schedule operated by Shanghai Airlines Co., Ltd. The data include the flight number of different size examples, the airport where the aircraft took off and landed, the take-off and landing time, and the airport closure and aircraft maintenance tasks encountered. The weights of the various costs are reasonably set according to experience, and in 2017, the China Graduate Mathematical Modeling Competition. The objective function consists of three parts: the first part is the flight delay time cost, where the time is measured in minutes and the weight value is 1; the second part is the flight cancellation cost, and the weight value is 800; the third part is the flight exchange cost, and the weight value is 10. The maximum delay time is 180 min, and the transit time for the two consecutive flights is 30 min. Examples 1–6 are small-scale examples, and Examples 7–11 are large-scale examples. The maximum running time for solving the flight example is set to 3600 s. If no solution is found within 3600 s, it is indicated by “-”. The calculation results are shown in

Table 1. Comparison of optimal results at different examples.

Example	Problem Scale	MIP			LBBD (Sub-MIP)	LBBD (Sub-CP)	LBBD(S)
		UB	LB	Optimal Solution	Optimal Solution	Optimal Solution	Optimal Solution
1	3a-12f-1c	-	-	2730	2730	2730	2730
2	3a-12f-1m	-	-	15	15	15	15
3	3a-12f-1c-1m	-	-	2745	2745	2745	2745
4	4a-15f-1c	-	-	150	150	150	150
5	4a-15f-1m	-	-	40	40	40	40
6	4a-15f-1c-1m	-	-	110	110	110	110
7	10a-35f-1c-1m	478	2110	-	1398	1398	1398
8	19a-68f-1c-3m	5000	1210	-	2249	2249	2249
9	28a-135f-2c-5m	-	-	-	2515	2515	2515
10	30a-149f-2c-6m	-	-	-	3362	3362	3362
11	44a-633f-1c-29m	-	-	-	1756	1756	1756

Note: The alphanumeric combination in the scale column indicates the number of aircraft, flights, airport closures, and aircraft maintenance tasks in the daily flight schedule. For example, 3a_7f (1c_1m) means 3 aircraft, 7 flights, 1 airport closed, 1 Aircraft maintenance mission.

,

Table 2. Comparison of the solving time for different examples.

Example	Problem Scale	MIP	LBBD (Sub-MIP)	LBBD (Sub-CP)		LBBD(S)
		CPU(S)	CPU(S)	CPU(S)	Gap(%)	CPU(S)	Gap(%)
1	3a-12f-1c	5	0.72	0.32	−125	0.4	−80
2	3a-12f-1m	9	0.31	0.27	−14.81	0.42	26.19
3	3a-12f-1c-1m	23	0.69	0.44	−56.82	0.51	−35.29
4	4a-15f-1c	11	0.58	0.68	14.71	0.49	−18.37
5	4a-15f-1m	17	0.36	0.28	−28.57	0.46	21.74
6	4a-15f-1c-1m	15	1.99	1.56	−27.56	1.17	−70.09
7	10a-35f-1c-1m	3600	185.67	196.56	5.54	201.32	7.77
8	19a-68f-1c-3m	3600	392.71	169.66	−131.47	171.73	−128.68
9	28a-135f-2c-5m	3600	569.47	210.49	−170.54	208.83	−172.70
10	30a-149f-2c-6m	3600	596.18	279.65	−113.19	263.11	−126.59
11	44a-633f-1c-29m	3600	639.89	345.61	−85.15	338.5	−89.04

and

Table 3. Comparison of the iteration number at different examples.

Example	Problem Scale	LBBD (Sub-MIP)	LBBD (Sub-CP)		LBBD(S)
		Iteration Number	Iteration Number	Gap(%)	Iteration Number	Gap(%)
1	3a-12f-1c	3	5	40	3	0
2	3a-12f-1m	3	4	25	3	0
3	3a-12f-1c-1m	8	6	−33.33	6	−33.33
4	4a-15f-1c	4	4	0	4	0
5	4a-15f-1m	4	6	33.33	4	0
6	4a-15f-1c-1m	8	11	27.27	8	0
7	10a-35f-1c-1m	65	73	10.96	65	0
8	19a-68f-1c-3m	184	78	−135.90	57	−222.81
9	28a-135f-2c-5m	209	151	−38.41	79	−164.56
10	30a-149f-2c-6m	237	189	−25.40	93	−154.84
11	44a-633f-1c-29m	375	294	−27.55	167	−124.56

.

It can be seen from the solutions’ results in Table 1, Table 2 and Table 3 that, in the small-scale examples, both CPLEX and the Benders decomposition algorithm can accurately find the optimal solution within the specified time. From the perspective of solution time, the solution is better when the LBBD subproblem is CP. However, due to the small-scale examples of LBBD(S), the improvement in solution time is not particularly obvious compared with LBBD. From the perspective of iterations, LBBD(S) has a more efficient solution which can obtain the optimal solution with fewer iterations. Therefore, as the scale of the problem increases, MIP has a poor solving performance and does not have the ability to solve larger-scale problems, while the two decomposition algorithms have better applicability for solving disrupted flight recovery problems.

In solving large-scale examples, due to the limitations of CPLEX, with the increase in the scale, the efficiency of the solution decreases significantly. However, aiming at the LBBD and LBBD(S), both algorithms have good solving capabilities in large-scale examples. It can be seen from the solution time in Table 1, Table 2 and Table 3 that, when using the LBBD to calculate large-scale examples 9–10, the solution effect is better when the subproblem is CP than when the subproblem is MIP. Because the solving ability of MIP is affected by the number of variables, the solving efficiency of the MIP model will become lower as the scale of the problem gradually expands, and the solution speed will become slower—while CP is more suitable for solving scheduling problem. It can use constraint conditions to better narrow the solution space. From the iterations for the large-scale examples 7–11 in Table 1, Table 2 and Table 3, when the subproblem is CP, the iterations are less than they are when the subproblem is MIP, which can solve the problem efficiently. Especially in Example 8, when the subproblem is CP, it only takes 78 iterations to obtain the optimal solution, and the iterations are reduced by half compared to when the subproblem is MIP. The reason is that the longer the solution time of the subproblem in the iterative process of the LBBD algorithm is, the number of iterations may increase. Each iteration requires waiting for the solution results of the subproblem. For NP-hard problems such as disrupted flight recovery, CP can flexibly use a variety of constraints to represent the problem, which can better adapt to the complex constraints of the problem.

In Table 1, Table 2 and Table 3, although the solution of LBBD for large-scale examples 7–11 is relatively stable, it also has certain limitations. By comparing the results of large-scale examples in Figure 4, it can be concluded that LBBD(S) can obtain the optimal solution more efficiently. The main reason is the selection of the LBBD cut. In LBBD, the cut has a great influence on the quality and efficiency of the solution. If the cut is more effective, the more inferior solutions can be eliminated per cut at a time; the faster the solution space shrinks, and the faster the quality solutions can be obtained, LBBD(S) with cut improvement can better adapt to problem solving.

Finally, by analyzing the solution results of the example 3 and example 4 in

Table 4. The flight recovery table for example 3.

Aircraft Number	Flight Number	Delay Cost	Cancellation Cost
A/1	11	0	0
	12	0	0
	13	170	0
	14	0	800
A/2	21	15	0
	22	160	0
	23	0	800
	24	0	800
A/3	31	0	0
	32	0	0
	33	0	0
	34	0	0

and

Table 5. The flight recovery table for example 4.

Aircraft Number	Flight Number	Delay Cost	Replacement Cost
A/1	11	100	0
	12	10	10
A/2	21	0	0
	22	0	0
	23	0	0
	24	0	0
	25	0	0
A/3	31	0	0
	32	0	10
	33	0	10
	34	0	10
A/4	41	0	0
	42	0	0
	43	0	0
	44	0	0

, the reasons for flight delay are as follows. The specific recovery situation can be found in Figure 5 and Figure 6. Firstly, the scheduled departure time of the flight is before the end of the maintenance task, so the flight is delayed until after the end of the maintenance task; Secondly, due to the delay of the adjacent previous flight, the estimated preparation time of the next flight is less than 30 min, so it is delayed so that there is enough preparation time. Finally, it is much cheaper to replace the aircraft for flight recovery than to simply delay the aircraft, so the cost of replacing aircraft is incurred. Therefore, airlines should try to reduce the occurrence of flight cancellations, so as to reduce the cost of flight recovery.

6. Conclusions

The purpose of this paper is to optimize the solution of the flight recovery problem and minimize the cost of flight recovery. Based on the existing resource assignment model, this paper introduced spatiotemporal connection constraints for the problem to establish an MIP model. The model not only included the common aircraft recovery strategies, but also considered eight kinds of constraints such as flight coverage, airport closure, and first flight airport matching, and completely describe the aircraft route recovery problem. In order to solve the problem, LBBD(S) algorithm was designed. The algorithm divided the problem into MP and SP, and established the MIP model and CP model for solution, respectively, and the results indicated that the LBBD(S) algorithm is better than the CPLEX direct solution and LBBD algorithm in solving large-scale examples, and can solve the problem more efficiently.

The disrupted flight recovery is a very complex system real-time planning problem, which is of great strategic significance for airlines to improve the service quality and flight management ability. This paper mainly focuses on the aircraft planning recovery problem. Given the limited time and effort, the following issues still need to be further studied and explored. Further research can also be extended to the recovery of other resources for disrupted flights. In addition to aircraft recovery, the issue of disrupted flight recovery also involves crew recovery and passenger recovery. The comprehensive recovery issue of disrupted flights needs further research in the future. It is also possible to use some new methods for the sensitivity analyses of different parameters and explore the feasibility of new methods.