# Weighted Time-Band Approximation Model for Flight Operations Recovery considering Simplex Group Cycle Approaches in China

Authors: Haiwen Xu; Songchen Han
Journal: Mathematical Problems in Engineering
 (2016)

---

## Abstract

The time-band approximation model for flight operations recovery following disruption (Bard, Yu, Arguello, IIE Transactions, 33, 931–947, 2001) is constructed by partitioning the recovery period into time bands and by approximating the delay costs associated with the possible flight connections. However, for disruptions occurring in a hub-and-spoke network, a large number of possible flight connections are constructed throughout the entire flight schedule, so as to obtain the approximate optimal. In this paper, we show the application of the simplex group cycle approach to hub-and-spoke airlines in China, along with the related weighted threshold necessary for controlling the computation time and the flight disruption scope and depth. Subsequently, we present the weighted time-band approximation model for flight operations recovery, which incorporates the simplex group cycle approach. Simple numerical experiments using actual data from Air China show that the weighted time-band approximation model is feasible, and the results of stochastic experiments using actual data from Sichuan Airlines show that the flight disruption and computation time are controlled by the airline operations control center, which aims to achieve a balance between the flight disruption scope and depth, computation time, and recovery value.


---

## Body

## 1. Introduction

Flight plans are very important for all airlines, as the efficiency of their construction can significantly affect profit margins and because they involve aircraft, crew, airports, and other important factors. Flight plans contain a series of flight schedules, which consist of the originating city, the departure time, the destination city, and the arrival time for flights the airline intends to operate. However, aircraft mechanical problems, crew unavailability due to illness, and inclement weather conditions often lead to disruptions and delay flight plan propagation [1]. With the rapid increase in scheduled flights and airlines in China, a greater number of airline schedule disruptions are occurring. Moreover, the aircraft, crew, airports, airspace ports, and airspace capacities are connected and restricted; thus, disruptions can lead to a domino effect that generates further flight disruptions. Such disruptions often result in irregular operations such as delays, cancellations, and aircraft reassignment. The majority of irregular operations can be attributed to four major factors, namely, shortage of airline resources (such as crew, aircraft, ground personnel, and gates), airport and airspace capacity shortages, inclement weather conditions, and management-level discontent that affects the related resources. In 2013, the economic losses due to airline schedule disruptions exceeded RMB43 billion, according to the Civil Aviation Resource Net of China. However, the Civil Aviation Development Statistical Bulletin reports that, at most, 50.49% of the schedule disruptions in 2014 can be attributed to airlines, with 26.41% being the average result. Therefore, the speed with which flight operations are recovered is very important in order to reduce economic losses due to schedule disruptions.A large amount of research has been devoted to this topic. For example, Teodorović and Guberinić [2] have presented a network (representing an airline network) in which the nodes represent the flights and the arcs are the total time losses on individual flights. Hence, a branch and bound procedure was developed to minimize the total passenger delay when an aircraft is grounded. Further, Teodorović and Stojković [3] have introduced a lexicographic dynamic programming approach and a heuristic algorithm to minimize the total passenger delays and the number of cancelled flights. Two minimum-cost network flow models to address aircraft shortages have also been introduced by Jarrah et al. [4]. The first is a delay model that allows for flights to be delayed or cancelled, aircraft to be alternated among scheduled flights, or the usage of surplus aircraft to be requested. The second model minimizes the total flight leg cancellation costs by similarly selecting multiple cancellations, employing aircraft substitution, and utilizing spare aircraft. However, accurate flight delay costs can not yet be quickly and easily determined, and the scope and depth of the flight disruption are not considered in the above models. In contrast, delay costs can be approximated with accuracy using the time-band approximation model introduced by Yu et al., which was developed in order to retain the superiority of the resource assignment model and the multicommodity flow model. Further, Yu [5] has introduced a time-based two-commodity network optimization model for aircraft routing. One commodity in the network model represents aircraft, while the other represents flight cancellations. In addition, Yan and Yang [6] have published a single model to initially combine flight cancellations and delays and to ferry flights. Using a basic time-space network representation, Yan and Lin [7] have developed network flow models to handle station closures, while Yan and Tu [8] have proposed a multiple-fleet network flow model. Finally, Cao and Kanafani [9, 10] have developed a minimum-cost network flow aircraft recovery model, along with network flow algorithms to determine solutions.However, the mathematical solution derived from a time-based network does not represent the delay costs accurately. In order to develop an optimization model that can determine delay costs with greater accuracy than the multicommodity flow model, the time-band optimization model for aircraft routing reconstruction in response to groundings and delays experienced over the course of a day has been introduced [11, 12]. A mathematical model that captures the delay costs for each flight based on a time-based network has been developed; the motivation for this approach is to exploit the underlying network structure associated with aircraft routings, with the mathematical model being a single-commodity integral minimum-cost flow problem with side constraints. The concept behind this model is to partition the time horizon into time bands with a fixed length. The nodes in the resulting network represent possible activity at a station. Thus, in the established network, some nodes are positioned at fixed intervals on the time axis. The aggregation of activities for that station can then be attained in O(mnt) operations, where m is the number of stations, n is the number of flights, and (1)t=timehorizontimesegmentlength.All aircraft that arrive at a station within the time period represented by a node may then be connected to any flights scheduled to depart from that station. The delay time can be approximated with an accuracy that is dependent on the length of the time segment; therefore, the delay costs can be determined quickly.When disruptions occur, the airline controllers in the airline operations control centers (AOCC) adjust the scheduled operations by delaying flight departures, cancelling flight legs, rerouting or swapping aircraft, summoning new crew (or reassigning existing crew), and so forth. In order to reassign resources and adjust flight schedules in the most economic manner, certain factors must be acknowledged: the flight delay costs, flight cancellation costs, aircraft substitution costs, aircraft assignment, crew schedules, maintenance requirements, aircraft positions, and so forth. However, it is difficult to determine the delay costs exactly. Further, flight cancellation costs involve both passenger opportunity costs and direct costs, and the delay time cannot be determined in advance. Therefore, the ability to compute both delay and flight cancellation costs is very important as regards the solution of flight operations recovery problems. Such solutions determine adjusted flight departure times, cancellations, and revised routing for affected aircraft.Many researchers have conducted significant work with regard to flight operations recovery considering passenger factors. For example, Bratu and Barnhart [13] have proposed two flight operations recovery optimization models, the Disrupted Passenger Metric (DPM) and the Passenger Delay Metric (PDM) models, the objective of which is to find the optimal trade-off between airline operation costs and passenger delay costs. The resultant recovery plans work to select flight departure times and flight cancellations, to assign aircraft, to reserve crews for each flight leg as necessary, and to ensure the constraints regarding crew regulations and aircraft maintenance requirements are considered. The objective of the DPM model is to minimize the sum of the operating and disrupted passenger costs. In contrast, the PDM model is constructed to more accurately compute delay costs. Thus, a special procedure to compute the costs due to disrupted passengers has been developed. In addition, Hu et al. [14] have proposed the integrated integer programming model, which is based on an approximate reduced time-band network and a passenger transiting relationship. The objective is to minimize the total cost associated with reassigning aircraft and passengers to flights. A feasibility analysis for the problem is conducted in order to obtain the conditions under which aircraft and passenger recovery is possible. Further, Zhao et al. [15] have introduced an approach in which the flight delay costs are subdivided, proposing the concept of passenger disappointment spillover cost, and demonstrated a mathematical model of an irregular flight schedule recovery problem that reschedules flight legs and reroutes aircraft by minimizing an objective function involving the flight delay costs or the delay time. The airline can choose one of selections of objective functions according to their needs. However, determining the passenger disappointment spillover cost function remains a problem, and the compensation provided by the airline is a very important factor influencing this cost function. For further research on recovery considering passenger factors, see [16–19]. Castro et al. [19] give a new approach for disruption management in airline operations control. They provide a Multiagent System Architecture that represents the AOCC, and introduce a method to calculate the quality costs from the passenger point of view and a system classification to classify disruption management systems. They have done much original work in the recovery operational costs; especially they first propose the quality operational costs (the cost that each minute of delay and flight cancellation has from a passengers point of view). They try to quantify in a monetary unit the cost that each minute of delay and flight cancellation has from a passengers point of view and, at the same time, use that value together with the direct operational costs to improve the decision making during the disruption management process. The quality costs of a flight are given out under the passenger goodwill; what is more, they propose the airline company case study of TAP Portugal, regarding the delay cost from the point of view of the passengers. However, we can not directly use a similar method to calculate the passenger recovery costs in China, in that the preconception of passenger’s compensation costs comes from Confucius’s idea of the average distribution two thousand years ago and some exemption rules from Civil Aviation Administration of China, such as the weather and other objective reasons, and the passengers can not get any compensation.When one or several aircraft are grounded, a heuristic approach based on a greedy randomized adaptive search procedure (GRASP) for the reconstruction of aircraft routes, which has been developed by Argüello et al. [20], can be applied. (Further optimization methods are provided in [21–25].) However, a large proportion of the feasible optimization methods copy flights to the entire flight schedule, while other resources are reassigned in order to repair the disrupted schedules in the best possible manner; thus, the disruption scope or depth may be wide or great. Further, the computation time increases with increases in the number of potentially disrupted flights, when such disruptions occur in hub-and-spoke airline networks.Petersen et al. [26] have introduced a disruptable flight set in an attempt to control the recovery search scope of an optimization approach to airline integrated recovery. This approach yields the first computed results for the fully integrated problem. In fact, the disruptable flight set may be comprised of all flights and the actual scope and depth of the disruption may not be controlled. In addition, Lan et al. [27] have introduced aircraft routing and flight departure time adjustment in order to reduce the number of disrupted passengers and to minimize the number of passenger misconnections. However, some passengers may have a long delay time or the flight scope may be wide. The computation time and the disruption scope and depth are not yet fully controllable.At the 2012 Informs meeting, we first proposed the simplex group cycle approach as a means of controlling the potential disruption scope [28]. The approximated delay costs considering the random flying time around the planned flying time is first introduced in the literature [29], and the time-band approximation model on flight operations recovery problems is constructed based on the time-band network and approximated delay costs. Further, a series of numerical experiments show that the time-band approximation model on flight operations recovery with the random flying time may be more efficient than the time-band approximation model on flight operations recovery with the planned flying time. Using the thought of stochastic delay costs, the approximated cancellation costs formula is first introduced in this paper. In addition, the formula takes into account interval random number, the number of passengers, and approximate city accommodation costs. However, we did not introduce the feasible algorithm for aircraft and flight partitioning, the feasible algorithm to compute weighted value and simulation tests, and so forth, in our previous work.Previously, Clausen et al. [30] have shown that robust planning or schedule robustness is an interesting research topic closely related to disruption management. The goal of robust planning is to reduce the sensitivity of flight and crew schedules and aircraft rotations to disruptions. Rosenberger et al. [31] have also proposed a robust fleet-assignment model with hub isolation and short cycles and proven that fleet assignments with limited hub connectivity have a greater number of short cycles. A cycle is a sequence of flights that begins and ends at the same airport; further when a cycle contains fewer flights, this cycle is called short cycle. And it is possible to reduce the impact of a disruption at one hub on other hubs by isolating the hubs insofar as possible; hub isolation is zero hub connectivity which is the number of legs in a rotation that are in a route that begins at a hub and ends at a different hub. In fact, the aim of hub isolation and short cycles is to control the difficulty and scope of schedule recovery. However, limited hub isolation corresponds to a lower number of feasible schedule recovery solutions, while short cycles are associated with flight cancellations or longer delay times within the short cycles. The scope of schedule recovery is controlled within the short cycle, rather than by the AOCC controllers.Moreover, airline network structure has an important effect on flight operations recovery. In America, the AOCC controllers formulating flight operations recovery plans must consider passenger itineraries within a hub-and-spoke network structure. A hub-and-spoke network [19] means a system of connections arranged like a chariot wheel, in which all traffic moves along spokes connected to the hub at the center. However, passenger itineraries of domestic flights in China containing a single flight leg are in the majority, and the international flights accounted for about 9% of all flights in 2015 according to flights data from the Civil Aviation Administration of China. Further, international flights and domestic flights are different in aircraft type and crews, so there is little implication between international flights and domestic flights. Thus, we do not consider passenger itineraries in this study on domestic flights in China. What is more, multi-hub-and-spoke airlines are associated with multibase airlines in China. Therefore, the hub-and-spoke airlines have some advantages as regards options for schedule recovery from irregular operations.This article makes three new contributions compared to previous results. First, we describe more specifically the simplex group cycle approach and first present a feasible algorithm for aircraft and flight partitioning and a feasible algorithm to compute weighted value. Second, we use a weighted threshold to control the disruption scope and depth, computation time and recovery value for flight operations recovery for hub-and-spoke airlines. Hence, we describe the weighted time-band approximation model (WTBAM) for flight operations recovery using the simplex group cycle approach, referring to the concept of the time-band approximation model for flight operations recovery [12]. Third, we design some practical numerical experiments and the results demonstrate that use of the WTBAM incorporating the simplex group cycle is reasonable and feasible, and we provide first the feasible method to choose the weighted threshold α0. Furthermore, the results verify that the gap between the relaxed weighted time-band approximation model and the weighted time-band approximation model is zero under certain conditions. Finally, the results demonstrate that we can obtain a satisfactory recovery plan considering the flight disruption scope and depth, computation time and recovery value under some appropriate rules.The remainder of this paper is organized as follows. In Section2, we introduce some fundamental concepts, including important definitions and key aspects of the time-band approximation model. In Section 3, we present the mathematical formulations of the WTBAM. The model is then applied to actual data from two airlines and the computational results are presented in Section 4. In Section 5, the conclusions are presented with a brief discussion.


