Reassigning Departure Slots with Preferences of the Airline and Passengers

Abstract

The recovery of a departure flight is an important part of airline disruption management. The commonly used optimization objectives for assessing airport slot-scheduling efficiency are delay cost and delay time. However, the current literature does not consider the preferences of airlines and passengers in the recovery process simultaneously. The objective of this paper is to focus on the departure slot reassignment problem and develop a bi-objective optimization model. We introduce a metric for the price of fairness and formulate the airport slot scheduling problem as a bi-objective optimization model that considers the trade-off between the total airline delay cost and total passenger delay time. To quantify the trade-off between total airline delay costs and total passenger delay time, we apply the metric of the price of fairness in the bi-objective model, treating the total airline delay cost as an efficiency metric and the total passenger delay time as a fairness metric, calculating the price of fairness for each Pareto solution. An adaptive non-dominated sorting genetic algorithm-II based on dominant strengths (ANSGA2-DS) is developed to solve this problem. More precisely, three improved operations are presented: the improved fast dominant strength sorting method, new crowding distance improvement, and an adaptive elitist retention strategy. Three scenarios derived from a Chinese airline’s operation data are applied to the proposed bi-objective model and algorithm. The experimental findings demonstrate that the proposed model and method can effectively and efficiently address the problem. This may provide a basis for airline operation controllers to achieve a generally acceptable solution.

Keywords

aviation airfield and airspace capacity and delay air traffic management airport operations optimization

Airlines are playing an increasingly significant role in the transportation industry. In the year 2020, the passenger throughput of China’s airports was more than 8.57 billion. Unfortunately, flight disruption has also become increasingly common, causing severe flight delays and economic losses. According to the 2020 Chinese statistics, the flight on-time rate was only 88.5%, and these flight delays caused about $50 billion of direct economic losses ( 1 ).

The original flight schedules of the airline are often renderd infeasible by variable unexpected events called disruptions ( 2 ). All these disruptions can be classified as either internal or external causes. Internal causes include unpredictable maintenance issues, machine malfunction, and crew unavailability, and so on. External causes include air traffic control, airport facility restrictions, inclement weather, earthquakes, other disasters, and so on. These disruptions result in the decline of the transportation supply capacity of airlines and break the balance between supply and demand, leading to flight delay. In general, decision makers have two ways to mitigate their difficult situation: i) provide extra facilities to cope with unexpected supply shortfalls; and ii) use scientific management methods to mine the potential of existing facilities. In reality, the former is usually infeasible for economic reasons. As to the latter, one useful method is to reschedule departure flights with the aim of making full use of departure slots ( 3 ).

The typical disruption recovery of airlines includes four sequential processes: flight schedule recovery, aircraft recovery, crew recovery, and passenger recovery ( 4 ). When a disruption occurs, the first decision to be made is flight schedule recovery, which is the process of making flight re-timing or cancellation decisions. In other words, it is the process of reassigning slots to the disrupted flights. The disrupted flight schedule recovery can be further divided into arrival flight schedule recovery and departure flight schedule recovery. Given the rapid development of air transportation and the serious situation of flight delays, the airline disruption recovery has attracted much research in recent years ( 5 – 8 ). However, when it comes to the flight schedule recovery, research on the issue of the planned recovery of departure flights has not been sufficiently studied. The existing literature on this problem generally regards re-timing departure flights as a component of the integration recovery or an aspect of consideration of the aircraft recovery ( 9 , 10 ).

Reducing the delay cost as much as possible is usually the primary preference of every airline. Most of the literature about airline disruption recovery takes the minimization of total delay cost as an optimization objective ( 11 – 13 ). However, in the competitive market environment, the preferences of passengers cannot be ignored. Long delay times would affect passenger satisfaction and reduce passenger loyalty to the airline. In the long term, airlines with severe flight delays will lose market share and profits. So airlines should also try their best to reduce the delay time of passengers. There are also many airline disruption recovery studies considering passenger delay times ( 14 – 16 ). Clearly, there is a trade-off between the total airline delay cost and the total passenger delay time. However, the existing literature rarely considers the total airline delay cost and the total passenger delay time simultaneously, nor does it consider the departure problem exhaustively in the context of the trade-off between the total airline delay cost and the total passenger delay time.

In our work, we propose a novel bi-objective model considering the airline’s and the passengers’ preferences simultaneously. It focuses on rescheduling departure flights from the perspective of the airline. An adaptive non-dominated sorted genetic algorithm-II based on dominant strengths (ANSGA2-DS) is presented to solve the departure slots reassignment problem. The metric of the price of fairness is introduced to explore the trade-off between the total airline delay cost and the total passenger delay time. The approach described in this research can deal with the preferences of passengers and airlines.

The paper is organized as follows. We review related literature and establish the paper’s contributions. The suggested bi-objective model is then presented along with a description of the departure slots reassignment problem. The adaptive non-dominated sorting genetic algorithm-II based on dominant strengths is then detailed to handle the problem under consideration. The results of using the suggested model and method are then shown. Finally, we present a brief review of our research and put forward a vision for future research.

Literature Review

The disruption slot recovery process is intricate since it involves the reallocation of multiple resources. Flight, aircraft, crew, and passengers are the four most important resources that need to be reallocated in the airline recovery problem ( 17 ). Both from a mathematical and a computational perspective, the integration of all recovery stages is a difficult task. The purpose of this integration is to minimize the total disruption cost. This is achieved by weighing the disruption cost related to aircraft, aircraft crew, and passengers simultaneously to find the recovery solution that overall results in the lowest cost for the airline. Consequently, the airline disruption recovery problem can be decomposed into four sub-problems. When a disruption occurs, the airline control center (ACC) usually solves the problem of flight schedule recovery, aircraft recovery, crew recovery and passenger recovery in sequence, and each problem’s solution is used as an input for the next problem. The classification of the current literature is shown in Figure 1, which also indicates the several sorts of procedure that have been used to recovery disrupted flights. The reader is directed to the reviews for a more thorough examination of the categorization and use of slot allocation techniques.

In this work, we deal with the departure slot reassignment problem, concentrating our efforts on slot recovery decisions that are based on rescheduling departure flights from the airline’s standpoint, so we will review the literature on this topic. The main goal and contribution is to create a novel bi-objective model for a single airport’s strategic slot scheduling. The presented model’s most notable characteristic is that it incorporates both airline and passenger preferences during the recovery phase. The suggested slot recovery model is solved using a multi-objective algorithm. We evaluate the relevant flight schedule recovery literature in this part, which addresses each of the two goals we set to highlight the research gaps associated with the failure to consider fairness objectives.

The literature has made some progress on the issue of flight recovery. Marla et al. ( 15 ) developed a novel method for dealing with airline delays and recovery. Planned resumption of airline operations entails making judgments during operations to save additional operating expenses while returning to regular operations as soon as practicable. Under the collaborative decision-making mechanism, Erkan et al. ( 18 ) proposed an integer programming model to address the arrival flight recovery problem. The application of the proposed model reassigned an airline’s slots to the disrupted inbound flights after the air traffic controller allocated slots to the airline. The model implicitly assumed that the crew and aircraft resources met the requirements. Wang et al. ( 19 ) published their work on the flight recovery problem as an integer or mixed integer linear programming problem, demonstrating the potential of simulation-based approaches in the study of the flight recovery problem; during aircraft ground operations, Evler et al. ( 20 ) incorporated all possible schedule recovery alternatives. The developed mathematical optimization model was an adaptation of the resource-constrained project scheduling problem, and it incorporated key features from the airline hub control problem such as turnaround target time prediction, passenger connection management, tactical stand allocation, and ground service vehicle routing.

For traditional airline recovery problems, most studies used the single objective model to get an optimal or a suboptimal solution. Santos et al. ( 21 ) constructed an airline delay recovery optimization model with an objective function to minimize the total additional costs in the delay management process. Liang et al. ( 13 ) developed an airline recovery model in which the objective function consisted of the sum of flight cancellation cost and path cost. Zhang et al. ( 22 ) studied a comprehensive airline service recovery problem, in which the aircraft and passenger schedule recovery problems were addressed concurrently. The objective is to minimize the sum of aircraft recovery costs, airline operating costs, and passenger travel delay costs.

Fieldsend and Singh ( 23 ) argued that the single objective solution cannot fully reflect the actual multi-objective needs in practical cases. A few scholars have begun to use the multi-objective optimization model to study the airline recovery problem in recent years. Liu et al. ( 24 ) put forward a multi-objective airline recovery model. Their multi-objective model contained five objective functions, namely: the total flight delay time objective, the flight duty swap objective, the delayed time variance, the delayed flight number objective, and flights with too long a delay objective. Hu et al. ( 25 ) constructed an airline recovery model with three objectives, namely to reduce the overall deviation from the initial flight plan, the maximum flight delay duration, and the number of flight interchanges. Hu et al. ( 26 ) used an integer programming model with two objectives to address both the airline’s and passengers’ interests and created a more efficient heuristic for multi-objective models, particularly for large-scale optimization problems. In the airline recovery model, the study described passengers’ willingness under itinerary disruption.