## 2. Fundamental Concepts

To construct the WTBAM, we first introduce several fundamental concepts.


### 2.1. Objective and Constraints

The objective of flight operations recovery is to make decisions that correspond to the lowest-cost response to restoring the disrupted schedule to the planned schedule. In this paper, we firstly consider flight departure delays or flight leg cancellations to repair a flight schedule after a disruption and subsequently assign individual aircraft to a new flight schedule by the method [32]. Moreover, considering the characteristics of multi-hub-and-spoke airlines in China, we have no considering maintenance base for the overnight restrictions in the process of assigning individual aircraft to a new flight schedule. In fact, the AOCC controllers customarily give priority to assign the same type aircraft, and in general there are a lot of the same type aircraft in the multi-hub-and-spoke airlines. Further, the different type of aircraft will bring about a series of problems, such as crew, airport, and maintenance; the AOCC controller has to make sure the aircraft routing is feasible. Therefore, the relaxation of maintenance base restrictions is one of the advantages for multi-hub-and-spoke airlines in China.Note that minimization of weighted delay costs and flight cancellation costs is a common objective. The delay costs include additional fuel expenses, overtime payments, further expenses associated with overtime payments when an aircraft is delayed in an airport, and passenger food expenses. Thus, delay costs are the direct costs incurred by flight delays, rather than associated costs that arise by chance. We consider the different weighted values of these costs in different simplex group cycles. In contrast, flight cancellation costs include loss of profit, passenger food and accommodation expenses, and passenger compensation. And flight cancellation costs were generated by the approximate estimation formulay=ax+b in this research, a is the number of passengers, x is a random number between 80 and 100 and generally includes meals and passenger compensation, and b is the approximate city accommodation cost. Further, the recovery plan must also satisfy the following constraints in order to be considered feasible. First, the turnaround time must be more than the minimum threshold, that is, 40 min. Second, every flight on each aircraft route must depart from the station at which the immediately preceding flight arrived. Finally, the aircraft balance necessary for the flight schedule to be resumed the next day must be achieved.


### 2.2. Simplex Group Cycle

The network of a multi-hub-and-spoke airline is comprised of two or more hub-and-spoke structures. Thus, multi-hub-and-spoke airlines have more maintenance bases and a greater number of feasible recovery plans. In fact, the group of flights between one or more hub-and-spoke systems in the same airline network is defined as belonging to a simplex group cycle and labelledSFs, where s denotes the specific simplex group cycle. Those flights are assigned to certain fixed aircraft, and the originating and destination cities contain one or more hub-and-spoke systems. Thus, each flight belongs to only one SFs. According to the definition of a simplex group cycle, a simplex group cycle partition for all aircraft can be determined, with each aircraft being assigned to one of various SAs groupings. The simplex group cycle approach and its superiority are shown in the following example.The Air China hub-and-spoke systems shown in the following flight schedule are Beijing (PEK), Shanghai (SHA), and Chengdou (CTU). The network comprised of the PEK, SHA, Xian (XIY), and CTU hubs is shown in Figure1.Figure 1
Air China flight network comprised of Beijing (PEK), Shanghai (SHA), Xian (XIY), and Chengdou (CTU) hubs.The flight schedule and aircraft assignments are shown in Table1. Thus, we can determine a partition based on the natural aircraft sequence. The first simplex group cycle is the set comprised of CA4193, CA4102, CA1216, CA1215, CA1945, CA1946, CA425, and CA1950, and the related aircraft are f1, f2, and f3. Thus, the second simplex group cycle is the set comprised of CA1203, CA1204, CA4107, CA4108, CA4201, and CA4202, with the related aircraft being f4 and f5.Table 1
Sample flight schedule and aircraft assignments.
FlightN TailN From To Dep.T Arr.T Ass. A C. cost CA4193 11 CTU PEK 7:00 9:30 f 1 , 321 11380 CA4102 12 PEK CTU 11:30 14:00 f 1 , 321 15150 CA1216 21 SHA PEK 8:00 10:00 f 2 , 321 12985 CA1215 22 PEK SHA 12:30 14:30 f 2 , 321 16991 CA1945 31 SHA CTU 8:05 10:35 f 3 , 321 11260 CA1946 32 CTU SHA 12:20 14:50 f 3 , 321 15785 CA425 33 SHA CTU 17:35 20:05 f 3 , 321 13031 CA1950 34 CTU SHA 21:00 23:30 f 3 , 321 13820 CA1203 41 PEK XIY 07:05 9:00 f 4 , 321 11650 CA1204 42 XIY PEK 10:00 11:55 f 4 , 321 10256 CA4107 51 CTU PEK 09:00 11:30 f 5 , 321 11000 CA4108 52 PEK CTU 15:00 17:30 f 5 , 321 15236 CA4201 53 CTU XIA 20:45 22:00 f 5 , 321 9325 CA4202 54 XIA CTU 23:00 00:15 f 5 , 321 9128 FlightN: flight number; Tail N: tail number; Dep. T: departure time; Arr. T: arrival time; Ass. A: assigned aircraft; C. cost: cancellation cost.The partitioning of the flights or aircraft is usually determined by the AOCC controllers, according to their empirical data and objectives. However, partitioning the flights or aircraft in a manner that establishes the optimalSFs groupings is a difficult problem. Therefore, we first present a feasible algorithm for aircraft and flight partitioning in Algorithm 1.Algorithm 1:Simplex group cycle partitioning (SGCP) algorithm (S Algorithm).
Input:F = Original flight schedule Aircraft = All the executive aircraft associated with the flights Output: Airport = An ordered list of all airports according to the number of related flights SAs = The aircraft group in simplex group cycle s SFs = The flight group in simplex group cycle s begin for each airportλi Count the related flightsFλi mark(λi)=Fλi; Sortλi according to Fλi; end    /According to the node degree at the airport-flight adjacency graph, we sort the airport from large to small./ j=m0;     /where m0 is the approximate simplex group cycle number/ TA=SAm0 = The related aircraft in airport λm0; fori=1:j SAj-i = The related aircraft in airport λj-i SAj-i=SAj-i-TA; /Ensure that each aircraft is in the only one SAi/ TA=SAj-i∪TA; i++; end if(TA≠Aircraft); SAj+1 = The related aircraft in airport λj+1 SAj+1=SAj+1-TA; TA=SAj+1∪TA;   j=j+1; else outputSAs,s∈S=1,2,…,j. end outputSFs,s∈S, SF = The flight group comprised of all flights in all simplex group cycles; end


### 2.3. Weighted Set and Potential Disruption Set

When disruptions occur in a hub-and-spoke network, they may lead to a large amount of disruptions overall. Thus, schedule recovery should be accomplished in the most economic manner. However, if we only consider the flights themselves, the disruptions may have a negative influence on passengers. Therefore, in order to control the potential disruption scopeFs in a hub-and-spoke network and the associated negative influence on passengers, Fs can be determined based on the flight disruption scope and depth, the computation time, and the recovery value. Therefore, we employ the concept of a weighted set, as explained below.LetS∗ be the set containing the simplex group cycle s which is at least one schedule disruption in s∈S. And let SA be the aircraft partition related to S, the set of all simplex group cycles. Then SA∗ is the aircraft partition related to S∗.Definition 1.
When a disruption occurs, the weighted value is denoted(2)wj=∑i∈SA∗wij,j∉SA∗,1,j∈SA∗.When the flights of theith simplex group cycle influence those of the jth simplex group cycle, the value of wij can usually be assigned by the AOCC controllers in accordance with their empirical data and objectives. Naturally, we define wii=1, ∀i∈S, and wij=β(1+ATSAj/ATSAi), ∀i,j∈S. Here, β is the amplification coefficient, and ATSAi and ATSAj are the average available flight times of each SAi and SAj, respectively. Then, the weighted set W={wj,∀j∈S}.The simplex group cycle approach can exploit the advantages provided by a multi-hub-and-spoke network. For example, in Table1, when aircraft f1 (CA4193) departed from CTU arrived in PEK, the maintenance personnel detected mechanical problems. It was estimated that a period of 4 h was required to complete the repairs. Thus, using the simplex group cycle approach, we utilize f2 to execute flight CA4102, followed by flight CA1950, with f3 being utilized for flights CA1945 and CA1946. At 13:30, f1 then executes flights CA1215 and CA425. The total delay time is 100 min, and we save 60 min. Note that only the disruption scope is controlled by the simplex group cycle approach. In addition, the developed recovery plan involved cooperation between China Airlines (f2,f3) and its branch company, China Southwest Airlines (f1).Based on a weighted thresholdα0, AOCC airline controllers can obtain a potential disrupted set PDFSα0, which is defined as follows.Definition 2.
The potential disrupted flights setPDFSα0 is the set of flights in the simplex group cycle s obtained when the condition ws≤α0, ∀s∈S, is satisfied.Hence, the AOCC airline controllers can set the potential disruption flightsPDFSα0 conveniently by considering the value of α0. However, it is difficult to compute the wij values for flights or aircraft. Therefore, a feasible algorithm to compute W and PDFSα0 is first given in Algorithm 2. The time-band network incorporating PDFSα0 is constructed using the time-band network transformation procedure found in [11, 12]. The time-band network mainly consists of station-time nodes, station-sink nodes, and flight arcs, so we refer to some concepts of the literature [11, 12] in the followingFlight arcs: arcs representing specific scheduled flights.Station-time nodes: nodes representing aggregate activity for a specific time segment at a station.Station-sink nodes: nodes representing the end of the recovery period at stations.Algorithm 2:Weighted set and potential disruption flights set (PDFSα0) algorithm (W Algorithm).
Input:SA,SF Output:W, potential disrupted aircraft set PDASα0 and PDFSα0 begin for eachSAi compute the average available flight time(ATSAi) in the SAi; /SAi is the set of aircraft in the simplex group cycle i,i∈S./ end for each simplex group cycleSAii∈S∗ for each simplex group cycleSAjj∈S compute w i j = β 1 + A T S A j A T S A i j ≠ i 1 j = i end end  /SA is the aircraft partition related to S. SA∗ is the aircraft partition related to S∗./ for eachSAj,∀j∈S. compute w j = ∑ i ∈ S A ∗ ‍ w i j j ∉ S ∗ 1 j ∈ S ∗ end W = ( w 1 , w 2 , … , w | S | ) T; W S A = ( w 1 , … , w 1 ︷ | S A 1 | , w 2 , … , w 2 ︷ | S A 2 | , … , w | S | , … , w | S | ︷ | S A | S | | ) T; PDASα0=∅;PDFSα0=∅; fori=1:|S| ifwi≤α0;/α0 is the threshold./ PDASα0=PDASα0∪SAi;  PDFSα0=PDFSα0∪SFi; end end endSubsequently all the possible delay costs for the flight arcs can be computed by considering the difference between the real takeoff time and the scheduled plan in the time-band network. Naturally, the WTBAM is constructed in accordance with the optimization model by considering a series of flight arcs with some potential flight delays. In the next section, we present the mathematical formulation of the time-band approximation model.


## 2.1. Objective and Constraints

The objective of flight operations recovery is to make decisions that correspond to the lowest-cost response to restoring the disrupted schedule to the planned schedule. In this paper, we firstly consider flight departure delays or flight leg cancellations to repair a flight schedule after a disruption and subsequently assign individual aircraft to a new flight schedule by the method [32]. Moreover, considering the characteristics of multi-hub-and-spoke airlines in China, we have no considering maintenance base for the overnight restrictions in the process of assigning individual aircraft to a new flight schedule. In fact, the AOCC controllers customarily give priority to assign the same type aircraft, and in general there are a lot of the same type aircraft in the multi-hub-and-spoke airlines. Further, the different type of aircraft will bring about a series of problems, such as crew, airport, and maintenance; the AOCC controller has to make sure the aircraft routing is feasible. Therefore, the relaxation of maintenance base restrictions is one of the advantages for multi-hub-and-spoke airlines in China.Note that minimization of weighted delay costs and flight cancellation costs is a common objective. The delay costs include additional fuel expenses, overtime payments, further expenses associated with overtime payments when an aircraft is delayed in an airport, and passenger food expenses. Thus, delay costs are the direct costs incurred by flight delays, rather than associated costs that arise by chance. We consider the different weighted values of these costs in different simplex group cycles. In contrast, flight cancellation costs include loss of profit, passenger food and accommodation expenses, and passenger compensation. And flight cancellation costs were generated by the approximate estimation formulay=ax+b in this research, a is the number of passengers, x is a random number between 80 and 100 and generally includes meals and passenger compensation, and b is the approximate city accommodation cost. Further, the recovery plan must also satisfy the following constraints in order to be considered feasible. First, the turnaround time must be more than the minimum threshold, that is, 40 min. Second, every flight on each aircraft route must depart from the station at which the immediately preceding flight arrived. Finally, the aircraft balance necessary for the flight schedule to be resumed the next day must be achieved.


## 2.2. Simplex Group Cycle

The network of a multi-hub-and-spoke airline is comprised of two or more hub-and-spoke structures. Thus, multi-hub-and-spoke airlines have more maintenance bases and a greater number of feasible recovery plans. In fact, the group of flights between one or more hub-and-spoke systems in the same airline network is defined as belonging to a simplex group cycle and labelledSFs, where s denotes the specific simplex group cycle. Those flights are assigned to certain fixed aircraft, and the originating and destination cities contain one or more hub-and-spoke systems. Thus, each flight belongs to only one SFs. According to the definition of a simplex group cycle, a simplex group cycle partition for all aircraft can be determined, with each aircraft being assigned to one of various SAs groupings. The simplex group cycle approach and its superiority are shown in the following example.The Air China hub-and-spoke systems shown in the following flight schedule are Beijing (PEK), Shanghai (SHA), and Chengdou (CTU). The network comprised of the PEK, SHA, Xian (XIY), and CTU hubs is shown in Figure1.Figure 1
Air China flight network comprised of Beijing (PEK), Shanghai (SHA), Xian (XIY), and Chengdou (CTU) hubs.The flight schedule and aircraft assignments are shown in Table1. Thus, we can determine a partition based on the natural aircraft sequence. The first simplex group cycle is the set comprised of CA4193, CA4102, CA1216, CA1215, CA1945, CA1946, CA425, and CA1950, and the related aircraft are f1, f2, and f3. Thus, the second simplex group cycle is the set comprised of CA1203, CA1204, CA4107, CA4108, CA4201, and CA4202, with the related aircraft being f4 and f5.Table 1
Sample flight schedule and aircraft assignments.
FlightN TailN From To Dep.T Arr.T Ass. A C. cost CA4193 11 CTU PEK 7:00 9:30 f 1 , 321 11380 CA4102 12 PEK CTU 11:30 14:00 f 1 , 321 15150 CA1216 21 SHA PEK 8:00 10:00 f 2 , 321 12985 CA1215 22 PEK SHA 12:30 14:30 f 2 , 321 16991 CA1945 31 SHA CTU 8:05 10:35 f 3 , 321 11260 CA1946 32 CTU SHA 12:20 14:50 f 3 , 321 15785 CA425 33 SHA CTU 17:35 20:05 f 3 , 321 13031 CA1950 34 CTU SHA 21:00 23:30 f 3 , 321 13820 CA1203 41 PEK XIY 07:05 9:00 f 4 , 321 11650 CA1204 42 XIY PEK 10:00 11:55 f 4 , 321 10256 CA4107 51 CTU PEK 09:00 11:30 f 5 , 321 11000 CA4108 52 PEK CTU 15:00 17:30 f 5 , 321 15236 CA4201 53 CTU XIA 20:45 22:00 f 5 , 321 9325 CA4202 54 XIA CTU 23:00 00:15 f 5 , 321 9128 FlightN: flight number; Tail N: tail number; Dep. T: departure time; Arr. T: arrival time; Ass. A: assigned aircraft; C. cost: cancellation cost.The partitioning of the flights or aircraft is usually determined by the AOCC controllers, according to their empirical data and objectives. However, partitioning the flights or aircraft in a manner that establishes the optimalSFs groupings is a difficult problem. Therefore, we first present a feasible algorithm for aircraft and flight partitioning in Algorithm 1.Algorithm 1:Simplex group cycle partitioning (SGCP) algorithm (S Algorithm).
Input:F = Original flight schedule Aircraft = All the executive aircraft associated with the flights Output: Airport = An ordered list of all airports according to the number of related flights SAs = The aircraft group in simplex group cycle s SFs = The flight group in simplex group cycle s begin for each airportλi Count the related flightsFλi mark(λi)=Fλi; Sortλi according to Fλi; end    /According to the node degree at the airport-flight adjacency graph, we sort the airport from large to small./ j=m0;     /where m0 is the approximate simplex group cycle number/ TA=SAm0 = The related aircraft in airport λm0; fori=1:j SAj-i = The related aircraft in airport λj-i SAj-i=SAj-i-TA; /Ensure that each aircraft is in the only one SAi/ TA=SAj-i∪TA; i++; end if(TA≠Aircraft); SAj+1 = The related aircraft in airport λj+1 SAj+1=SAj+1-TA; TA=SAj+1∪TA;   j=j+1; else outputSAs,s∈S=1,2,…,j. end outputSFs,s∈S, SF = The flight group comprised of all flights in all simplex group cycles; end


## 2.3. Weighted Set and Potential Disruption Set