There are currently no models for scheduling series of slots that account for the airline’s and passengers’ preferences. It is worth noting that in research in the literature on the allocation of declining resources, fairness has been identified as an additional criterion. From the perspective of congestion pricing and the introduction of a monetary compensation mechanism to allocate time slots using a market-based method, fairness has been proposed as a standard for time slot allocation ( 27 ). Each airline should be penalized in proportion to its contribution to the inability to find the best solution. This indicates that if an airline seeks to obtain slots when demand overflows real capacity, individuals who would be unable to use the airport during this crowded period should be paid. Barnhart et al. ( 28 ) underlined the importance of conducting a thorough analysis of various levels of capacity specification, which would show the ideal trade-off between schedule and delay time, among other things. Androutsopoulos and Madas ( 29 ) suggested a fairness-informed extension of the strategic airport slot scheduling model, with the goal of ensuring that each airline absorbs its “fair share” of congestion in the form of additional schedule displacement.

In the event of a disruption, various heuristic algorithms have demonstrated great performance in reassigning airlines and passengers at the same time. For the integrated recovery of airlines and passengers following airline operation disruption, Hu et al. ( 11 ) adopted a greedy randomized adaptive search procedure (GRASP). The GRASP method may be used to find a suitable passenger reassignment in each iteration. Manyem ( 30 ) presented polynomial time algorithms based on the primal-dual schema to solve the problem of disruption of departure and take-off flights in airport ground waiting. Tian et al. ( 31 ) suggested an enhanced column generation method to optimize the scheduling of disrupted flights, reducing the airline’s economic loss while boosting operational efficiency and providing a foundation for decision making. Ji et al. ( 32 ) introduced a built-in flight feasibility verification technique to calculate the flight timetable in disruption management based on the lexicographic preference of flight priority.

The literature study finds that there are few studies that address airline and passenger preferences in flight schedule recovery. As a result, future research in this field should focus on developing models and solution methods that account for flight schedule recovery.

In a nutshell, the following are the primary contributions of this research. (i) This paper focuses on the departure slots recovery problem and proposes a dedicated bi-objective integer programming model used for reassigning disrupted slots for the airline. (ii) The proposed model in our research considers the total airline delay cost and the total passenger delay time simultaneously, which reflects the preferences of airlines and passengers respectively. (iii) The suggested bi-objective model’s complete efficient frontier depicts the trade-off between total airline delay cost and total passenger delay time. Furthermore, the information offered by the price of fairness aids airline operations controllers in reaching a widely approved reassignment choice for a disrupted flight. (iv) This paper develops an adaptive non-dominated sorting genetic algorithm based on dominant strengths (ANSGA2-DS) to achieve a set of Pareto solutions for the airline operation controllers to use for selecting the better design solution. The ANSGA2-DS algorithm has been improved in three areas: non-dominated sorting, distribution preservation, and elitist retention strategy, with the results compared with different algorithms to indicate the effectiveness and efficiency performance of the modified operations and the ANSGA2-DS in a range of scenarios.

Problem Description and Model Formulation

The suggested bi-objective slot scheduling paradigm is mathematically represented using the notation below.

Sets

I Set of disrupted flights

J Set of available slots

N Set of number of departure flights

Indexes

i Flight index

j Slot index

Parameters

$n_{i}$ Number of passengers of flight i, i∈I

$r_{i}$ Originally scheduled departure time of flight i, i∈I

$s_{j}$ Time of slot j, j∈J

t The delay time of a flight

$t_{max}$ The upper bound of delay time for disrupted flights

Variables

$x_{ij}$ $x_{ij}$ = 1, if slot j is assigned to flight i; otherwise $x_{ij}$ = 0

Functions

$φ (t)$ Passenger delay cost function representing the passenger delay cost of a given t min delay

$ϕ (t)$ Additional airline cost function representing the additional airline operational cost of each disrupted flight

Problem Description

The essence target of flight recovery problems is to re-accommodate passengers as soon as possible when an irregularity happens. Every recovery plan should maintain flow balance for every plane, crew, and passenger flow. Delays and cancellations are the basic measures to judge flight recovery. After a delay or cancellation is applied, every active (not cancelled) flight will have its estimated time of departure and estimated time of arrival. To some minor disruptions, delay might be an intuitive recovery policy, and it may be effective if the delay time is acceptable and does not break the flow balance in the system. Cancellation is a quick response to disruptions, but it is costly because a bunch of passengers will be re-accommodated or spilled, and it may also break the aircraft or crew connections. Cancelling a flight leg usually requires rerouting the aircraft, crew, and passenger flows. Therefore, the model developed here considers cancelling if the delay exceeds 480 min.

For airline recovery, there are some specific strategies. Aircraft swap or type substitution may be applied to find the possible swap opportunities in the same aircraft type or between other types. Reserved aircraft can be used to solve the disruption caused by shortage of aircraft. When inclement weather or other unexpected events emerge, airlines will get the airport capacity information from air traffic control (ATC) authority covering available slots in a unit time period. In this paper, the slots allocated by ATC are later than the original time, and the number of them is less than or equal to the number of original flights. Airlines need to reassign departure slots to flights according to their own preferences based on the initial slot allocation of ATC. If the number of original flights is more than the available slots, the airline should also consider cancelling some flights to achieve balance.

Our problem is to find a slot schedule recovery plan for the flights that minimizes the total airline delay cost and the total passenger delay time. In addition, to reduce the delay cost as much as possible is the primary preference of every airline. Another objective of the problem in this paper is to find a trade-off between the total airline delay cost and the total passenger delay time. It is essential to construct models that provide preferences for investigating the employment of slot scheduling preferences on the airline–passenger trade-off while also providing a framework for airline operation controllers to arrive at a generally agreed solution.

Working Assumptions

To simplify the problem, we make the following assumptions in our research. It should be noted that these simplifications and assumptions do not limit the applicability of the proposed methodology. Instead, they can ensure that the bi-objective model proposed in this research can be better solved. Therefore, we propose the following assumptions:

(i) There are no airport resource constraints.

(ii) For the sake of focusing on departure slot reassignment, the aircraft rotations, maintenance plans, and crew assignments are preserved.

(iii) The aircraft and crew are adequately resourced and may not be rearranged.

(iv) We only consider the delay cost and delay time at the departure airport.

(v) The number of slots allocated by ATC is equal to that of original flights and the airline does not consider flight cancellation. There is no slot constraint in airports.

(vi) The flights can only be delayed or on time, not earlier.

Model Formulation

We suggest the following mathematical model based on the assumptions mentioned above, which takes into account the airline’s and the passengers’ preferences.

min Z_{1} = \sum_{i \in I} \sum_{j \in J} x_{ij} n_{i} ϕ (s_{j} - r_{i})

(1)