When disruptions occur in a hub-and-spoke network, they may lead to a large amount of disruptions overall. Thus, schedule recovery should be accomplished in the most economic manner. However, if we only consider the flights themselves, the disruptions may have a negative influence on passengers. Therefore, in order to control the potential disruption scopeFs in a hub-and-spoke network and the associated negative influence on passengers, Fs can be determined based on the flight disruption scope and depth, the computation time, and the recovery value. Therefore, we employ the concept of a weighted set, as explained below.LetS∗ be the set containing the simplex group cycle s which is at least one schedule disruption in s∈S. And let SA be the aircraft partition related to S, the set of all simplex group cycles. Then SA∗ is the aircraft partition related to S∗.Definition 1.
When a disruption occurs, the weighted value is denoted(2)wj=∑i∈SA∗wij,j∉SA∗,1,j∈SA∗.When the flights of theith simplex group cycle influence those of the jth simplex group cycle, the value of wij can usually be assigned by the AOCC controllers in accordance with their empirical data and objectives. Naturally, we define wii=1, ∀i∈S, and wij=β(1+ATSAj/ATSAi), ∀i,j∈S. Here, β is the amplification coefficient, and ATSAi and ATSAj are the average available flight times of each SAi and SAj, respectively. Then, the weighted set W={wj,∀j∈S}.The simplex group cycle approach can exploit the advantages provided by a multi-hub-and-spoke network. For example, in Table1, when aircraft f1 (CA4193) departed from CTU arrived in PEK, the maintenance personnel detected mechanical problems. It was estimated that a period of 4 h was required to complete the repairs. Thus, using the simplex group cycle approach, we utilize f2 to execute flight CA4102, followed by flight CA1950, with f3 being utilized for flights CA1945 and CA1946. At 13:30, f1 then executes flights CA1215 and CA425. The total delay time is 100 min, and we save 60 min. Note that only the disruption scope is controlled by the simplex group cycle approach. In addition, the developed recovery plan involved cooperation between China Airlines (f2,f3) and its branch company, China Southwest Airlines (f1).Based on a weighted thresholdα0, AOCC airline controllers can obtain a potential disrupted set PDFSα0, which is defined as follows.Definition 2.
The potential disrupted flights setPDFSα0 is the set of flights in the simplex group cycle s obtained when the condition ws≤α0, ∀s∈S, is satisfied.Hence, the AOCC airline controllers can set the potential disruption flightsPDFSα0 conveniently by considering the value of α0. However, it is difficult to compute the wij values for flights or aircraft. Therefore, a feasible algorithm to compute W and PDFSα0 is first given in Algorithm 2. The time-band network incorporating PDFSα0 is constructed using the time-band network transformation procedure found in [11, 12]. The time-band network mainly consists of station-time nodes, station-sink nodes, and flight arcs, so we refer to some concepts of the literature [11, 12] in the followingFlight arcs: arcs representing specific scheduled flights.Station-time nodes: nodes representing aggregate activity for a specific time segment at a station.Station-sink nodes: nodes representing the end of the recovery period at stations.Algorithm 2:Weighted set and potential disruption flights set (PDFSα0) algorithm (W Algorithm).
Input:SA,SF Output:W, potential disrupted aircraft set PDASα0 and PDFSα0 begin for eachSAi compute the average available flight time(ATSAi) in the SAi; /SAi is the set of aircraft in the simplex group cycle i,i∈S./ end for each simplex group cycleSAii∈S∗ for each simplex group cycleSAjj∈S compute w i j = β 1 + A T S A j A T S A i j ≠ i 1 j = i end end  /SA is the aircraft partition related to S. SA∗ is the aircraft partition related to S∗./ for eachSAj,∀j∈S. compute w j = ∑ i ∈ S A ∗ ‍ w i j j ∉ S ∗ 1 j ∈ S ∗ end W = ( w 1 , w 2 , … , w | S | ) T; W S A = ( w 1 , … , w 1 ︷ | S A 1 | , w 2 , … , w 2 ︷ | S A 2 | , … , w | S | , … , w | S | ︷ | S A | S | | ) T; PDASα0=∅;PDFSα0=∅; fori=1:|S| ifwi≤α0;/α0 is the threshold./ PDASα0=PDASα0∪SAi;  PDFSα0=PDFSα0∪SFi; end end endSubsequently all the possible delay costs for the flight arcs can be computed by considering the difference between the real takeoff time and the scheduled plan in the time-band network. Naturally, the WTBAM is constructed in accordance with the optimization model by considering a series of flight arcs with some potential flight delays. In the next section, we present the mathematical formulation of the time-band approximation model.


## 3. Time-Band Approximation Model Mathematical Formulation

In order to construct the mathematical formulation of the optimization model, some indices, sets, parameters, and variables are employed, which are given in Nomenclature.Usingα0 and considering the recovery plan for PDFSα0 only, we can express the WTBA approximation model as follows:(3)minFα0x,y,z=∑k∈PDFSα0∑i∈Pk∑j∈Hk,iwijkdijkxijk+∑k∈PDFSα0wkckyk,(4)subjectto∑i∈Pk∑j∈Hk,ixijk+yk=1,∀k∈PDFSα0,(5)∑k∈Gi∑j∈Hk,ixijk+zi-∑k∈Ni∑j∈Mk,ixijk=aiα0,∀i∈I,k∈PDFSα0,(6)∑k∈Ni∑j∈Mk,ixjik+∑j∈Qizj=hiα0,∀i∈J,k∈PDFSα0,(7)xijk∈0,1,k∈PDFSα0,i∈I,j∈Hk,i,(8)yk∈0,1,k∈PDFSα0,(9)zi∈Z+,i∈I.The objective function (3) minimizes the delay and cancellation costs for PDFSα0. Constraint (4) shows that all flights in the simplex group cycle must be operated or cancelled. Further, constraint (5) satisfies the aircraft utilization requirement at the station-time node. The station-sink node flow constraint (6) enforces aircraft balance. The binary xijk and yk ensure that a flight can only be operated or cancelled; that is, it must not be partially serviced and then cancelled. The possible arcs must be integrated, which is enforced by constraint (9).Remark 3.
Whenα0=1, the solution of WTBAM is obtained after searching the flights in S∗, and the passengers affected by this solution may experience long flights, or some flights in the simplex group cycle may be cancelled. In other words, the disruption scope can be controlled in the simplex group cycle S∗, but the disruption depth may be very large.
In contrast to the optimization model withα0≥1, the objective function and constraints in the model can be modified by k∈SFS∗. In this optimization model, PDFSα0 is restricted to the disrupted flight set SFS∗ only. We can obtain the optimization model with WS∗=1, as follows:(10)minfS∗x,y,z=∑s∈S∗∑k∈SFs∑i∈Pk∑j∈Hk,idijkxijk+ckyk,(11)subjectto∑i∈Pk∑j∈Hk,ixijk+yk=1,∀k∈SFS∗,(12)∑k∈Gi∑j∈Hk,ixijk+zi-∑k∈Ni∑j∈Mk,ixijk=ai1,∀i∈I,k∈SFS∗,(13)∑k∈Ni∑j∈Mk,ixjik+∑j∈Qizj=hi1,∀i∈J,k∈SFS∗,(14)xijk∈0,1,k∈SFS∗,i∈I,j∈Hk,i,(15)yk∈0,1,k∈SFS∗,(16)zi∈Z+,i∈I.The objective function (10) minimizes the delay costs and the cancellation costs in S∗. Further, constraint (11) shows that all flights in ⋃s∈S∗SFs must be operated or cancelled. Constraint (12) satisfies the aircraft utilization requirement for ⋃s∈S∗SFs at the station-time node. The station-sink node flow constraint (13) enforces aircraft balance in ⋃s∈S∗SFs. The binary xijk and yk ensure that a flight can only be operated or cancelled; that is, it must not be partially serviced and then cancelled. Finally, the copy arcs must be integrated, which is enforced by constraint (16).Remark 4.
Whenα0 has the maximum weighted value αsup, Fs corresponds to all of the flights. In that case, it may be very difficult for the AOCC to quickly obtain the optimal solution or the disrupted flight scope may be very broad. It may be very difficult to implement such a recovery plan for actual flight production, because it does not satisfy the requirements of timeliness and balance between the disruption scope, disruption depth, and recovery value.
For1≤α0≤αsup, it is difficult for the AOCC to determine the optimal α0 that satisfies the balance between the passenger and airline requirements. However, the AOCC can choose the best satisfactory value under those conditions.Remark 5.
When a disruption occurs, the weighted value is given out by theW Algorithm, Then (17)wijk=wk=ws,wherews∣∃s∈S,s.t.k∈PDFSαsup.Proof.
Because all the flights are contained withinPDFSαsup=⋃s∈SSFs, when i≠j, SFi≠SFj, ∀i,j∈S. Therefore, we can obtain (18)∃s∈S,s.t.k∈PDFSαsup.In fact, zi must be less than or equal to the total number of aircraft ∑s∈S‍SAs. And then the linear programming relaxation of the weighted time-band approximation model (LPRWTBAM) is expressed as follows:(19)minfα0x,y,z=∑k∈PDFSα0∑i∈Pk∑j∈Hk,iwijkdijkxijk+wkckyk,(20)subjectto∑i∈Pk∑j∈Hk,ixijk+yk=1,∀k∈PDFSα0,(21)∑k∈Gi∑j∈Hk,ixijk+zi-∑k∈Ni∑j∈Mk,ixijk=aiα0,∀i∈I,k∈PDFSα0,(22)∑k∈Ni∑j∈Mk,ixjik+∑j∈Qizj=hiα0,∀i∈J,k∈PDFSα0,(23)xijk∈0,1,k∈PDFSα0,i∈I,j∈Hk,i,(24)yk∈0,1,k∈PDFSα0,(25)zi∈0,∑s∈SSAs,i∈I.
Naturally,wijkdijk≥0 and wkck≥0, ∀i∈I, j∈H(k,i), k∈PDFSα0. We can set (26)I0,J0,K0=i0,j0,k0∣wi0j0k0di0j0k0>0,i0∈I,j0∈Hk0,i0,k0∈PDFSα0,K1=k1∣wk1ck1>0,k1∈PDFSα0.Further, we assume that wijkdijk and wkck satisfy the following properties.
Well-Ordered Property. The nonzero value coefficient set (NVCS)(27)wijkdijk,∀i,j,k∈I0,J0,K0∪wkck,∀k∈K1is well ordered according to <.
In fact, the weighted value, delayed time, and cancellation cost are often different in the NVCS; therefore, the following sequence properties may be satisfied in most cases(28)w000d000<w000d001<⋯<w010d010<w011d011<⋯<wI0J0K0dI0J0K0,i,j,k∈I0,J0,K0,w0c0<w1c1<⋯<wK1cK1,k∈K1.Naturally, the NVCS frequently exhibits a well-ordered property.
LetF0k be the number of elements in the F0k set. Then, we can obtain the following property in the majority of cases.
Possible Zero Property. F0k=0 or 1, F0k={(i,j,k)∣wijkdijk=0}, ∀k∈PDFSα0. In fact, when there is only a small number of available aircraft in i∈P(k), the aircraft utilization is generally reasonably high and flights cannot take off early; then F0k=0 or 1 often occurs.Remark 6.
If the feasible solution of WTBAM is nonempty,aiα0 and hiα0 are integers, and NVCS exhibits a well-ordered property, then F0k has the possible zero property, ∀k∈PDFSα0, i∈P(k). Then, the WTBAM and LPRWTBAM solutions are identical.Proof.
Let(xlp∗,ylp∗,zlp∗)T be the LPRWTBAM solution and (x∗,y∗,z∗)T be the WTBAM solution. Then, because the LPRWTBAM is the relaxed WTBAM, (29)fxlp∗,ylp∗,zlp∗≤fx∗,y∗,z∗.If (xlp∗,ylp∗,zlp∗)T is an integer, then(30)x∗,y∗,z∗T=xlp∗,ylp∗,zlp∗T.The analysis of (xlp∗,ylp∗,zlp∗)T is as follows.
WhenF0k=0 or 1, ∀k∈PDFSα0, we adopt the assumption (31)∃i,j,k0,s.t.wijk0dijk0=0.Then wijk0dijk0∪NVCS is well ordered. According to xijk∈[0,1], yk∈[0,1], zi∈[0,M0], i∈I, (19), and (20), we can obtain(32)xijk=0,1,yk=0,1,∀k∈PDFSα0.Furthermore, according to (21) and (22) and as aiα0 and hiα0 are integers, we know that zi={0,1,…,M0}, where M0 is an integer. Finally, we conclude that (xlp∗,ylp∗,zlp∗)T is an integer.


## 4. Computational Results

Two sets of computational results are presented in this section: (i) the computational results obtained by application of the WTBAM to the sample data given in Table1, which demonstrate that use of the WTBAM incorporating the simplex group cycle is reasonable and feasible; (ii) results of a test using data from actual aircraft belonging to Sichuan Airlines in China, which involves a hub-and-spoke network. The analysis results obtained for different weighted thresholds and different simplex group cycles under four scenarios are given.


### 4.1. Sample Flight Schedule Table1

Mechanical problems are detected for aircraftf1 at 9:50, and it is estimated that a 4-h period is required for the repair work. In this example, the time band is set to half an hour and the schedule recovery is implemented from 10:00 to 02:00 the next day. In this example, the simplex group cycle partitions are set to S1 and S2, in order to show the AOCC controllability. Note that these partitions do not correspond to the partition implemented using the simplex group cycle procedure. The weighted value W2=1.9 is determined according to the weighted set procedure. We set the disruption threshold α0=2.0; then the potential disruption flights set PDFS2.0 is as shown in Table 2.Table 2
Flight schedule and aircraft assignments forPDFS2.0.
TailN From To Dep.T Arr.T Ass. A C. Cost 12 PEK CTU 11:30 14:00 f 1 , 321 15150 22 PEK SHA 12:30 14:30 f 2 , 321 16991 32 CTU SHA 12:20 14:50 f 3 , 321 15785 33 SHA CTU 17:35 20:05 f 3 , 321 13031 34 CTU SHA 21:00 23:30 f 3 , 321 13820 42 XIY PEK 10:00 11:55 f 4 , 321 10256 52 PEK CTU 15:00 17:30 f 5 , 321 15236 53 CTU XIY 20:45 22:00 f 5 , 321 9325 54 XIY CTU 23:00 00:15 f 5 , 321 9128Subsequently, the flight arc delay costs for the recovery problem are determined using the time-band transformation network [12]. The time-band transformation contains 26 nodes and 57 flight arcs. The delay cost for each flight arc is calculated according to the arc delay, and a 20-per-min delay cost function is assumed [12] in this paper. The nonzero flight arc delay costs for α0=1.0 and 2.0 are listed in Tables 3 and 4, respectively. Finally, we can compute the WTBAM solution using Lingo 14.0. The solutions for α0=1.0 and 2.0 are listed in Tables 5 and 6, respectively. The results obtained for the time-band transformation with α0=2.0 contain more nodes and flight arcs than that for α0=1.0; therefore, the WTBAM solution (with α0=2.0) may yield a superior proximal point than the standard time-band transformation with α0=1.0. Further, the optimal value yielded by the WTBAM is smaller than that for the time-band transformation with α0=1.0.Table 3
Nonzero flight arc delay costs with disruption thresholdα0=1.0.
TailN Origin node Destination node Arc delay cost 12 3 7 3000 21 3 6 1800 32 4 8 3200 32 7 9 6200 32 10 14 10400 32 11 14 11600 33 8 11 1100 33 9 13 4100 34 11 14 1200Table 4
Nonzero flight arc delay costs with disruption thresholdα0=2.0.
TailN Origin node Destination node w i j k ∗  arc delay cost 12 4 10 1200 12 5 11 1800 12 6 13 1800 22 5 9 600 22 6 12 3420 32 7 14 3200 32 10 16 4400 32 11 17 5000 32 13 18 6200 32 15 20 7400 32 19 27 10400 32 21 27 11600 32 22 27 12800 32 24 27 14000 33 14 21 1100 33 16 22 2300 33 17 24 2900 33 18 26 4100 33 20 29 5300 34 21 27 1200 34 22 27 2400 34 24 27 3600 42 23 28 29640 42 25 28 31920 53 19 23 570 53 21 25 1800 53 22 30 5130 53 24 30 6270 53 26 30 8550 54 25 29 2280Table 5
Results forα0=1.0.
min ⁡ ⁡ z = 15785 h 1 = h 2 = h 3 = 1 TailN From To OST node DST node Ass. A D. cost C. cost  12 PEK CTU 2 4 f 2 0 — 21 PEK SHA 1 5 f 3 0 — 32 CTU SHA — — — — 15758 33 SHA CTU 5 10 f 3 0 — 34 CTU SHA 4 14 f 2 0 — OST: origin station-time; DST: destination station-time; D. cost: delay cost.Table 6
Results forα0=2.0.
min ⁡ z = 0 h 1 = 2 ,   h 2 = 1 ,   h 3 = 2 ,   h 4 = 0 TailN From To OST node DST node Ass. A D. cost C. cost  12 PEK CTU 2 7 f 2 0 — 22 PEK SHA 4 8 f 5 0 — 32 CTU SHA 3 8 f 3 0 — 33 SHA CTU 8 19 f 3 0 — 34 CTU SHA 19 27 f 1 0 — 42 XIY PEK 1 5 f 4 0 — 52 PEK CTU 6 15 f 1 0 — 53 CTU XIY 15 23 f 2 0 — 54 XIY CTU 23 29 f 2 0 —


### 4.2. Stochastic Experiments