ϕ (t) {\begin{matrix} 0.03 t^{*} 0 \leq t < 5 \\ 0.03 * 5 + 0 . 17^{*} (t - 5) 5 \leq t < 15 \\ 0 . 03^{*} 5 + 0 . 17^{*} (15 - 5) + 0 . 58^{*} (t - 15) 15 \leq t < 30 \\ 0 . 03^{*} 5 + 0 . 17^{*} (15 - 5) + 0 . 58^{*} (30 - 15) + 1 . 3^{*} (t - 30) 30 \leq t < 45 \\ 0 . 03^{*} 5 + 0 . 17^{*} (15 - 5) + 0 . 58^{*} (30 - 15) + 45 \leq t < 60 \\ 1 . 3^{*} (45 - 30) + 1 . 86^{*} (t - 45) \\ 0 . 03^{*} 5 + 0 . 17^{*} (15 - 5) + 0 . 58^{*} (30 - 15) + 60 \leq t < 75 \\ 1 . 3^{*} (45 - 30) + 1 . 86^{*} (60 - 45) + 1 . 79^{*} (t - 60) + 10 \\ 0 . 03^{*} 5 + 0 . 17^{*} (15 - 5) + 0 . 58^{*} (30 - 15) + \\ 1 . 3^{*} (45 - 30) + 1 . 86^{*} (60 - 45) + 1 . 79^{*} (75 - 60) + 75 \leq t < 120 \\ 1 . 55^{*} (t - 75) + 10 \\ 0 . 03^{*} 5 + 0 . 17^{*} (15 - 5) + 0 . 58^{*} (30 - 15) + \\ 1 . 3^{*} (45 - 30) + 1 . 86^{*} (60 - 45) + 1 . 79^{*} (75 - 60) + 120 \leq t < 150 \\ 1 . 55^{*} (120 - 75) + 1 . 39^{*} (t - 120) + 15 \end{matrix}

(2)

min Z_{2} = \sum_{i \in I} \sum_{j \in J} x_{ij} (s_{j} - r_{i}) n_{i}

(3)

subject to:

\sum_{j \in J} x_{ij} = 1, \forall i \in I

(4)

\sum_{i \in I} x_{ij} = 1, \forall j \in J

(5)

\sum_{i \in I} \sum_{j \in J} x_{ij} = N, \forall i \in I, \forall j \in J

(6)

x_{ij} (s_{j} - r_{i}) \geq 0, \forall i \in I, \forall j \in J

(7)

x_{ij} (s_{j} - r_{i}) \leq t_{\max}, \forall i \in I, \forall j \in J

(8)

x_{ij} = {0, 1}, \forall i \in I, \forall j \in J

(9)

Equation 1 of the proposed model seeks to minimize the total delay cost of each flight of the airline. The first term of Equation 1 $x_{ij} n_{i} ϕ (s_{j} - r_{i})$ refers to the costs associated with passenger delays. Estimating costs as accurately as possible is critical in the aviation industry. In the event of a flight interruption, most studies consider the change of cost to be linear with time, while the nonlinear delay cost is studied by Cook et al. ( 33 , 34 ) who propose a cost distribution to calculate soft and hard costs as a function of delay duration. Given that there is no information available to estimate the passenger-related cost function, we considered the cost estimate proposed by Cook et al. ( 34 ). Although this is a study for the European market, to the authors’ knowledge, it is the only study in the literature that estimates the costs associated with air transport delays and is able to provide a good example for the Chinese air market. Based on the piecewise linear function transformed from the logit function proposed by Cook et al., the mathematical formulation of the passenger delay cost function in this paper is provided in Equation 2. This cost function is depicted in Figure 2 for the first 150 min. As shown in Figure 2, the hard costs refer to compensation, rebooking, or accommodation for passengers, while the soft costs refer to the estimated potential revenue losses caused by passenger dissatisfaction at being delayed. In this cost function, a passenger who is delayed for 60 to 120 min would receive $10 compensation. When the delay time is 120 to 150 min, the amount of compensation is $15.

Equation 3 minimizes the sum of the passenger delay time of each flight, passenger satisfaction has a big impact on airlines, so they try to keep total passenger delays to a minimum. Equation 4 ensures each flight is reassigned to specific slot. Equation 5 requires that each slot belongs to one flight. Equation 6 stipulates that all the slot resources are assigned and there is no waste of slots. Equation 7 states that each flight cannot take off before the originally scheduled time. Equation 8 expresses that each flight is delayed no more than the maximum delay time. Equation 9 defines the decision variable as binary.

Solving the Bi-Objective Slot Scheduling Model

The objective of the present work in this paper is to obtain a trade-off between the total airline delay cost and the total passenger delay time. To solve the problem, we employ the ε-constraint approach (ECA) to achieve Pareto solutions, which is one of the most widely used a posteriori methods for solving multi-objective optimization problems ( 35 ). As illustrated in the following, this method selects one goal as the model’s main objective function and constrains the other objective functions with their upper boundaries in minimization and lower bounds in maximization. By constraining the parameter changes of the objective function, an efficient solution to the problem can be obtained.

The Proposed ANSGA2-DS Algorithm

This part will go over our multi-objective resolution technique, which is based on the Non-dominated Sorting Genetic Algorithm II (NSGA2) algorithm ( 36 ). It is commonly used to tackle multi-objective optimization issues in the automobile industry ( 37 ), manufacturing schedule ( 38 ), quality control check ( 39 ), and logistics and supply chain ( 40 ).

Non-Dominated Sorting Genetic Algorithm-II (NSGA2)

In NSGA2, the individuals with better rank or those with greater crowding distance at the same rank will be picked to form a new offspring population once the parent population has been initialized. To evolve the offspring population, the crossover and mutation operators are employed successively. Elitism is then used to choose the best individuals from the parent and offspring populations to create a new parent population. The main loop is iterated until the termination condition is satisfied and NSGA2 results in a set of Pareto solutions. Calculating the rank and crowding distance of individuals is the key to NSGA2. Deb et al. ( 36 ) provide details of how to calculate the rank and crowding distance.

NSGA2 is specifically designed for solving the multi-objective model and it has been effectively applied in a lot of multi-objective optimization problems ( 41 , 42 ). The key issues in developing NSGA2 are the encoding scheme of the solution, the retention of elitist individuals, the calculation of the ranks and the crowding distances. These problems are discussed exhaustively to provide the adaptive NSGA2 algorithm based on dominant strengths (ANSGA2-DS) for reassigning departure slots depending on airline and passenger preferences in this section.

Adaptive NSGA2 Algorithm Based on Dominant Strengths (ANSGA2-DS)

Algorithm Initialization

In this paper, according to the problem of departure flight recovery, Np individuals are randomly generated to form an initialization population, and individual coding is performed. As shown in Figure 3, each individual represents an outbound flight recovery scheme, consisting of integers 1 to N randomly arranged genes, the positions of the genes correspond to the available time slots, and the value of each gene represents the number of the specified flight. Take an individual A_k: (3-1-2-4-5-6-7-8)-(252,519.67-265044)-(null-null-null) as an example (k represents the k-th individual in the population, k∈Np), where (3-1-2-4-5-6-7-8) represents a random arrangement of eight slots, and the “3” on the first bit indicates that the 3rd slot is assigned to Flight 1, the “1” in the second digit means that slot 1 is assigned to flight 2, and so on. (252,519.67-265044) means that under this distribution method, the total delay cost of airlines and the total delay time of passengers are 252,519.67 and 265,044, respectively. (null-null-null) is expressed as null because the nondominant level, domination strength, and crowding distance are not calculated in the initialization phase.

Constraint-Handling Procedure

Following algorithm initialization, to ensure that the solutions of the generated individuals are feasible, check each individual to determine whether there are repeated individuals in the population, for example, the departure flight recovery plan for both individuals is (3-1-2-4-5-6-7-8), and individuals who violate constraints (8) and (9), that is, $x_{ij} (s_{j} - r_{i}) < 0$ or $x_{ij} (s_{j} - r_{i}) > t_{\max}, \forall i \in I, \forall j \in J$ . If the individuals in the above situation appear in the population, select the individuals in the population which violate the conditions to regenerate until all the individuals in the population meet the constraints in the problem. For constraints (5), (6), and (7), the correspondence between flights and available time slots in individual genetic codes has been initialized by algorithm initialization.

The Improved Fast Domination Sorting Strategy

After the constraints are processed, the individuals are sorted hierarchically using the improved fast domination sorting strategy as follows:

Algorithm 1. Pseudocode of the improved fast domination sorting strategy
Input: All population individuals A_k Output: Non-dominated sets P_N and non-dominated ranks of individuals ${rank}_{A_{k}}$ in the population //Initialization Initialize the non-dominated sets P_N =∅, comparison set P_C =∅,non-dominated ranks of individuals ${rank}_{A_{k}}$ =0; Put all population individuals into comparison set; //Main loop whileP_C≠∅do A₁ is the first individual in P_C ; V←all individuals which dominate A₁; if $V \neq Ø$ then $A_{2} \in V$ , A₂ is the first individual of V; E←all individuals which dominate A₂; if $E \neq Ø$ then A_k is all individuals that are mutually nondominant with A₁ and A₂; P_N=P_N∪A₁∪A₂∪A_k; $Ø \leftarrow A_{k} \in {A_{k} ≺ A_{1} \cup A_{k} ≺ A_{2}}$ ; else $A_{k} ≺ A_{1} \cup A_{k} ≺ A_{2}, A_{k} \in P_{C}$ P_N=P_N∪A₁∪A₂; $P_{C} \leftarrow A_{k} \in {A_{k} ≻ A_{1} \cup A_{k} ≻ A_{2}}$ ; end if elseP_N←A₁ end if ${rank}_{A_{k}} = {rank}_{A_{k}} + 1$ end while

Algorithm 1. Pseudocode of the improved fast domination sorting strategy

Input: All population individuals A_k
Output: Non-dominated sets P_N and non-dominated ranks of individuals

{rank}_{A_{k}}

in the population
//Initialization
Initialize the non-dominated sets P_N =∅, comparison set P_C =∅,non-dominated ranks of individuals

{rank}_{A_{k}}

=0;
Put all population individuals into comparison set;
//Main loop
whileP_C≠∅do
A₁ is the first individual in P_C ;
V←all individuals which dominate A₁;
if

V \neq Ø

then

A_{2} \in V

, A₂ is the first individual of V;
E←all individuals which dominate A₂;
if

E \neq Ø

then
A_k is all individuals that are mutually nondominant with A₁ and A₂;
P_N=P_N∪A₁∪A₂∪A_k;

Ø \leftarrow A_{k} \in {A_{k} ≺ A_{1} \cup A_{k} ≺ A_{2}}

;
else

A_{k} ≺ A_{1} \cup A_{k} ≺ A_{2}, A_{k} \in P_{C}

P_N=P_N∪A₁∪A₂;

P_{C} \leftarrow A_{k} \in {A_{k} ≻ A_{1} \cup A_{k} ≻ A_{2}}

;
end if
elseP_N←A₁
end if

{rank}_{A_{k}} = {rank}_{A_{k}} + 1

end while

When all the individuals in the population have completed the grading and sorting, a new performance judgment index-dominance strength ξ is introduced. The smaller the dominance strength of the individual in the non-dominated set, the better the optimization results of most of its sub-goals, and the greater the probability of entering the next generation population. In this paper, the dominance strength ensures that individuals with better performance will preferentially obtain genetics, which improves the quality of the algorithm’s solution set. The calculation formula of the dominance strength among individuals $ξ_{A_{k}}$ is as follows, where the individual A_k belongs to the non-dominated set, the number of sub-goals in the multi-objective problem is M, and the maximum and minimum values of the g-th sub-goal are represented $f_{g}^{max}$ and $f_{g}^{min}$ respectively:

ξ_{A_{k}} = \sum_{g = 1}^{M} (\frac{f_{g} (A_{k}) - f_{g}^{min}}{f_{g}^{max} - f_{g}^{min}})

(10)

Crowding Distance Calculation

The basic idea of crowding distance is to compare the density of individuals and judge whether the distribution of individuals is uniform by calculating the distance between each individual in the same non-dominated layer and its two adjacent individuals. The crowding distance formula of the original NSGA2 algorithm only focuses on the distance between adjacent individuals. Individuals with large differences in crowding distances on different sub-goals are less likely to be inherited, which is not conducive to the maintenance of the distribution of the solution set. In our research, a new crowding distance considering variance is proposed:

D_{A_{k}} = \frac{c_{A_{k}}}{{\frac{1}{M} {\sum_{g = 1}^{M} [(| f_{g}^{A_{k + 1}} - f_{g}^{A_{k - 1}} |) - \frac{c_{A_{k}}}{M}]}^{2}}^{- 1} + 1}

(11)

The traditional distance formula is $c_{A_{k}} = \sum_{g = 1}^{M} [| f_{g}^{A_{k + 1}} - f_{g}^{A_{k - 1}} |]$ , where the functions $f_{g}^{A_{k + 1}}$ and $f_{g}^{A_{k - 1}}$ represent the value of g-th sub-objective of individual A+1 and individual A-1. After the above-mentioned fast dominance intensity ranking and new crowding distance calculation, each individual A has three attributes: non-dominated rank ${rank}_{A_{k}}$ , domination of non-dominating set strength $ξ_{A_{k}}$ , and crowding distance $D_{A_{k}}$ . In the non-dominating set, first compare the non-dominated rank, then compare the dominance strength, and finally the crowding distance. For any two individual A_k and B_k: if $ran k_{A_{k}} > ran k_{B_{k}}$ or $ran k_{A_{k}} = ran k_{B_{k}} \cap ξ_{A_{k}} < ξ_{B_{k}}$ or $ran k_{A_{k}} = ran k_{B_{k}} \cap ξ_{A_{k}} = ξ_{B_{k}} \cap D_{A_{k}} > D_{B_{k}}$ , individual A_k is better than individual B_k. After the above comparison, the individuals in the population can be better distributed on the Pareto frontier.

Adaptive Elitist Retention Strategy

The size of the traditional elite retention strategy usually takes a fixed value, which is not conducive to the convergence of the solution set. In this paper, we adopt a strategy of adaptive elitist reservation: in the early stage of evolution, the retention scale of elitist individuals in the population is limited to increase the diversity of the next generation of individuals; in the later stage of evolution, it is gradually increased to converge to the Pareto boundary as soon as possible. During the evolution of the w generation, the retained size of the elitist individuals of the population ${| Elitist |}_{w}$ is calculated as follows:

{| Elitist |}_{w} = | Pop | * α_{w}

(12)

α_{w + 1} = α_{w} [1 + \ln (ρ + 1)]

(13)

where

$α_{w}$ and $α_{w + 1}$ are the influencing factors of the elitist retention scale in the evolution process of the w and w + 1 generations respectively,

$| Pop |$ is the population size, and

$ρ$ represents the ratio of the size of the non-dominated set in the population to $| Pop |$ .

In addition, to prevent the scale of individual elitist retention from going to extremes, when $α_{w}$ > 0.8, make $α_{w}$ = 0.8; when $α_{w}$ < 0.2, make $α_{w}$ = 0.2.

Genetic Operations

For crossover and mutation, the algorithm in this paper adopts the method of simulating binary crossover and polynomial mutation of NSGA2 to generate offspring ( 36 ). At the same time, after swapping genes between individuals, to prevent the occurrence of individuals with duplicated genes, non-duplicated genes are found according to the mapping relationship of the exchanged gene segments, and the number of mapped genes is replaced by the number of duplicated genes in the non-exchanged segments. For example, when a fragment (3,4,5,6) of individual A₁ (1,2,3,4,5,6,7,8) is allelic exchanged with a fragment (8,1,7,4) of individual A₂ (3,5,8,1,7,4,2,6), non-repetitive genes need to be found according to the mapping relationship of the exchanged gene fragments, and the mapping relationship is (1⇄4⇄6,8⇄3,7⇄5), and change the number of mapped genes to the number of repeating genes in non-exchange segments to avoid gene segment duplication, and finally individual A₁ becomes (6,2,8,1,7,4,5,3).

Population Combine

The elite individuals selected by the adaptive elite retention strategy in the parent population are mixed with the offspring generated by crossover and mutation in the parent population to form the next generation population.

The Full Procedure of ANSGA2-DS

The overall structure for addressing the bi-objective optimization model of the disrupted departure flight recovery problem using the suggested ANSGA2-DS is given as follows:

Algorithm 2. ANSGA2-DS overall structure
Input: The disrupted departure flight recovery problem data, population size N_p, crossover probability $p_{c}$ and mutation probability $p_{m}$ , the maximum number of generations of the algorithm $GE N_{max}$ Output: The non-dominated solutions of departure flight recovery problem //Initialization Create the initial population P of size Np randomly; Constraint handling for P; Calculate the objective function value; //Main loop Set w=0; while $w < GE N_{max}$ do The improved fast domination sorting strategy: Sort individuals in P; Generate non-dominated ranks of individuals ${rank}_{A_{k}}$ and dominance strength among individuals $ξ_{A_{k}}$ Crowding distance calculation: calculate crowding distance $D_{A_{k}}$ considering variance; Adaptive elitist retention strategy: ${\| Elitist \|}_{w}$ individuals in the population are selected directly from P into the next generation population; Genetic operations: generate offspring population Q; Constraint handling for Q; Calculate the objective function value for Q; Population combine:R = P∪Q, update P with the top N_p individuals of R; Set w=w+1 end while The non-dominated solutions in P are the final solutions.

Algorithm 2. ANSGA2-DS overall structure

Input: The disrupted departure flight recovery problem data, population size N_p, crossover probability

p_{c}

and mutation probability

p_{m}

, the maximum number of generations of the algorithm

GE N_{max}

Output: The non-dominated solutions of departure flight recovery problem
//Initialization
Create the initial population P of size Np randomly;
Constraint handling for P;
Calculate the objective function value;
//Main loop
Set w=0;
while

w < GE N_{max}

do
The improved fast domination sorting strategy: Sort individuals in P;
Generate non-dominated ranks of individuals

{rank}_{A_{k}}

and dominance strength among individuals

ξ_{A_{k}}

Crowding distance calculation: calculate crowding distance

D_{A_{k}}

considering variance;
Adaptive elitist retention strategy:

{| Elitist |}_{w}

individuals in the population are selected directly from P into the next generation population;
Genetic operations: generate offspring population Q;
Constraint handling for Q;
Calculate the objective function value for Q;
Population combine:R = P∪Q, update P with the top N_p individuals of R;
Set w=w+1
end while
The non-dominated solutions in P are the final solutions.

Computational Results

In this part, we take over the computational results of applying the proposed bi-objective model combined with the ANSGA2-DS algorithm in three scenarios.

Experimental Data

In this paper, three departure flight schedule scenarios are used to test the model and the algorithm’s efficacy. These scenarios are designed based on the operation data of a Chinese airline in Fuzhou airport in 2021. The information of the three scenarios is presented in Table 1. The disruption magnitudes of the three scenarios increase gradually.

Table 1.

Information of the Three Scenarios

Scenarios	Disrupted flights	Disruption duration	Allocated slots
A	8	3 h 13 mins	8
B	14	3 h 35 mins	14
C	25	6 h 49 mins	25

The input data required by the model and the ANSGA2-DS algorithm include the original departure time, allocated slot time and number of passengers on each disrupted flight. Here we only show the detailed data of scenario A (shown in Table 2) and data of the other two more large-scale scenarios are provided in Appendix A and Appendix B.

Table 2.

Information of Scenario A

Flight ID	Origin departure	Allocated slot	No. of passengers
1	11:10	11:45	134
2	11:25	12:20	330
3	11:47	12:16	182
4	11:59	12:55	149
5	12:05	13:55	222
6	12:28	13:58	379
7	12:55	14:00	112
8	12:59	14:23	310

Performance Evaluation Metrics

We use two comparison metrics to assess and estimate the superiority of the suggested model and ANSGA2-DS. More specifically, all iterations’ outcomes will be reported, and then metrics will be computed for each set of created solutions for each approach.

The Metric of the Price of Fairness

To quantify the trade-off between total airline delay cost and total passenger delay time, we apply the metric of the price of fairness by Zografos and Jiang ( 43 ). In our bi-objective model, we can regard the total airline delay cost as an efficiency indicator, and the total passenger delay time as a fairness indicator. For each Pareto solution, we can calculate the price of fairness F(T) at a given fairness level (T) according to Equation (15):

F (T) = (C (T) - C^{*}) / C^{*}

(14)

where C(T) means the value of total airline delay cost at the total passenger delay time of T, and $C^{*}$ means the optimum total airline delay cost value.

Inverted Generational Distance (IGD)

Mathematically, IGD is defined as $IGD = \frac{\sqrt{\sum_{i = 1}^{| P^{*} |} d_{i}^{2}}}{| P^{*} |}$

where

$P^{*}$ denotes the set of true Pareto solutions,

$| P^{*} |$ is the number of solutions in $P^{*}$ , and

$d_{i}$ represents the Euclidean distance between ith solution in $P^{*}$ and its nearest solution in Pareto front obtained by the algorithm.

It is a measure of the convergence and diversity of the algorithm. The smaller the IGD value, the closer the solutions obtained by the algorithm approximate the true Pareto frontier ( 44 ).

Evaluating the Trade-Off in Slot Scheduling

The results of the proposed bi-objective model when solved by ECA using CPLEX OPL software are discussed in this section. Table 3 displays the outcomes of scenario A. Figure 4 depicts the efficient frontier for each slot. As is shown in Table 3 and Figure 4, we observe that with the value of z changing, the values of $f_{1}$ and $f_{2}$ change oppositely. When the value of z reaches a certain threshold, the value of $f_{1}$ will converge to the optimal value while $f_{2}$ will keep increasing. The optimal value (minimum) of total delay cost and the ideal value (minimum) of delay time goal, respectively, are represented by the top left-hand side and bottom right-hand side points of the efficient bounds in Figure 4. This establishes that there is a cost–time trade-off, and the objective values achieved are saved to determine the efficient frontier.

Table 3.

Results of ε-Constraint Approach (ECA) in Scenario A with Constraint $f_{2} \leq z$

ECA	Scenario A
ECA	$f_{1}$	$f_{2}$
Minimize $f_{1}$	134,789.56	157,940
Minimize $f_{2}$	144,637.19	149,608
$z_{1}$ =150,000	144,637.19	149,648
$z_{2}$ =152,000	140,620.12	151,725
$z_{3}$ =154,000	137,502.8	153,952
$z_{4}$ =156,000	134,858.23	155,891
$z_{5}$ =158,000	134,789.56	157,940
$z_{6}$ =160,000	134,789.56	159,834
Computation time (seconds)	14.57

Table 4 expounds the solution found by FSFS (first scheduled, first serve) and the Pareto optimal solution set found by our proposed method. Each vector denotes a feasible solution to the rescheduling problem. The two underlined values represent the minimum of total delay cost and total delay time, respectively. From Table 4, we can calculate that the total airline delay cost is decreased by 52.17% in solution 2 compared with the FSFS solution, and the total passenger delay time is reduced by 29.51% in solution 3 compared with the FSFS solution. These results suggest that the proposed bi-objective model is well able to decrease the airline delay cost and the passenger delay time.

Table 4.

Pareto set of Scenario A

Flight ID	Origin departure time	FSFS	Pareto frontiers
Flight ID	Origin departure time	FSFS	Solution 1	Solution 2	Solution 3
1	11:10	11:45	12:20	12:20	11:45
2	11:25	12:20	11:45	11:45	12:55
3	11:47	12:16	14:00	13:55	12:20
4	11:59	12:55	13:58	12:16	12:16
5	12:05	13:55	12:16	14:00	14:00
6	12:28	13:58	12:55	14:23	13:58
7	12:55	14:00	14:23	13:58	13:55
8	12:59	14:23	13:55	13:55	14:23
Total airline delay cost ($)		282,825.07	140,620.12	135,268.1	144,637.19
Total passenger delay time (mins)		212,552	151,725	157,940	149,808

Note: FSFS = first scheduled, first serve.

When comparing the FSFS solution to other positions of the bar, Figures 5 and 6 show the value of replacement that each airline delay cost (or passenger delay time) is gaining or losing specifically manifested in the scope of replacement. Figure 5 represents the outcome of point 1 in Figure 4, whereas Figure 6 represents the result of point 2 in Figure 4. The ideal airline delay cost schedule is indicated by point 1, while the optimum passenger delay time is indicated by point 2. A positive value of the change in displacements suggests a higher schedule substitute for the associated airline, while a negative value indicates a lesser schedule displacement for the corresponding airline. As shown in Figure 5, the passenger delay time of flight 8, 2, 5, 6 lowers in solution 3. Despite the other four flights’ passenger wait times rising, the total delay cost decreases. Furthermore, we find that for the FSFS slot requests, four airlines will face greater schedule displacement and airline delay costs in the instance under discussion. Four airlines will have lower airline delay costs if a schedule with superior delay time performance (point 2) is chosen above the optimal airline delay cost (point 1). The price of fairness in our bi-objective model indicates the additional total airline delay cost incurred so as to achieve a certain level of total passenger wait time, expressed as a percentage of the optimal total airline delay cost.

For example, as to the Pareto optimal front shown in Figure 4, we can calculate the price for achieving the optimal total passenger delay time, F(149,129) = (166,294.38–135,268.1) /135268.1 = 0.1423. This result suggests that to achieve optimal fairness, that is, to minimize the average delay time of passengers, the airline needs to pay 14.23% additional delay cost based on the minimum delay cost. Obviously, the airline that makes the most money in this scenario is F06, which also has the worst overall performance.

In Table 5, we also solved the scenario B and C in the same proposed method. We can calculate that the total airline delay cost decreases by 35.51% in $f_{1}$ compared with the FSFS solution, and the total passenger delay time reduces by 20.25% in $f_{2}$ compared with the FSFS solution. In scenario C, we can calculate that the total airline delay cost decreases by 29.03% in $f_{1}$ compared with the FSFS solution, and the total passenger delay time reduces by 24.96% in $f_{2}$ compared with the FSFS solution.

Table 5.

Results of ε-Constraint Approach (ECA) in Scenario B and C with Constraint $f_{2} \leq z$

Scenario B			Scenario C
ECA	$f_{1}$	$f_{2}$	ECA	$f_{1}$	$f_{2}$
Minimize $f_{1}$	251,490.85	293,635	Minimize $f_{1}$	524,925.72	479,042
Minimize $f_{2}$	300,049.39	243,765	Minimize $f_{2}$	609,741.97	416,997
FSFS	389,964.38	301,887	FSFS	739,695.86	638,448
Z1=244,000	300,049.39	243,765	Z1=417,000	609,741.97	416,997
Z2=264,000	287,625.03	263,971	Z2=428,000	581,085.55	427,635
Z3=284,000	263,952.44	283,860	Z3=439,000	568,684.12	435,621
Z4=304,000	251,490.85	293,835	Z4=450,000	542,405.67	449,236
Z5=324,000	251,490.85	323,900	Z5=461,000	529,292.39	460,832
Z6=344,000	251,490.85	333,918	Z6=480,000	524,925.72	479,042
Computation time(seconds)	345.91		Computation time (seconds)	9,316.28

Note: FSFS = first scheduled, first serve.

In reality, different values of ε may be used to do various comparisons. As a result, any airline’s winner or loser status may shift. When making slot scheduling decisions, the information in Figures 5 and 6 is particularly useful since it clearly illustrates for each stakeholder (airline) the benefits or sacrifices that must be made when deciding on an adequate level of fairness. As a result, providing dis-aggregated information for each flight improves airline and passenger preference for scheduling choices.

Performance of the ANSGA2-DS Algorithm

In this subsection, to verify the proposed algorithm, we use the same data from three departure flight schedule scenarios. In ANSGA2-DS, the Taguchi approach examines the performance of critical parameter combinations. Then, the results of ANSGA2-DS and other algorithms are compared, and the superiority of the proposed algorithm is demonstrated. All the computations are performed on a computer with Intel i5-5200U CPU and 4GB of RAM.

Identifying Efficient Parameters

It is generally known that choosing the right parameters has a significant impact on the algorithm’s computing performance. Before we apply the ANSGA2-DS algorithm, the selection of parameter values turns into a key issue. Three essential factors in the proposed ANSGA2-DS are population size N_p, crossover probability $p_{c}$ , and mutation probability $p_{m}$ . On the basis of a large-scale problem, the Taguchi design method ( 45 ) is carried out to determine the optimal combination of the three critical parameters, which effectively determines the orthogonal experiment table, reduces experimental testing ( 46 ), and ensures parameter setting stability. Both Minitab software and literature relate to the specific procedure ( 47 ).

We adjust the parameter in the algorithm and observe the number of solutions, solution time, and quality. The number of solutions, solution time, and average gap with the optimal value are selected to assess the parameter combinations by executing each parameter combination (see Table 6 and Figure 7) numerous times. The gap $G$ from the optimal known value $V_{O}$ to the current value $V_{C}$ , as calculated by the following formula $G = \frac{V_{O} - V_{C}}{V_{O} + V_{C}} * 100 %$ ( 48 ). According to the principle of maximizing the number of solutions, minimizing the solution time and minimizing the average gap with the optimal value, the best parameter result is N_p = 80, $p_{c}$ = 0.8, and $p_{m}$ = 0.2.

Table 6.

Variations in Parameter Values and Results

Experiment No.	Parameters			Solution time/s	Number of solutions	Min $f_{1}$	Min $f_{2}$	The average gap/%
Experiment No.	N_p	$p_{m}$	$p_{c}$	Solution time/s	Number of solutions	Min $f_{1}$	Min $f_{2}$	The average gap/%
1	40	0.1	0.8	92.73	6	252,519.67	265,044	4.85
2	40	0.2	0.3	64.71	5	253,105.21	270,816	7.36
3	40	0.3	0.5	76.58	4	252,137.38	265,281	4.80
4	80	0.1	0.3	158.69	8	253,409.55	275,075	6.52
5	80	0.2	0.5	182.62	7	253,223.97	264,024	4.73
6	80	0.3	0.8	220.19	7	252,830.51	262,543	3.99
7	120	0.1	0.5	248.54	6	253,572.43	267,058	5.49
8	120	0.2	0.8	328.45	8	252,246.05	263,460	4.12
9	120	0.3	0.3	236.78	8	252,798.59	280,937	8.47

Solution Quality: Comparison with Other Algorithms

To investigate the performance of the proposed ANSGA2-DS, the unimproved NSGA2 and a multi-objective evolutionary algorithm based on dominance and decomposition (MOEAD) (49) are set up to deal with the same problems. As a new multi-objective optimization algorithm, MOEAD shows excellent performance in some multi-objective problems (50, 51). Since NSGA2 and MOEAD are both classic multi-objective optimization algorithms, we compare them with the ANSGA2-DS in this paper. Table 7 depicts the results of the ANSGA2-DS with the traditional first-schedule-first-serve method (FSFS) and the ε-constraint approach (ECA) that converts multiple targets to single targets in three different scenarios. During the final test run, all solutions compute each metric, and the results are shown in Figure 8 which expounds the distribution of the solutions obtained by the three algorithms in their respective scenarios, which all run under the same algorithm parameter settings.

Table 7.

Computational Results of ANSGA2-DS

	Scenario A	Scenario B	Scenario C
FSFS solution
$f_{1}$	282,825.07	389,964.38	739,695.86
$f_{2}$	212,552	301,887	638,448
ECA solution
Optimum of $f_{1}$	134,789.56	251,490.85	524,925.70
Optimum of $f_{2}$	149,608	243,765	416,997
Pareto set
No. of Pareto solutions	7	6	4
Optimum of $f_{1}$	135,268.1	253,142.78	531,868.435
Optimum of $f_{2}$	149,832	259,467	436,982
Maximum price of fairness (F[T])	14.23%	5.61%	4.36%
The average gap with ECA/%	4.88	4.71	6.26
Computation time (seconds)	23.42	40.73	149.95

Note: FSFS = first scheduled, first serve; ECA = ε-constraint approach.

As shown in Figure 8 and Table 8, ANSGA2-DS performs well in producing a good solution in the three departure flight schedule scenarios. The above findings are examined from the three perspectives listed below. First, consider that the elitist storage approach, which is based on the enhancement of the scale selection strategy (i.e., ANSGA2-DS and NSGA2), is clearly better than traditional NSGA2. Second, in all three scenarios, the Pareto number and frontier of ANSGA2-DS are generally better than the NSGA2 and MOEAD. It is worth mentioning that as the number of solved flights grows, the effects of the proposed algorithm become more prominent. Third, whether the optimal value of each objective function or the maximum price of fairness, ANSGA2-DS is better than NSGA2 and MOEAD. In summary, constraint processing, the rapid dominance intensity ranking method, and the adaptive elitist retention strategy improve the proposed algorithm’s ability, and the Pareto elitist preservation mechanism can retain optimum solutions during the iterative process, avoiding the optimal individual being destroyed by the hybrid operation.

Table 8.

Comparison between the Optimal Value of the Three Algorithms and the Maximum Price of Fairness (F[T]).

	ANSGA2-DS	NSGA2	MOEAD
Scenario A
Optimum of $f_{1}$	135,268.1	136,414.04	138,989.7
Optimum of $f_{2}$	149,832	154,586	157,940
F(T)	14.23%	19.38%	23.71%
Scenario B
Optimum of $f_{1}$	253,142.78	254,551.42	255,670.78
Optimum of $f_{2}$	259,467	262,036	265,789
F(T)	5.61%	7.05%	8.33%
Scenario C
Optimum of $f_{1}$	531,868.435	536,551.42	540,642.78
Optimum of $f_{2}$	436,982	442,036	457,467
F(T)	4.36%	5.82%	7.12%

Note: ANSGA2-DS = adaptive non-dominated sorting genetic algorithm-II based on dominant strengths; NSGA2 = non-dominated sorting genetic algorithm II; MOEAD = multi-objective evolutionary algorithm based on dominance and decomposition.

As shown in Figures 9 and 10, these two figures compare the passenger delay time and delay cost of each flight obtained by FSFS and the ANSGA2-DS, NSGA2, and MOEAD algorithms in scenario C. From these two figures, we can see that the solution set obtained by the multi-objective algorithm is overall better than the solution obtained by FSFS, and among the three multi-objective algorithms, the solution obtained by ANSGA2-DS is relatively better. However, even in many schemes, there are plans for flights that are worse than the solution obtained by FSFS, such as flight 2 and flight 10. This is because in the multi-objective scheme, flight 2 is sacrificed in exchange for the cost of delay of other flight being reduced. In overall quantity, 72% of flight plans are improved. In addition, the degree of improvement in the results is also related to the model of the aircraft, which has different passenger capacity.

To assess the convergence and distribution of the three algorithms, the reverse generation distances of the results of the three algorithms in solving different scenarios are counted, and the results are shown in Table 9. The parameter settings for operation are the same as those set in Section 5.4.1. IGD can reflect the convergence and diversity of the algorithm. In general, ANSGA2-DS is absolutely superior to NSGA2 and MOEAD in the reverse generation distance value in different scale scenarios. The results prove that the ANSGA2-DS algorithm is superior in processing the flight recovery problem in the scenario of large interruption.

Table 9.

Comparison of IGD in different scenarios of three algorithms

	ANSGA2-DS	NSGA2	MOEAD
Scenario A	1.1807e+05	1.3596e+05	1.5841e+05
Scenario B	2.8329e+05	2.9105e+05	2.9817e+05
Scenario C	6.4822e+04	6.7045e+05	7.4161e+05

Sensitivity analysis

This research uses the proposed model to conduct a sensitivity analysis. After considering the above simulation experiment results, we believe that the cost functions associated with passenger delay have a greater impact on the objective function. Therefore, a sensitivity analysis of the above parameters is carried out. In addition, the sensitivity analysis is performed by changing (increasing or decreasing) the value of one parameter at a time, while leaving the other parameters unchanged.

We adjust the price in the timeframe per time interval of the segmentation function by −20%, −10%, +10%, +20%, +40%. For example, when the delay time is 120 to 150 min, the amount of compensation is $18 increases by 20% ($18 = $15 × 120%). According to the sensitivity analysis values of the previous parameters, we use OBJ’/OBJ as the sensitivity analysis measurement, where OBJ is the objective function value under the original parameters, and OBJ’ is the objective function value after the parameter changes. The sensitivity analysis results are shown in Table 10.

Table 10.

Sensitivity Analysis Results

Adjustment ranges	Optimum of $f_{1}$	OBJ’/OBJ $f_{1}$	Optimum of $f_{2}$	OBJ’/OBJ $f_{2}$
Scenario A
−20%	134,643.28	0.99	150,746	1.01
−10%	134,858.59	0.99	149,868	1.00
+10%,	135,236.56	1.00	150,131	1.00
+20%	135,926.72	1.00	156,129	1.04
+40%	150,482.04	1.11	158,438	1.06
Scenario B
−20%	249,095.67	0.98	270,251	1.04
−10%	251,560.84	0.99	272,442	1.05
+10%	251,565.09	0.99	271,665	1.05
+20%	272,743.67	1.08	283,802	1.09
+40%	296,756.25	1.17	285,209	1.10
Scenario C
−20%	516,413.94	0.97	423,635	0.97
−10%	525,633.27	0.99	424,143	0.97
+10%,	530,812.63	1.00	441,311	1.01
+20%	664,409.10	1.25	452,601	1.03
+40%	705,267.17	1.33	503,159	1.15

Through sensitivity analysis, the following results can be obtained: the range of OBJ’/OBJ $f_{1}$ is from 0.97 to 1.33, and the range of OBJ’/OBJ $f_{2}$ is from 0.97 to 1.15. Objective function 1 is more sensitive to changes in the cost function than objective function 2. Besides, the larger the scenario size, the greater the effect of the magnitude of the cost function on sensitivity. Therefore, the choice of the delay cost function does not have a particularly significant impact on the results of this paper’s model under the same schedule.

Concluding Remarks

In this paper, we focus on the departure slot reassignment problem and develop a bi-objective integer programming model. The objective of the proposed model, compared with previous studies, is to achieve an evaluation which balances two basic preferences of the airline and passengers, namely the total airline delay cost and the total passenger delay time. An adaptive non-dominated sorted genetic algorithm-II based on dominant strengths (ANSGA2-DS) is presented by using a fast dominance ranking method, a new crowding distance considering the variance and the adaptive elitist retention strategy. Many experiments are carried out based on real data from the flight plan of a certain airport in China. The computational results from the application show that the ANSGA2-DS algorithm not only reduces the total delay cost of airlines, but also shortens the total delay time of passengers compared with the FSFS solution. The results are close to the results obtained by the ε-constraint approach. Compared with other algorithms, the ANSGA2-DS algorithm shows better performance in the optimal value of the objective function, the maximum fair price of the resulting solution, convergence, and diversity. A better time slot allocation scheme can be obtained in solving the departure flight recovery problem, which has certain guiding significance.

Although the proposed bi-objective model can effectively improve the recovery performance of the disrupted departure flights, there is still much work that can be improved in the future. For instance, in this paper, we assume that the aircraft rotation, aircraft maintenance, and crew pairing remain unchanged. However, when considering aircraft rotation, aircraft maintenance, repairing crew, and so on, the delay issue would become more complicated. Finally, constraints related to weather or airport capacity uncertainty can be integrated into the model to manage their possible unavailability more effectively.

Supplemental Material

sj-doc-1-trr-10.1177_03611981231182714 – Supplemental material for Reassigning Departure Slots with Preferences of the Airline and Passengers

Supplemental material, sj-doc-1-trr-10.1177_03611981231182714 for Reassigning Departure Slots with Preferences of the Airline and Passengers by Kejia Chen, Juntao Wu and Lixi Yang in Transportation Research Record

Footnotes

Author Contributions

The authors confirm contribution to the paper as follows: study conception and design: Kejia Chen; data collection: Juntao Wu; analysis and interpretation of results: Juntao Wu, Lixi Yang; draft manuscript preparation: Juntao Wu, Lixi Yang. All authors reviewed the results and approved the final version of the manuscript.

Declaration of Conflicting Interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: Funding: The presented research work was supported by the National Social Science Foundation of China (Grant No. 18BGL003).

ORCID iDs

Juntao Wu

Lixi Yang

Supplemental Material

Supplemental material for this article is available online.

References

Civil Aviation Administration of China. Development Statistics Bulletin of Civil Aviation Industry in 2020. http://www.caac.gov.cn/en/HYYJ/NDBG/202202/t20220222_211894.html. Accessed June 10, 2021.

Manyem

Disruption Recovery at Airports: Ground Holding, Curfew Restrictions and an Approximation Algorithm. Journal of the Operations Research Society of China, Vol. 9, 2021, pp. 819–852. https://doi.org/10.1007/s40305-020-00338-1.

Zhong

Guan

Zhang

Jiang

Fan

Deng

A Bi-Objective Integer Programming Model for Partly-Restricted Flight Departure Scheduling. Plos One, Vol. 13, No. 5, 2018, p. e0196146. https://doi.org/10.1371/journal.pone.0196146.

Xie

Wang

Airline Disruption Management: A Review of Models and Solution Methods. Engineering, Vol. 7, No. 4, 2021, pp. 435–447. https://doi.org/10.1016/j.eng.2020.08.021.

Serhan

Lee

Yoon

S. W.

Minimizing Airline and Passenger Delay Cost in Airport Surface and Terminal Airspace Operations. Journal of Air Transport Management, Vol. 73, 2018, pp. 120–133. https://doi.org/10.1016/j.jairtraman.2018.07.001.

Yan

S. Y.

Chen

Y. -C.

Flight Rescheduling, Fleet Rerouting and Passenger Reassignment for Typhoon Disruption Events. Transportation Letters-the International Journal of Transportation Research, Vol. 14, No. 8, 2022, pp. 818–837. https://doi.org/10.1080/19427867.2021.1950266.

Postorino

M. N.

Mantecchini

Malandri

Paganelli

A Methodological Framework to Evaluate the Impact of Disruptions on Airport Turnaround Operations: A Case Study. Case Studies on Transport Policy, Vol. 8, No. 2, 2020, pp. 429–439. https://doi.org/10.1016/j.cstp.2020.03.007.

Rhodes-Leader

L. A.

Nelson

B. L.

Onggo

B. S.

Worthington

D. J.

A Multi-Fidelity Modelling Approach for Airline Disruption Management Using Simulation. Journal of The Operational Research Society, Vol. 73, No. 10, 2022, pp. 2228–2241. https://doi.org/10.1080/01605682.2021.1971574.

Stephane

Cynthia

Flight Operations Recovery: New Approaches Considering Passenger Recovery. Journal of Scheduling, Vol. 9, No. 3, 2006, pp. 279–298. https://doi.org/10.1007/s10951-006-6781-0.

10.

Nabil

Aida

Ali

The Integrated Aircraft Routing Problem with Optional Flights and Delay Considerations. Transportation Research Part E: Logistics and Transportation Review, Vol. 118, No. 10, 2018, pp. 355–375. https://doi.org/10.1016/j.tre.2018.08.002.

11.

Song

Zhao

Integrated Recovery of Aircraft and Passengers after Airline Operation Disruption Based on a GRASP Algorithm. Transportation Research Part E: Logistics and Transportation Review, Vol. 87, 2016, pp. 97–112. https://doi.org/10.1016/j.tre.2016.01.002.

12.

Şafak

Ö.

Çavuş

Ö.

Selim Aktürk

Multi-Stage Airline Scheduling Problem with Stochastic Passenger Demand and Non-Cruise Times. Transportation Research Part B-Methodological, Vol. 114, 2018, pp. 39–67. https://doi.org/10.1016/j.trb.2018.05.012.

13.

Liang

Xiao

Qian

Karichery

A Column Generation-Based Heuristic for Aircraft Recovery Problem with Airport Capacity Constraints and Maintenance Flexibility. Transportation Research Part B-Methodological, Vol. 113, 2018, pp. 70–90. https://doi.org/10.1016/j.trb.2018.05.007.

14.

Sinclair

Cordeau

J. F.

Laporte

Improvements to a Large Neighborhood Search Heuristic for an Integrated Aircraft and Passenger Recovery Problem. European Journal of Operational Research, Vol. 233, No. 1, 2013, pp. 234–245. https://doi.org/10.1016/j.ejor.2013.08.034.

15.

Marla

Vaaben

Barnhart

Integrated Disruption Management and Flight Planning to Trade Off Delays and Fuel Burn. Transportation Science, Vol. 51, No. 1, 2015, pp. 88–111. https://doi.org/10.1287/trsc.2015.0609.

16.

McCarty

L. A.

Cohn

A. E. M.

Preemptive Rerouting of Airline Passengers under Uncertain Delays. Computers and Operations Research, Vol. 9, 2017, pp. 1–11. https://doi.org/10.1016/J.COR.2017.09.001.

17.

Hassan

L. K.

Santos

B. F.

Vink

Airline Disruption Management: A Literature Review and Practical Challenges. Computers and Operations Research, Vol. 127, 2020, p. 105137. https://doi.org/10.1016/J.COR.2020.105137.

18.

Erkan

Erkip

N. K.

Safak

Collaborative Decision Making for Air Traffic Management: A Generic Mathematical Program for the Rescheduling Problem. Computers and Industrial Engineering, Vol. 137, 2019, p. 106016. https://doi.org/10.1016/j.cie.2019.106016.

19.

Wang

Flight Schedule Recovery: A Simulation-Based Approach. Asia-Pacific Journal of Operational Research, Vol. 36, No. 6, 2019, p. 1940010. https://doi.org/10.1142/S0217595919400104.

20.

Evler

Asadi

Preis

Fricke

Airline Ground Operations: Schedule Recovery Optimization Approach with Constrained Resources. Transportation Research Part C:Emerging Technologies, Vol. 128, 2021, p. 103129. https://doi.org/10.1016/j.trc.2021.103129.

21.

Santos

B. F.

Wormer

M. M. E. C.

Achola

T. A. O.

Curran

Airline Delay Management Problem with Airport Capacity Constraints and Priority Decisions. Journal of Air Transport Management, Vol. 63, 2017, pp. 34–44.

22.

Zhang

Desai

Lau

A Math-Heuristic Algorithm for the Integrated Air Service Recovery. Transportation Research Part B-Methodological, Vol. 84, 2015, pp. 211–236. https://doi.org/10.1016/j.trb.2015.11.016.

23.

Fieldsend

J. E.

Singh

Pareto Evolutionary Neural Networks. IEEE Transactions on Neural Networks, Vol. 16, No. 2, 2013, pp. 338–354. https://doi.org/10.1109/TNN.2004.841794.

24.

Liu

Qin

Zhang

Yao

Wang

Ouyang

A Region Search Evolutionary Algorithm for Many-Objective Optimization. Information Sciences, Vol. 488, 2019, pp. 19–40. https://doi.org/10.1016/j.ins.2019.03.016.

25.

Liao

Zhang

Song

Multiple Objective Solution Approaches for Aircraft Rerouting under The Disruption of Multi-Aircraft. Expert Systems With Applications, Vol. 83, 2017, pp. 283–299. https://doi.org/10.1016/j.eswa.2017.04.031.

26.

Zhang

Fan

Zhang

Song

Integrated Recovery of Aircraft and Passengers with Passengers’ Willingness under Various Itinerary Disruption Situations. Computers and Industrial Engineering, Vol. 161, 2021, p. 107664. https://doi.org/10.1016/j.cie.2021.107664.

27.

Castelli

Pellegrini

Pesenti

Airport Slot Allocation in Europe: Economic Efficiency and Fairness. International Journal of Revenue Management, Vol. 6, No. 1–2, 2012, pp. 28–44. https://doi.org/10.1504/ijrm.2012.044514.

28.

Barnhart

Fearing

Odoni

A. R.

Vaze

Demand and Capacity Management in Air Transportation. EURO Journal on Transportation and Logistics, Vol. 1, No. 1–2, 2012, pp. 135–155. https://doi.org/10.1007/s13676-012-0006-9.

29.

Androutsopoulos

K. N.

Madas

M. A.

Being Fair or Efficient? A Fairness-Driven Modeling Extension to the Strategic Airport Slot Scheduling Problem. Transportation Research Part E: Logistics and Transportation Review, Vol. 130, 2019, pp. 37–60. https://doi.org/10.1016/j.tre.2019.08.010

30.

Manyem

Disruption Recovery at Airports: Integer Programming Formulations and Polynomial Time Algorithms. Discrete Applied Mathematics, Vol. 242, 2017, pp. 102–117. https://doi.org/10.1016/j.dam.2017.11.010.

31.

Tian

Q. N.

K. P.

W. L.

D. Y.

Optimization Operation of Disrupted Flights by Improving Column Generation Algorithm. Systems Engineering, Vol. 39, No. 11, 2019, pp. 2815–2827. https://doi.org/10.12011/1000-6788-2018-0472-13.

32.

Gao

Zhang

A Novel Rescheduling Algorithm for the Airline Recovery with Flight Priorities and Airport Capacity Constraints. Asia-pacific Journal of Operational Research,Vol. 38, No. 5, 2021, p. 2140025. https://doi.org/10.1142/S021759592140025X.

33.

Cook

Tanner

Meise

Dynamic Cost Indexing-Managing Airline Delay Costs. Journal of Air Transport Management, Vol. 15, 2009, pp. 26–35. https://doi.org/10.1016/j.jairtraman.2008.07.001.

34.

Cook

Tanner

Lawes

The Hidden Cost of Airline Unpunctuality. Journal of Transport Economics and Policy, Vol. 46, No. 2, 2012, pp. 157–173. https://www.jstor.org/stable/24396360.

35.

García

S. G.

Montequín

V. R.

Piloñeta

M. D.

Lougedo

S. T.

Multi-Objective Optimization of Steel Off-Gas in Cogeneration Using the ε-Constraint Method: A Combined Coke Ovenand Converter Gas Case Study. Energies, Vol. 14, 2021, p. 2741. https://doi.org/10.3390/en14102741.

36.

Deb

Pratap

Agarwal

Meyarivan

A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, Vol. 6, No. 2, 2002, pp. 182–197. https://doi.org/10.1109/4235.996017.

37.

Chica

Bautista

De Armas

Benefits of Robust Multiobjective Optimization for Flexible Automotive Assembly Line Balancing. Flexible Services and Manufacturing Journal, Vol. 31, No. 1, 2019, pp. 75–103. https://doi.org/10.1007/s10696-018-9309-y.

38.

Souier

Dahane

Maliki

An NSGA-II-based Multiobjective Approach for Real-Time Routing Selection in a Flexible Manufacturing System under Uncertainty and Reliability Constraints. International Journal of Advanced Manufacturing Technology, Vol. 100, No. 9–12, 2019, pp. 2813–2829. https://doi.org/10.1007/s00170-018-2897-6.

39.

Sahnoun

M. H.

Bettayeb

Bassetto

S. J.

Tollenaere

Simulation-based Optimization of Sampling Plans to Reduce Inspections while Mastering the Risk Exposure in Semiconductor Manufacturing. Journal of Intelligent Manufacturing, Vol. 27, No. 6, 2016, pp. 1335–1349. https://doi.org/10.1007/s10845-014-0956-x

40.

Alavidoost

M. H.

Tarimoradi

Zarandi

M. F.

Bi-objective Mixed-Integer Nonlinear Programming for Multi-Commodity Tri-Echelon Supply Chain Networks. Journal of Intelligent Manufacturing, Vol. 29, No. 4, 2018, pp. 809–826. https://doi.org/10.1007/s10845-015-1130-9.

41.

Jiang

Kwong

C. K.

Chan

C. Y.

Yung

K. L.

A Multi-Objective Evolutionary Approach for Fuzzy Regression Analysis. Expert Systems with Applications, Vol. 130, 2019, pp. 225–235. https://doi.org/10.1016/j.eswa.2019.04.033.

42.

Dai

Tang

Giret

Salido

M. A.

Multi-objective Optimization for Energy-Efficient Flexible Job Shop Scheduling Problem with Transportation Constraints. Robotics and Computer-integrated Manufacturing, Vol. 59, 2019, pp. 143–157. https://doi.org/10.1016/j.rcim.2019.04.006.

43.

Zografos

K. G.

Jiang

A Bi-Objective Efficiency-Fairness Model for Scheduling Slots At Congested Airports. Transportation Research Part C: Emerging Technologies, Vol. 102, No. 5, 2019, pp. 336–350. https://doi.org/10.1016/j.trc.2019.01.023.

44.

Figueiredo

E. M. N.

Ludermir

T. B.

Bastos-Filho

C. J. A.

Many Objective Particle Swarm Optimization. Information Sciences. Vol. 374, 2016, pp. 115–134. https://doi.org/10.1016/j.ins.2016.09.026.

45.

Montgomery

D. C.

Design & Analysis of Experiments. John Wiley & Sons, New York, 2008.

46.

Karimi

Ardalan

Naderi

Mohammadi

Scheduling Flexible Job-Shops with Transportation Times: Mathematical Models and a Hybrid Imperialist Competitive Algorithm. Applied Mathematical Modelling, Vol. 41, No. 1, 2016, pp. 667–682. https://doi.org/10.1016/j.apm.2016.09.022.

47.

Naderi

Ghomi

S. M. T. F.

Aminnayeri

A High Performing Meta-Heuristic for Job-Shop Scheduling with Sequence-Dependent Setup Times. Applied Soft Computing, Vol. 10, No. 3, 2009, pp. 703–710. https://doi.org/10.1016/j.asoc.2009.08.039.

48.

Bach

Hasle

Wøhlk

A Lower Bound for the Node, Edge, and Arc Routing Problem. Computers and Operations Research, Vol. 40, 2013, pp. 943–952. https://doi.org/10.1016/j.cor.2012.11.014.

49.

Zhang

Hui

MOEA/D: A Multiobjective Evolutionary Algorithm Based on Decomposition. IEEE Transactions on Evolutionary Computation, Vol. 11, No. 6, 2008, pp. 712–731. https://doi.org/10.1109/tevc.2007.892759.

50.

Han

Jin

An Adaptive Decomposition-Based Evolutionary Algorithm for Many-Objective Optimization. Information Sciences, Vol. 491, 2019, pp. 204–222. https://doi.org/10.1016/j.ins.2019.03.062.

51.

Gee

S. B.

Arokiasami

W. A.

Jiang

Tan

K. C.

Decomposition-based Multi-Objective Evolutionary Algorithm for Vehicle Routing Problem with Stochastic Demands. Soft Computing, Vol. 20, No. 9, 2016, pp. 3443–3453. https://doi.org/10.1007/s00500-015-1830-2.

Supplementary Material

Please find the following supplemental material available below.

For Open Access articles published under a Creative Commons License, all supplemental material carries the same license as the article it is associated with.

For non-Open Access articles published, all supplemental material carries a non-exclusive license, and permission requests for re-use of supplemental material or any part of supplemental material shall be sent directly to the copyright owner as specified in the copyright notice associated with the article.

0.00 MB

0.06 MB