Our model was also tested using actual data obtained for a specific day in 2015, for a hub-and-spoke airline network under Sichuan Airlines having approximately 254 daily flights. The WTBAM was implemented in C++ using CPLEX 12.3 on a Lenovo notebook with a 2.16-GHz processor. As the arrival time of the disrupted flight was 02:30 on the next day and recovery time interval should contain all the flight schedule, we set the schedule recovery from 07:00 to 03:00 on the next day and the time band to 5 min in order to reduce the gap bound. Then, 1–4 aircraft having mechanical problems or some issue prohibiting them from use between 07:00 to 03:00 on the next day were randomly generated; these events were labelled scenarios 1–4. Combined with the experience of AOCC, the simplex group cycle should not be very large but should not be very small, 60 aircraft in the actual data, roughly divided into 6–15 group. If the simplex group cycle is very large, it may lead to the fact that the calculation time of optimal solution is too long and the potential disruption scope is too large, while if it is too small it may lead to a large potential disruption depth. So we obtain the 7, 12, and 15 three simplex group cycles by settingm0=5,10,12 in the S Algorithm. Subsequently, three simplex group cycle partitions are listed in Tables 7–9, and due to the limit of table length, only apart results of WTBAM under these partitions and different disruption thresholds are listed in Tables 12–15. In addition, the results for the simplex group cycle partitions, the scenarios, and the weighted values are presented in Figure 2.Table 7
First simplex group cycle partition.
SGCN TailN S 1 16 17 18 21 31 32 33 35 39 42 S 2 1 22 25 26 27 30 38 48 52 54 55 57 60 S 3 2 3 8 9 10 11 34 40 41 43 44 S 4 29 36 37 47 49 53 S 5 5 6 15 20 56 58 59 S 6 4 7 12 19 23 24 46 S 7 13 14 28 45 50 51 SGCN: Simplex group cycle number.Table 8
Second simplex group cycle partition.
SGCN TailN S 1 17 18 32 35 39 42 S 2 22 25 26 38 57 S 3 2 8 9 10 11 34 40 41 S 4 29 36 37 49 53 S 5 5 6 15 20 56 59 S 6 12 23 24 46 S 7 27 43 52 58 S 8 1 30 33 47 48 S 9 13 14 28 45 50 51 S 10 3 16 44 55 60 S 11 4 19 21 S 12 7 31 54Table 9
Third simplex group cycle partition.
SGCN TailN S 1 18 32 35 39 42 S 2 22 25 26 38 S 3 2 8 9 10 11 34 40 41 S 4 29 36 37 49 S 5 5 6 15 20 56 59 S 6 23 24 S 7 43 58 S 8 1 30 47 48 S 9 14 28 45 51 S 10 3 16 44 55 60 S 11 4 19 21 S 12 7 31 54 S 13 12 46 50 S 14 13 52 57 S 15 15 17 27 53Figure 2
Weighted value under different scenarios.
(a)
Weighted value under scenario 1 (b)
Weighted value under scenario 2 (c)
Weighted value under scenario 3 (d)
Weighted value under scenario 4Note that DT 60, DT 30, DT 15, and DT 0 indicate that the flight delay time is more than 60 min, between 30 min and 60 min, between 15 min and 30 min, and between 0 min and 15 min, respectively. Further, GTSN time (s) represents the time required to generate the time-space network in seconds, while CPU time represents the WTBAM calculation time.Comparison of the data in Tables12–15 leads to the conclusion that the potential disruption scope Fs, GTSN time, and CPU time increase with increased α0. Subsequently, by the results in Tables 12–15, we can obtain that GTSN time, CPU time, and potential disruption scope Fs satisfy the function in Table 11 and Figure 3. With the increase of Fs, GTSN time and CPU time are exponential growth and the function relationship is 10ax+b,a>0,b∈R,R is the real set. In view of this test, GTSN time and CPU time of second simplex group cycle partitions are generally better than the other simplex group cycle partitions. Note that GTSNij and CPUij indicate the function of GTSN time and potential disruption scope Fs in the case of scenario i and jth simplex group cycle partitions, i=1,2,3,4 and j=1,2,3.Figure 3
CPU Ttme and GTSN time under different scenarios.However, the optimal integer solution primarily decreases with increasedα0, and the gap between the optimal integer and the optimization solution is zero in the examples. Further, when the optimal integer reaches a certain level, it does not necessarily decrease or decreases only slightly, in most cases. These results show that a larger Fs is not necessarily better. In fact, the real extent of the flight disruption decreases with increased α0; however, note that this factor, disruption scope, and depth do increase with increased α0 in some cases. Further, the nodes and flight arcs increase with increased α0, along with the CPLEX 12.3 computational time.The AOCC controllers can choose the value ofα0 by considering the balance between the real flight disruption scope and depth, the CPU time, and the optimal integer value. Subsequently, we first introduce the feasible method to choose the value of α0 (Choose Method) in the following. The AOCC controllers choose the appropriate value of α0 which should be consistent with the four rules in the following.Choose Method The first rule is to meet the time limit for flight operations recovery. The second rule is about the flight recovery value in the following formula. Letf∗ be minf1∗,f2∗, α0∗ be the corresponding threshold of f∗, and α0i be the corresponding threshold of fi∗,i=1,2. (33)α0=α0∗f1∗-f2∗f∗>γ,α01orα02otherwise. The third rule is as small as possible to the impact of disruption flights scope and depth. The fourth rule is to ensure the uniqueness flight recovery plan. If there are two flight recovery plans to meet the previous three rules, then select a smaller flight recovery value. And if the flight recovery value is also the same, then select the CPU time which is less than that of the flight recovery plan.In this paper, we chooseγ=0.25 which means that the two flight recovery plans can be considered as equivalent when the difference ratio of the two flight recovery values is less than or equal to 0.25, because the AOCC controllers are not just considering about flight recovery values. The airlines can adjust γ to meet their management objectives. Subsequently, we provide a feasible method to measure the impact of disruption flights scope and depth according to the actual situation in China. Firstly, the weighted value of common delay time band is determined by the AOCC controllers, and then we calculate the total impact value. The delay time band and the weighted value are given out in Table 10. In particular, the weighted value can be adjusted according to the requirements of the airlines.Table 10
The impact of disruption flights scope and depth.
Delay time band DT 0 DT 15 DT 30 DT 60 Cancelled flight Weighted value 1 2 4 6 8Table 11
Functions for different simplex group cycle partitions and potential disruption scope.
First SGP Second SGP Third SGP First SGP Second SGP Third SGP Scenario 1 Scenario 2  GTSN 1 0 2.30 x + 0.82 1 0 2.97 x - 0.01 1 0 3.28 x + 0.03 1 0 2.53 x + 0.55 1 0 2.53 x + 0.16 1 0 2.98 x + 0.18 CPU 1 0 2.20 x + 0.99 1 0 2.76 x + 0.26 1 0 2.97 x + 0.34 1 0 2.43 x + 0.72 1 0 2.33 x + 0.44 1 0 2.74 x + 0.47  Scenario 3 Scenario 4  GTSN 1 0 2.26 x + 0.79 1 0 1.82 x + 1.16 1 0 2.56 x + 0.51 1 0 2.90 x + 0.08 1 0 2.27 x + 0.47 1 0 2.60 x + 0.41 CPU 1 0 2.12 x + 1.02 1 0 1.76 x + 1.29 1 0 2.39 x + 0.74 1 0 2.73 x + 0.33 1 0 2.12 x + 0.73 1 0 2.45 x + 0.64 x : F s.Table 12
Results for different simplex group cycle partitions and weighted thresholds under scenario 1.
α 0 First simplex group cycle partition Second simplex group cycle partition Third simplex group cycle partition 1 2.1 2.5 2.6 2.7 1 2.27 2.7 2.87 3.3 1 2.5 3.1 3.2 4.1 F s 16.5% 38.1% 63.3% 88.1% 100% 8.6% 22.4% 46.8% 75.9% 100% 7.0% 24.8% 42.9% 50.3% 100% DT 60 6 6 8 6 6 3 2 0 0 0 3 2 0 0 0 DT 30 1 1 0 0 0 7 8 9 6 6 7 8 6 3 3 DT 15 1 1 0 0 0 1 1 0 0 0 1 1 2 1 1 DT 0 1 0 1 3 3 1 2 2 3 2 1 3 4 6 6 Nodes 1953 6408 11634 14314 15137 679 1965 4599 7091 15137 489 1998 5803 7331 15137 Flight arcs 3877 13903 32606 44636 49439 1064 3516 10331 21364 49439 738 3285 12309 16963 49439 Cancellations 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 GTSN time (s) 7.10 101.9 403.0 677.4 801.0 0.86 7.6 45.6 134.1 816.5 0.45 8.4 86.3 144.3 797.7 CPU time (s) 10.9 126.1 492.3 825.0 960.6 1.9 10.8 60.2 185.2 982.4 1.3 11.2 106.7 178.8 949.7 Optimal integer 14100 13700 12447 11647 11647 21500 20925 15725 13510 13025 21500 21391 16542 13542 13040 Gap 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0%Table 13
Results for different simplex group cycle partitions and weighted threshold under scenario 2.
α 0 First simplex group cycle partition Second simplex group cycle partition Third simplex group cycle partition 1 3.6 4.4 4.45 4.5 1 3.2 3.5 3.9 4.6 1 3.0 3.3 4.2 4.7 F s 28.3% 35.8% 75.1% 89.3% 100% 12.9% 21.6% 45.2% 81.4% 100% 12.9% 23.6% 37.7% 79.1% 100% DT 60 7 7 7 7 7 7 6 8 8 8 7 9 8 8 8 DT 30 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 DT 15 1 1 1 1 1 0 0 0 0 0 4 0 0 0 0 DT 0 1 1 2 2 2 0 0 2 2 2 0 1 2 2 2 Nodes 2853 3479 12739 14188 15158 781 2261 4639 5164 15158 781 2353 4390 12921 15158 Flight arcs 5948 7659 36361 45118 49543 1369 4436 10646 12089 49543 1369 4984 9171 37809 49543 Cancellations 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 GTSN time (s) 16.5 26.1 504.3 689.1 809.8 1.3 10.0 46.8 59.4 809.6 1.3 11.7 46.3 530.7 810.9 CPU time (s) 23.7 35.1 606.9 841.6 992.7 3.0 14.2 62.0 78.2 1006.5 3.1 17.5 59.6 652.9 998.4 Optimal integer 71200 61100 59835 59835 59835 101300 92600 63343 59743 59743 101300 63000 61722 60822 59722 Gap 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0%Table 14
Results for different simplex group cycle partitions and weighted threshold under scenario 3.
α 0 First simplex group cycle partition Second simplex group cycle partition Third simplex group cycle partition 1 1.7 1.8 2.1 2.2 1 4.8 4.9 5.9 6.3 1 4.5 6.0 6.6 7.4 F s 25.1% 49.2% 63.3% 88.1% 100% 27.1% 35.8% 40.9% 65.3% 100% 22.0% 29.1% 58.6% 87.7% 100% DT 60 10 6 5 5 5 6 4 5 5 3 18 16 11 6 5 DT 30 4 7 8 8 8 4 1 1 1 2 1 1 2 2 2 DT 15 2 3 4 4 4 1 1 1 1 1 2 2 3 4 2 DT 0 6 7 6 6 6 5 5 5 5 7 4 6 7 10 11 Nodes 2951 5420 11407 14052 14879 3530 5200 5688 10177 14879 1803 2798 8566 13603 14879 Flight arcs 6474 14395 31950 43790 48559 7786 11783 13309 28117 48559 4070 6430 22541 43039 48559 Cancellations 2 2 2 2 2 4 4 4 2 2 2 2 2 2 2 GTSN time (s) 17.5 68.4 395.2 659.4 781.7 33.0 71.1 89.4 324.7 781.0 8.0 17.9 224.5 624.9 777.1 CPU time (s) 27.5 97.2 497.5 807.4 957.4 44.4 91.8 112.9 409.4 938.8 13.9 25.7 278.9 766.8 942.2 Optimal integer 89500 76071 73850 73850 73850 101299 93500 88900 81879 74580 127700 108000 105654 90300 87500 Gap 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0%Table 15
Results for different simplex group cycle partitions and weighted threshold under scenario 4.
α 0 First simplex group cycle partition Second simplex group cycle partition Third simplex group cycle partition 1 6.9 7.3 9.1 1 6.2 6.75 8.1 8.4 1 5.8 6.4 8.3 9.10 F s 66.5% 74.0% 88.1% 100% 40.1% 48.8% 62.5% 86.2% 100% 33.8% 40.9% 58.6% 87.7% 100% DT 60 14 15 16 17 18 21 24 25 29 20 25 25 26 29 DT 30 2 2 2 2 8 5 8 5 3 6 6 5 2 2 DT 15 2 3 3 2 3 3 2 3 3 3 1 3 2 1 DT 0 9 7 8 8 9 8 8 9 7 7 8 9 11 9 Nodes 6475 7037 14034 14858 2959 4200 5466 7735 14858 2425 3474 6503 13585 14858 Flight arcs 19023 20974 43699 48454 8040 11335 15674 25801 48454 6326 8982 16996 42950 48454 Cancellations 3 3 3 3 3 3 3 3 3 3 3 3 3 3 GTSN time (s) 108.6 131.3 662.4 783.9 23.8 45.1 79.8 175.1 781.7 15.6 29.9 125.4 625.3 777.6 CPU time (s) 150.2 184.2 824.4 977.9 38.2 65.6 110.3 259.3 923.2 24.7 41.9 158.6 769.7 931.7 Best integer 140700 140700 137399 137399 172300 150500 144374 142174 139773 182000 155700 149239 143391 141991 Gap 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0%By the Choose Method, we give out the value ofα0 under different scenarios for the time limit of 5 minutes, 10 minutes, 15 minutes, and 20 minutes in Table 16. The solution is obtained considering the flight disruption scope and depth, computation time, and recovery value under some appropriate rules, which is generally different from the minimum recovery value.Table 16
Chooseα0 for different time limit under different scenarios.
Time limit 5 min 10 min 15 min 20 min Scenario S 1 S 2 S 3 S 4 S 1 S 2 S 3 S 4 S 1 S 2 S 3 S 4 S 1 S 2 S 3 S 4 α 0 3.2 3.6 4.9 1 3.2 3.6 5.9 1 3.2 3.6 5.9 1 3.2 3.6 6.3 1 SGP 3 1 2 1 3 1 2 1 3 1 2 1 3 1 2 1 CPU time (s) 178.8 35.1 112.9 150.2 178.8 35.1 409.4 150.2 178.8 35.1 409.4 150.2 178.8 35.1 938.8 150.2 Impact 20 57 73 129 20 57 57 129 20 57 57 129 20 57 51 129 Optimal integer 13542 61100 88900 140700 13542 61100 81879 140700 13542 61100 81879 140700 13542 61100 74580 140700Note that the time-space network generation time occupies the majority of the computational time required to solve the WTBAM. In fact, the feasible region of the WTBAM is the time-space network, the total CPU time primarily consists of the time required to generated a feasible region, and the well-ordered property requirement must be satisfied or approximately satisfied in most cases.By comparing the data for the same disruption scenario, we note that the simplex group cycle partition is finer, the weighted value is larger, and the optimal integer value is largest for all potential flight disruptions. The number of aircraft decreases as the number of simplex group cycles increases, according to Tables7–9. For the same disruption scenario, the weighted value also increases when the number of simplex group cycles increases, according to Figure 2.


## 4.1. Sample Flight Schedule Table1

Mechanical problems are detected for aircraftf1 at 9:50, and it is estimated that a 4-h period is required for the repair work. In this example, the time band is set to half an hour and the schedule recovery is implemented from 10:00 to 02:00 the next day. In this example, the simplex group cycle partitions are set to S1 and S2, in order to show the AOCC controllability. Note that these partitions do not correspond to the partition implemented using the simplex group cycle procedure. The weighted value W2=1.9 is determined according to the weighted set procedure. We set the disruption threshold α0=2.0; then the potential disruption flights set PDFS2.0 is as shown in Table 2.Table 2
Flight schedule and aircraft assignments forPDFS2.0.
TailN From To Dep.T Arr.T Ass. A C. Cost 12 PEK CTU 11:30 14:00 f 1 , 321 15150 22 PEK SHA 12:30 14:30 f 2 , 321 16991 32 CTU SHA 12:20 14:50 f 3 , 321 15785 33 SHA CTU 17:35 20:05 f 3 , 321 13031 34 CTU SHA 21:00 23:30 f 3 , 321 13820 42 XIY PEK 10:00 11:55 f 4 , 321 10256 52 PEK CTU 15:00 17:30 f 5 , 321 15236 53 CTU XIY 20:45 22:00 f 5 , 321 9325 54 XIY CTU 23:00 00:15 f 5 , 321 9128Subsequently, the flight arc delay costs for the recovery problem are determined using the time-band transformation network [12]. The time-band transformation contains 26 nodes and 57 flight arcs. The delay cost for each flight arc is calculated according to the arc delay, and a 20-per-min delay cost function is assumed [12] in this paper. The nonzero flight arc delay costs for α0=1.0 and 2.0 are listed in Tables 3 and 4, respectively. Finally, we can compute the WTBAM solution using Lingo 14.0. The solutions for α0=1.0 and 2.0 are listed in Tables 5 and 6, respectively. The results obtained for the time-band transformation with α0=2.0 contain more nodes and flight arcs than that for α0=1.0; therefore, the WTBAM solution (with α0=2.0) may yield a superior proximal point than the standard time-band transformation with α0=1.0. Further, the optimal value yielded by the WTBAM is smaller than that for the time-band transformation with α0=1.0.Table 3
Nonzero flight arc delay costs with disruption thresholdα0=1.0.
TailN Origin node Destination node Arc delay cost 12 3 7 3000 21 3 6 1800 32 4 8 3200 32 7 9 6200 32 10 14 10400 32 11 14 11600 33 8 11 1100 33 9 13 4100 34 11 14 1200Table 4
Nonzero flight arc delay costs with disruption thresholdα0=2.0.
TailN Origin node Destination node w i j k ∗  arc delay cost 12 4 10 1200 12 5 11 1800 12 6 13 1800 22 5 9 600 22 6 12 3420 32 7 14 3200 32 10 16 4400 32 11 17 5000 32 13 18 6200 32 15 20 7400 32 19 27 10400 32 21 27 11600 32 22 27 12800 32 24 27 14000 33 14 21 1100 33 16 22 2300 33 17 24 2900 33 18 26 4100 33 20 29 5300 34 21 27 1200 34 22 27 2400 34 24 27 3600 42 23 28 29640 42 25 28 31920 53 19 23 570 53 21 25 1800 53 22 30 5130 53 24 30 6270 53 26 30 8550 54 25 29 2280Table 5
Results forα0=1.0.
min ⁡ ⁡ z = 15785 h 1 = h 2 = h 3 = 1 TailN From To OST node DST node Ass. A D. cost C. cost  12 PEK CTU 2 4 f 2 0 — 21 PEK SHA 1 5 f 3 0 — 32 CTU SHA — — — — 15758 33 SHA CTU 5 10 f 3 0 — 34 CTU SHA 4 14 f 2 0 — OST: origin station-time; DST: destination station-time; D. cost: delay cost.Table 6
Results forα0=2.0.
min ⁡ z = 0 h 1 = 2 ,   h 2 = 1 ,   h 3 = 2 ,   h 4 = 0 TailN From To OST node DST node Ass. A D. cost C. cost  12 PEK CTU 2 7 f 2 0 — 22 PEK SHA 4 8 f 5 0 — 32 CTU SHA 3 8 f 3 0 — 33 SHA CTU 8 19 f 3 0 — 34 CTU SHA 19 27 f 1 0 — 42 XIY PEK 1 5 f 4 0 — 52 PEK CTU 6 15 f 1 0 — 53 CTU XIY 15 23 f 2 0 — 54 XIY CTU 23 29 f 2 0 —


## 4.2. Stochastic Experiments

Our model was also tested using actual data obtained for a specific day in 2015, for a hub-and-spoke airline network under Sichuan Airlines having approximately 254 daily flights. The WTBAM was implemented in C++ using CPLEX 12.3 on a Lenovo notebook with a 2.16-GHz processor. As the arrival time of the disrupted flight was 02:30 on the next day and recovery time interval should contain all the flight schedule, we set the schedule recovery from 07:00 to 03:00 on the next day and the time band to 5 min in order to reduce the gap bound. Then, 1–4 aircraft having mechanical problems or some issue prohibiting them from use between 07:00 to 03:00 on the next day were randomly generated; these events were labelled scenarios 1–4. Combined with the experience of AOCC, the simplex group cycle should not be very large but should not be very small, 60 aircraft in the actual data, roughly divided into 6–15 group. If the simplex group cycle is very large, it may lead to the fact that the calculation time of optimal solution is too long and the potential disruption scope is too large, while if it is too small it may lead to a large potential disruption depth. So we obtain the 7, 12, and 15 three simplex group cycles by settingm0=5,10,12 in the S Algorithm. Subsequently, three simplex group cycle partitions are listed in Tables 7–9, and due to the limit of table length, only apart results of WTBAM under these partitions and different disruption thresholds are listed in Tables 12–15. In addition, the results for the simplex group cycle partitions, the scenarios, and the weighted values are presented in Figure 2.Table 7
First simplex group cycle partition.
SGCN TailN S 1 16 17 18 21 31 32 33 35 39 42 S 2 1 22 25 26 27 30 38 48 52 54 55 57 60 S 3 2 3 8 9 10 11 34 40 41 43 44 S 4 29 36 37 47 49 53 S 5 5 6 15 20 56 58 59 S 6 4 7 12 19 23 24 46 S 7 13 14 28 45 50 51 SGCN: Simplex group cycle number.Table 8
Second simplex group cycle partition.
SGCN TailN S 1 17 18 32 35 39 42 S 2 22 25 26 38 57 S 3 2 8 9 10 11 34 40 41 S 4 29 36 37 49 53 S 5 5 6 15 20 56 59 S 6 12 23 24 46 S 7 27 43 52 58 S 8 1 30 33 47 48 S 9 13 14 28 45 50 51 S 10 3 16 44 55 60 S 11 4 19 21 S 12 7 31 54Table 9
Third simplex group cycle partition.
SGCN TailN S 1 18 32 35 39 42 S 2 22 25 26 38 S 3 2 8 9 10 11 34 40 41 S 4 29 36 37 49 S 5 5 6 15 20 56 59 S 6 23 24 S 7 43 58 S 8 1 30 47 48 S 9 14 28 45 51 S 10 3 16 44 55 60 S 11 4 19 21 S 12 7 31 54 S 13 12 46 50 S 14 13 52 57 S 15 15 17 27 53Figure 2
Weighted value under different scenarios.
(a)
Weighted value under scenario 1 (b)
Weighted value under scenario 2 (c)
Weighted value under scenario 3 (d)
Weighted value under scenario 4Note that DT 60, DT 30, DT 15, and DT 0 indicate that the flight delay time is more than 60 min, between 30 min and 60 min, between 15 min and 30 min, and between 0 min and 15 min, respectively. Further, GTSN time (s) represents the time required to generate the time-space network in seconds, while CPU time represents the WTBAM calculation time.Comparison of the data in Tables12–15 leads to the conclusion that the potential disruption scope Fs, GTSN time, and CPU time increase with increased α0. Subsequently, by the results in Tables 12–15, we can obtain that GTSN time, CPU time, and potential disruption scope Fs satisfy the function in Table 11 and Figure 3. With the increase of Fs, GTSN time and CPU time are exponential growth and the function relationship is 10ax+b,a>0,b∈R,R is the real set. In view of this test, GTSN time and CPU time of second simplex group cycle partitions are generally better than the other simplex group cycle partitions. Note that GTSNij and CPUij indicate the function of GTSN time and potential disruption scope Fs in the case of scenario i and jth simplex group cycle partitions, i=1,2,3,4 and j=1,2,3.Figure 3
CPU Ttme and GTSN time under different scenarios.However, the optimal integer solution primarily decreases with increasedα0, and the gap between the optimal integer and the optimization solution is zero in the examples. Further, when the optimal integer reaches a certain level, it does not necessarily decrease or decreases only slightly, in most cases. These results show that a larger Fs is not necessarily better. In fact, the real extent of the flight disruption decreases with increased α0; however, note that this factor, disruption scope, and depth do increase with increased α0 in some cases. Further, the nodes and flight arcs increase with increased α0, along with the CPLEX 12.3 computational time.The AOCC controllers can choose the value ofα0 by considering the balance between the real flight disruption scope and depth, the CPU time, and the optimal integer value. Subsequently, we first introduce the feasible method to choose the value of α0 (Choose Method) in the following. The AOCC controllers choose the appropriate value of α0 which should be consistent with the four rules in the following.Choose Method The first rule is to meet the time limit for flight operations recovery. The second rule is about the flight recovery value in the following formula. Letf∗ be minf1∗,f2∗, α0∗ be the corresponding threshold of f∗, and α0i be the corresponding threshold of fi∗,i=1,2. (33)α0=α0∗f1∗-f2∗f∗>γ,α01orα02otherwise. The third rule is as small as possible to the impact of disruption flights scope and depth. The fourth rule is to ensure the uniqueness flight recovery plan. If there are two flight recovery plans to meet the previous three rules, then select a smaller flight recovery value. And if the flight recovery value is also the same, then select the CPU time which is less than that of the flight recovery plan.In this paper, we chooseγ=0.25 which means that the two flight recovery plans can be considered as equivalent when the difference ratio of the two flight recovery values is less than or equal to 0.25, because the AOCC controllers are not just considering about flight recovery values. The airlines can adjust γ to meet their management objectives. Subsequently, we provide a feasible method to measure the impact of disruption flights scope and depth according to the actual situation in China. Firstly, the weighted value of common delay time band is determined by the AOCC controllers, and then we calculate the total impact value. The delay time band and the weighted value are given out in Table 10. In particular, the weighted value can be adjusted according to the requirements of the airlines.Table 10
The impact of disruption flights scope and depth.
Delay time band DT 0 DT 15 DT 30 DT 60 Cancelled flight Weighted value 1 2 4 6 8Table 11
Functions for different simplex group cycle partitions and potential disruption scope.
First SGP Second SGP Third SGP First SGP Second SGP Third SGP Scenario 1 Scenario 2  GTSN 1 0 2.30 x + 0.82 1 0 2.97 x - 0.01 1 0 3.28 x + 0.03 1 0 2.53 x + 0.55 1 0 2.53 x + 0.16 1 0 2.98 x + 0.18 CPU 1 0 2.20 x + 0.99 1 0 2.76 x + 0.26 1 0 2.97 x + 0.34 1 0 2.43 x + 0.72 1 0 2.33 x + 0.44 1 0 2.74 x + 0.47  Scenario 3 Scenario 4  GTSN 1 0 2.26 x + 0.79 1 0 1.82 x + 1.16 1 0 2.56 x + 0.51 1 0 2.90 x + 0.08 1 0 2.27 x + 0.47 1 0 2.60 x + 0.41 CPU 1 0 2.12 x + 1.02 1 0 1.76 x + 1.29 1 0 2.39 x + 0.74 1 0 2.73 x + 0.33 1 0 2.12 x + 0.73 1 0 2.45 x + 0.64 x : F s.Table 12
Results for different simplex group cycle partitions and weighted thresholds under scenario 1.
α 0 First simplex group cycle partition Second simplex group cycle partition Third simplex group cycle partition 1 2.1 2.5 2.6 2.7 1 2.27 2.7 2.87 3.3 1 2.5 3.1 3.2 4.1 F s 16.5% 38.1% 63.3% 88.1% 100% 8.6% 22.4% 46.8% 75.9% 100% 7.0% 24.8% 42.9% 50.3% 100% DT 60 6 6 8 6 6 3 2 0 0 0 3 2 0 0 0 DT 30 1 1 0 0 0 7 8 9 6 6 7 8 6 3 3 DT 15 1 1 0 0 0 1 1 0 0 0 1 1 2 1 1 DT 0 1 0 1 3 3 1 2 2 3 2 1 3 4 6 6 Nodes 1953 6408 11634 14314 15137 679 1965 4599 7091 15137 489 1998 5803 7331 15137 Flight arcs 3877 13903 32606 44636 49439 1064 3516 10331 21364 49439 738 3285 12309 16963 49439 Cancellations 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 GTSN time (s) 7.10 101.9 403.0 677.4 801.0 0.86 7.6 45.6 134.1 816.5 0.45 8.4 86.3 144.3 797.7 CPU time (s) 10.9 126.1 492.3 825.0 960.6 1.9 10.8 60.2 185.2 982.4 1.3 11.2 106.7 178.8 949.7 Optimal integer 14100 13700 12447 11647 11647 21500 20925 15725 13510 13025 21500 21391 16542 13542 13040 Gap 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0%Table 13
Results for different simplex group cycle partitions and weighted threshold under scenario 2.
α 0 First simplex group cycle partition Second simplex group cycle partition Third simplex group cycle partition 1 3.6 4.4 4.45 4.5 1 3.2 3.5 3.9 4.6 1 3.0 3.3 4.2 4.7 F s 28.3% 35.8% 75.1% 89.3% 100% 12.9% 21.6% 45.2% 81.4% 100% 12.9% 23.6% 37.7% 79.1% 100% DT 60 7 7 7 7 7 7 6 8 8 8 7 9 8 8 8 DT 30 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 DT 15 1 1 1 1 1 0 0 0 0 0 4 0 0 0 0 DT 0 1 1 2 2 2 0 0 2 2 2 0 1 2 2 2 Nodes 2853 3479 12739 14188 15158 781 2261 4639 5164 15158 781 2353 4390 12921 15158 Flight arcs 5948 7659 36361 45118 49543 1369 4436 10646 12089 49543 1369 4984 9171 37809 49543 Cancellations 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 GTSN time (s) 16.5 26.1 504.3 689.1 809.8 1.3 10.0 46.8 59.4 809.6 1.3 11.7 46.3 530.7 810.9 CPU time (s) 23.7 35.1 606.9 841.6 992.7 3.0 14.2 62.0 78.2 1006.5 3.1 17.5 59.6 652.9 998.4 Optimal integer 71200 61100 59835 59835 59835 101300 92600 63343 59743 59743 101300 63000 61722 60822 59722 Gap 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0%Table 14
Results for different simplex group cycle partitions and weighted threshold under scenario 3.
α 0 First simplex group cycle partition Second simplex group cycle partition Third simplex group cycle partition 1 1.7 1.8 2.1 2.2 1 4.8 4.9 5.9 6.3 1 4.5 6.0 6.6 7.4 F s 25.1% 49.2% 63.3% 88.1% 100% 27.1% 35.8% 40.9% 65.3% 100% 22.0% 29.1% 58.6% 87.7% 100% DT 60 10 6 5 5 5 6 4 5 5 3 18 16 11 6 5 DT 30 4 7 8 8 8 4 1 1 1 2 1 1 2 2 2 DT 15 2 3 4 4 4 1 1 1 1 1 2 2 3 4 2 DT 0 6 7 6 6 6 5 5 5 5 7 4 6 7 10 11 Nodes 2951 5420 11407 14052 14879 3530 5200 5688 10177 14879 1803 2798 8566 13603 14879 Flight arcs 6474 14395 31950 43790 48559 7786 11783 13309 28117 48559 4070 6430 22541 43039 48559 Cancellations 2 2 2 2 2 4 4 4 2 2 2 2 2 2 2 GTSN time (s) 17.5 68.4 395.2 659.4 781.7 33.0 71.1 89.4 324.7 781.0 8.0 17.9 224.5 624.9 777.1 CPU time (s) 27.5 97.2 497.5 807.4 957.4 44.4 91.8 112.9 409.4 938.8 13.9 25.7 278.9 766.8 942.2 Optimal integer 89500 76071 73850 73850 73850 101299 93500 88900 81879 74580 127700 108000 105654 90300 87500 Gap 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0%Table 15
Results for different simplex group cycle partitions and weighted threshold under scenario 4.
α 0 First simplex group cycle partition Second simplex group cycle partition Third simplex group cycle partition 1 6.9 7.3 9.1 1 6.2 6.75 8.1 8.4 1 5.8 6.4 8.3 9.10 F s 66.5% 74.0% 88.1% 100% 40.1% 48.8% 62.5% 86.2% 100% 33.8% 40.9% 58.6% 87.7% 100% DT 60 14 15 16 17 18 21 24 25 29 20 25 25 26 29 DT 30 2 2 2 2 8 5 8 5 3 6 6 5 2 2 DT 15 2 3 3 2 3 3 2 3 3 3 1 3 2 1 DT 0 9 7 8 8 9 8 8 9 7 7 8 9 11 9 Nodes 6475 7037 14034 14858 2959 4200 5466 7735 14858 2425 3474 6503 13585 14858 Flight arcs 19023 20974 43699 48454 8040 11335 15674 25801 48454 6326 8982 16996 42950 48454 Cancellations 3 3 3 3 3 3 3 3 3 3 3 3 3 3 GTSN time (s) 108.6 131.3 662.4 783.9 23.8 45.1 79.8 175.1 781.7 15.6 29.9 125.4 625.3 777.6 CPU time (s) 150.2 184.2 824.4 977.9 38.2 65.6 110.3 259.3 923.2 24.7 41.9 158.6 769.7 931.7 Best integer 140700 140700 137399 137399 172300 150500 144374 142174 139773 182000 155700 149239 143391 141991 Gap 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0%By the Choose Method, we give out the value ofα0 under different scenarios for the time limit of 5 minutes, 10 minutes, 15 minutes, and 20 minutes in Table 16. The solution is obtained considering the flight disruption scope and depth, computation time, and recovery value under some appropriate rules, which is generally different from the minimum recovery value.Table 16
Chooseα0 for different time limit under different scenarios.
Time limit 5 min 10 min 15 min 20 min Scenario S 1 S 2 S 3 S 4 S 1 S 2 S 3 S 4 S 1 S 2 S 3 S 4 S 1 S 2 S 3 S 4 α 0 3.2 3.6 4.9 1 3.2 3.6 5.9 1 3.2 3.6 5.9 1 3.2 3.6 6.3 1 SGP 3 1 2 1 3 1 2 1 3 1 2 1 3 1 2 1 CPU time (s) 178.8 35.1 112.9 150.2 178.8 35.1 409.4 150.2 178.8 35.1 409.4 150.2 178.8 35.1 938.8 150.2 Impact 20 57 73 129 20 57 57 129 20 57 57 129 20 57 51 129 Optimal integer 13542 61100 88900 140700 13542 61100 81879 140700 13542 61100 81879 140700 13542 61100 74580 140700Note that the time-space network generation time occupies the majority of the computational time required to solve the WTBAM. In fact, the feasible region of the WTBAM is the time-space network, the total CPU time primarily consists of the time required to generated a feasible region, and the well-ordered property requirement must be satisfied or approximately satisfied in most cases.By comparing the data for the same disruption scenario, we note that the simplex group cycle partition is finer, the weighted value is larger, and the optimal integer value is largest for all potential flight disruptions. The number of aircraft decreases as the number of simplex group cycles increases, according to Tables7–9. For the same disruption scenario, the weighted value also increases when the number of simplex group cycles increases, according to Figure 2.


## 5. Conclusions and Discussion

In this study, we constructed the weighted time-band approximation model (WTBAM) incorporating simplex group cycles for flight operations recovery. The objective of the WTBAM as regards flight operations recovery is to minimize both the delay costs and the cancellation costs through implementation of a weighted threshold. The series of experiments conducted here has shown that the potential disruption scope and depth, computation time, and recovery value are controlled by the disruption threshold. Considering the balance between the real impact of flight disruption scope and depth, the CPU operation time, and the recovery value, airline operations control center (AOCC) controllers can conveniently obtain satisfactory recovery plan by changing the disruption threshold. Through examination of the WTBAM characteristics, it was determined that the gap between the linear programming relaxation of the WTBAM (LPRWTBAM) and WTBAM solutions is zero under some conditions. Therefore, the total CPU operation time is primarily comprised of the time required for the WTBAM to generate a feasible region for the time-space network. The computation time decreases as the disruption threshold is decreased. In future research, methods to partition the flights or aircraft into the optimal simplex group cycles will be investigated.



---

*Source: 3201490-2016-10-27.xml*