Optimization of Flight Rescheduling Problem under Carbon Tax

Abstract

The flight rescheduling problem is one of the major challenges of air traffic issue. Unforeseen bad weather conditions stimulate air traffic congestion and make the initial scheduling infeasible, resulting in significant economic losses for passengers and airlines. Furthermore, due to rigorous environmental legislations, flight rescheduling becomes a more complicated problem, as it has to deal with flight delays on the one hand, and carbon emissions on the other hand. In this paper, we address the flight rescheduling problem with an environmental requirement subject to the air capacity limitation due to bad weather conditions. A new strategy is proposed to minimize the disruption effects on planned flights, which adopted ground delay, longer route change, flight cancellation, as well speed adjustment to arrive at a scheduled time. Firstly, the objective of this study is to determine the economical flights plan in line with the new available air capacity. Secondly, by considering the environmental impact of the kerosene consumption, we illustrate the contribution of an economical decision to aircraft emissions. Experiment results are provided to show the efficiency of the proposed strategies and genetic algorithm as the used optimization method. Furthermore, the impacts of carbon tax and cost of arrival delay on the flights carbon emissions are studied.

1. Introduction

With accelerating industrialization, global transportation and urbanization, many countries are faced with tremendous pressure for containing enormous carbon emissions and air pollution while maintaining high economic growth. Different sectors in the world are responsible for carbon dioxide emissions (CO₂). The CO₂ emissions in the industrial sector were 463.35 million tons in 2016 [1,2,3]. Overall, the industrial activities are responsible for more than 50% of the total global CO₂ emissions [4]. The transportation sector contributes with $14\%$ to the total global CO₂ emissions [5,6,7]. One of the most important activities of transportation is the aviation sector, which accounts for about 2% of the total global CO₂ emissions and about 12% of the CO₂ emissions from all transportation sources [8,9,10]. At the same time, the aircraft fleet in the world continues to increase with an exponential rate [11,12]. This increase brings into question the air traffic capacity that should adapt the growing demand, as well as the environmental sustainability in front of the pollutants amount emitted by flights. One of the primary effects for this limited-air-capacity is the almost permanent delay in flights due to frequent air navigation congestion.

According to the 2017 and 2018 studies of the European Organization for the Safety of Air Navigation ($\mathrm{EUROCONTROL}$) [13], one can notice that delays are important. The delays that are longer than $60\min$, regardless of cause, are increased in one year by $1.3\%$. In addition to the large aircraft fleet, the bad weather conditions contribute by 6.4% to the annual delays. Even if delays can be considered negligible from the point of view of a non-expert, the financial risks for the stakeholders (airlines, passengers, air controller, etc.) in the air sector are serious. For instance, the total delays cost is evaluated to be closer to $\$32.9$ billion only for flights within the US. This big loss is shared in a large part between the airline company by $\$8.3$ billion and the passengers by $\$16.7$ billion [14]. Other costs to the air traffic controllers are the cost for the airports following the use of the infrastructure. The main motivation of the present paper is to improve the air traffic flow by the sustainable decision support system taking into account the environmental impact, the interests of all stakeholders in order to minimize the total delays, and therefore significantly reducing the costs involved.

To overcome the delays and the air congestion, the balancing between the demand on the air system and the available air capacity remains a concern of the air traffic flow managers [12]. However, the bad weather conditions that are uncertain before takeoff make the initial scheduling of some flights plan infeasible, promote ground delay, and consequently contribute to the heavy congestion. The flight rescheduling problem (FRP) arises as an air traffic management issue when the flights are at the ground level. In order to develop the sustainable decision support system for the FRP, the development of a smart and environmentally friendly new rescheduling methodology is considered essential to maintain the sustainable development of air transport. Within this framework, the adoption of a new rescheduling methodology should be reducing the harmful effects of pollution as much as possible and improving the flow of air traffic [15,16].

Therefore, the purpose of this study is to propose a sustainable decision support system that can be deployed by the air stakeholders to propose the optimal rescheduling flights with minimum pollution. In other words, we aim to approach the flight rescheduling problem by using a mathematical modeling and metaheuristic optimization method with the genetic algorithm to provide an optimal rescheduling flight, that minimizes on hand the total flight delays and the global carbon quantity emitted by flights taken into account of all rescheduling strategies. The rest of this paper is structured as follows. Section 2 provides a literature review. In Section 3, the problem statement and the used notation are described. The mathematical model formulation including the objective function and the constraints are presented in Section 4. Section 5 introduces the resolution approach of $\mathrm{FRP}$ using the genetic algorithm. The performances of the presented approach are given in Section 6. In the final section, the conclusions and some perspectives are presented.

2. Literature Review

The slots allocated to flights are always changing. Taking into account the actual data pertaining to weather conditions and the exact positioning of aircrafts in the air system, the slots reallocation can be carried out. Indeed, for the committed flights (in the air) the improvement is limited to the recalculation of the passage timetable across the air sectors, but for the uncommitted flights (on the ground) an improvement is on the takeoff timetable. In many situations, the flight rescheduling including slot reallocation is necessary to balance between the air demand and available capacity. The new scheduling should satisfy, as far as possible, the different stakeholders in which each have their own set of important measures; the central authority represented by the International Civil Aviation Organization (ICAO) to limit the carbon dioxide emissions from air travel using the appropriate speed adjustment, airline companies in order to obtain the shortest path between the two airports and reallocation of reasonable takeoff slots, and passengers to reduce the delays and maximize the airline reputation. In the FRP, some constraints should be observed: The ground-delay does not exceed 4 h, the available capacity should be considered at each time slice, and the aircraft speed mode that is correlated with the amount of kerosene consumed and therefore with harmful emissions.

In the rest of this section, we survey the works dealing with air traffic management under three angles: The flight rescheduling problem in the broadest sense, the flight rescheduling problem for the uncommitted flights, the environmental aspect in the air traffic management problem.

A series of studies have dealt with $\mathrm{FRP}$ and related issues go back to the early 1980s. The management of delay at the airport level, due the unforeseen event that perturbed the initial planning, is firstly considered in [17]. Before departure, a ground delay is assigned to the affected flights until the air capacity becomes compatible with scheduled flights. Then, this work is extended by other researchers taking into account the airborne, the rerouting, and cancellation decisions [18,19,20,21]. In this regard, Andreatta and Romanin-Jacur in 1987 [18] treated the deterministic ground holding problem for the case where the congestion affected the airports and the air sector capacity is considered significant. With the same assumptions, Terrab and Odoni in 1993 [19] studied the ground holding problem with a stochastic version in which the flights come from different origins to land in a single destination that is constrained by capacity. To solve the problem, the authors adopted an exact dynamic programming approach and many heuristics by considering the capacity of arrival airport stochastic with a known probability distribution. The objective function for the ground holding problem is to minimize the cost of ground delay added to the cost of the airborne delay. For a static version of the ground holding problem, the model of objective function is firstly developed by Richetta and Odoni (1993) [20] that is extended in a dynamic version by the same authors Richetta and Odoni (1994) [21]. In addition to the minimizing of ground delay, the objective incorporates the optimization of flight time and total arrival delay. In the same context of the static decision version, Beasley et al. (2000) [22] proposed a general model for the scheduling problem at the arrival airport level that uses a mixed-integer zero–one formulation. This problem aims to decide the exact landing time for each aircraft, which should be included in a predefined time interval, while respecting the separations between planes. They provide a solution methodology based on the linear programming-based tree search and also a heuristic algorithm. For simplicity of the model, as in [23], the aircraft awaiting landing is classified according to its technical characteristics such as speed, capacity, and weight. There are other attempts to suggest additional possible objectives such as fuel consumption and noise nuisance [24,25]. In a second time, the flight rescheduling problem discussed the real case of one aircraft that performed more than one flight, in the same day, by using the above explained strategies [26,27]. The decision to change the initial planning by imposing ground delay on a flight segment causes the delay of the next flights segment, and also delays its subordinated flights [28,29]. The most discussed flight rescheduling aims to solve the air traffic congestion issue by essentially minimizing the various costs linked to airline profits and passengers satisfaction.

Although there are several research works that deal with the FRP. Only few studies have considered the speed adjustment as an alternative strategy to catch up with the delay. Indeed, in practice, the challenge for air companies is to increase their profits through the minimization of flight durations, the total delay, and the number of canceled flights. In fact, the cost optimization of flight durations aims to assign the shortest path instead of opting a speed mode (cruise speed) that is higher than the economic mode [30]. Thus, we will consider the speed adjustment as in the practice and that fill the gap concerning the FRP issue. Moreover, in practice, the speed mode is correlated with the amount of kerosene consumed and therefore with harmful emissions, which represents a great ambiguity for environmental requirements. As it is known, nowadays, environmental legislations are rigorous and the carbon emission control in most countries has become an increasing challenge. Several countries promulgated some emission regulations, such as carbon emission cap and trade, carbon taxes, and mandatory carbon emissions [31,32]. In the transport domain, the carbon tax regulation is usually imposed as a strategy for curbing the carbon emissions [33,34,35]. Indeed, several governments continued imposing extra taxes on the fuel price, such as carbon tax on kerosene [36,37,38]. The carbon tax that is implemented in the final kerosene price is called the purchase kerosene price. The carbon tax is usually presented by the percentage applied on the kerosene production price. Therefore, the carbon taxes increase the purchase kerosene prices and oblige the airline companies to reduce the kerosene consumption which implies curbing the carbon emissions [39]. Therefore, the airline companies have to face on one hand, the flight delays, on the other hand, the carbon emissions (i.e., kerosene consumption). Consequently, today, the airline companies are devoted to provide optimal speed adjustments that minimize costs of delay and kerosene consumption [40]. In the recent literature, Hamdan et al. [41] formulated the flight rescheduling problem based on the bi-objective mixed integer linear programming model in order to optimize the costs of CO₂ emissions and the total delay. The authors used the Pareto-based scalarization technique, called the weighted comprehensive criterion method, in order to minimize the different costs. Akgunduz and Kazerooni [42] introduced a non-time segmented flight rescheduling problem in order to minimize the total arrival delays. Moreover, the authors incorporated the adjustment speed and its dependence on the kerosene consumed, by proposing a resolution method based on sequential solution heuristics.

However, these papers mentioned above have not combined all the rescheduling options that complicate the rescheduling model and its resolution. Furthermore, to the best of our knowledge, no study has addressed the flight rescheduling problem under air capacity floating due to bad weather conditions by opting the ground delay, itinerary changing, speed adjustment, and cancellation decisions with environmental consideration. To fill this research gap, this work provides an optimal rescheduling flight plan that minimizes on hand the total flights delays and the global carbon quantity emitted by flights taking into account all rescheduling strategies, that represent the main paper contribution. Therefore, this work has a double objective: Determine the optimal flight plan that minimizes the cost incurred from using aircrafts and the curbing emissions. For this purpose, firstly, we aim to develop a mathematical model that describes the problem taking into account the different constraints explained above and minimizes the flight cost. Regarding the problem complexity, the flight rescheduling problem with an environmental consideration involves a combinatorial optimization problem generating a huge space of solutions [43]. The genetic algorithms that belong to the evolutionary algorithm family, inspired from the Darwin principal, provides an efficient solution with low cost ([13,44]). They have shown their success in the problematic around planning either in the transport field [45,46] or in another field such as in [47,48]. In the present flight rescheduling problem, each flight plan solution is presented by a chromosome in which we suggest a new encoding for $\mathrm{FRP}$ using the genetic algorithm. Moreover, the genetic algorithm supplies solutions for $\mathrm{FRP}$ respecting the tolerated ground delay and cruise time. We added a verification stage that allows us to survey the feasibility of generated solutions towards the constraints of the programming model. This provided genetic algorithm represents a second contribution in this work.

3. Air Traffic Management Formulation

In this section, we describe the proposed system in the first subsection, then we present and explain the different variables and parameters in the second subsection.

3.1. Problem Statement

In this paper, the proposed system considers a set of flights scheduled to fly according to an initial plan. This latest is actually attributed by the central flow management unit. As in practice, we consider a flight plan defined by the departure airport, arrival airport, scheduled departure time, scheduled arrival time, and itinerary. The flight plan shall respect the available air capacity. The capacity of the air traffic element (airport and sector) is characterized by the number of aircrafts allowed to use it per time unit. As in the real case, it assumed that the capacity of the air traffic element depends on weather conditions. In this paper, the uncertain capacity is considered as the main cause of the flight plan disruption.

The central flow management unit performs the flight plan before a lengthy period of flight day in accordance with the capacities forecasts. Nevertheless, the unforeseen bad weather conditions stimulate the air traffic congestion and make the initial scheduling of some flights plan infeasible. In this case, the stakeholders take specific decisions in order to minimize the perturbation effects and return the traffic fluidity as soon as possible. In this paper, the adopted decisions to reschedule the flights plan are the ground delay, the initial itinerary changing, speed adjustment, and cancellation. We consider also that the aircraft is equipped with three speed modes in which the first mode is the economic that is adopted in the initial scheduling. Each speed mode correlates with two types of states: The first corresponds to the kerosene consumption state and the second concerns the carbon emission state. Both criterions are presented by one index denoted by $Ind\left(·\right)$.

Therefore, the choice of speed mode other than the economic to recover the ground delay and\or the longer itinerary generates a greater index. We recall that the objective is to minimize the total cost of flights rescheduling through determining the suitable decisions in order to avoid the unforeseen capacity reduction. The following assumptions are adopted for the flight rescheduling generation:

(1)

The flight rescheduling is considered only before takeoff (uncommitted flights) and once the flight has taken off will be controlled by air traffic controllers until arrival at the destination airport; a static flight rescheduling problem applies on a single replanning point which is the departure airport.

(2)

Rescheduling options include ground delay, itinerary changing, speed adjustment, and cancellation decisions. The recourse to flight cancellation is only when the authorized delay time is exceeded, that is known in the air field by 4 h of maximum ground delay. In addition, in the situation where the delay is excessive due to a significant ground delay and/or itinerary changing, the speed adjustment is used as an alternative option to minimize the arrival delay.

(3)

This paper assumes that all aircrafts are with the same types and with the same number of passengers. We note that these two hypotheses are to simplify the model presentation, and are not intended to reduce the general character of the developed decision support system. In addition, the quantity of consumed kerosene really depends on the aircraft type and the weight of the aircraft (the empty mass plus the number of passengers).

3.2. Notation

In this subsection, we present the notations that are used in the paper body. In the following, we present parameters of the model, including state-specifying parameters and decision variables: A finite set of itineraries ${\mathfrak{T}}_f=\left\{I_{1,f},I_{2,f},\dots ,I_{\left|{\mathfrak{T}}_f\right|,f}\right\}$ are reserved for flight $f$ in which each one connects the departure airport to the arrival airport. A flight itinerary $I_{l,f}$ is defined by a succession of sectors: $I_{l,f}=\left(s_{m_1},s_{m_2},\dots ,s_{m_n}\right)$. The traveled distance by $f$ in $s_{m_2}$ following $I_{l,f}$ is denoted by $\overline{I_{l,f}\left[2\right]}$.

The description of the remaining parameters is as follows:

$\mathbb{F}$	: Number of scheduled flights
$c_g$	: Unit cost per time slice of ground delay
$c_k$	: Unit purchase kerosene price
$c_p$	: Unit cost per time slice of arrival delay
${\delta }_f$	: Number of time unit of ground delay carried out by $f$
$\overline{I_{l,f}\left[i\right]}$	: Distance travelled by $f$ in sector $i$
$SP\left(I_{l,f}\left[i\right]\right)$	: Speed used in sector $i$
$d_f$	: Scheduled departure time of $f$
$A_f^P$.	: Scheduled arrival time of $f$
$A_f^R$	: Real arrival time of $f$
${\tau }_{I_{l,f}\left[i\right]}^{OT}$	: Exit time of $f$ from $I_{l,f}\left[i\right]$.
${\tau }_{I_{l,f}\left[i\right]}^{IN}$	: Entry time of $f$ in $I_{l,f}\left[i\right]$
$G_{tol}$	: The tolerated ground delay

To establish the exact arrival time of a flight in a given sector, a decision variable $X_{ft}^{I_{l,f}\left[i\right]}$ is defined as follows:

$$X_{ft}^{I_{l,f}\left[i\right]}=\{\begin{array}{l}1iffentersthe{s}_{i}attfollowing{I}_{l,f}\\ 0else\end{array}$$

Additionally, a binary-state variable $Y_{ft}^{I_{l,f}\left[i\right]}$ is introduced to locate the flight in the air system and consequently compute the involved costs.

$$Y_{ft}^{I_{l,f}\left[i\right]}=\{\begin{array}{l}1iffin{I}_{l,f}\left[i\right]att\in \left[{\tau }_{I_{l,f}\left[i\right]}^{IN},{\tau }_{I_{l,f}\left[i\right]}^{OT}\right]\\ 0else\end{array}$$

The bounds of time interval, describing the entry and exit of a flight from the air sector, are calculated by using the decision variable $X_{ft}^{I_{l,f}\left[i\right]}$ as follows:

$${\tau }_{I_{l,f}\left[i\right]}^{OT}={\displaystyle {\displaystyle \sum }_{j=1}^i}\frac{\overline{I_{l,f}\left[j\right]}}{SP\left(I_{l,f}\left[j\right]\right)}+{\tau }_{I_{l,f}\left[1\right]}^{IN}$$

$${\tau }_{I_{l,f}\left[i\right]}^{IN}={\displaystyle {\displaystyle \sum }_{t=d_f}^{d_f+G_{tol}}}\left(X_{ft}^{I_{l,f}\left[1\right]}\times t\right)$$

4. Mathematical Model

In this section, we present the developed mathematical model that is composed of the objective function and the constraints.

4.1. The Objective Function

The objective function aims to minimize the total cost induced by the rescheduling due to unforeseen bad weather conditions. The objective function includes the ground delay cost, the penalty cost, the cruise cost, the cost of consumption kerosene, the cost of late arrival, and the cost of carbon emissions. In what follows, we present the different equations that compose the objective function.

It assumed that the takeoff duration is negligible. The number of time slice of the ground delay ${\delta }_f$ equals the real departure time $X_{ft}^{I_{l,f}\left[i\right]}$ minus the scheduled departure time $d_f$. Thus, the number of time slice of the ground is given by:

$${\delta }_f={\displaystyle {\displaystyle \sum }_{t=d_f}^{d_f+G_{tol}}}\left(X_{ft}^{I_f\left[1\right]}·t\right)-d_f$$

(1)

Among the objectives is to decide how much each flight is delayed at the airport in case of an unforeseen event such as bad weather conditions, which make the initial planning infeasible. The induced ground delay cost of flight $f$ is characterized by the number of time units of the ground delay carried out by flight ${\delta }_f$ and the unit cost of ground delay $c_g$ which varies from one airport to another. The induced ground delay cost of flight $f$ is formulated by the following equation:

$$C_g^f={\delta }_f·c_g$$

(2)

Once the aircraft has left the ground, after the takeoff phase, the flight cost includes the cost of consumed kerosene. This cost is called the cruise cost that depends on the quantity of consumed kerosene, $Q_k^{I_{l,f}\left[i\right]}$, according to the aircraft type and number of passengers. The cruise cost is defined by Equation (3). This paper assumes that all aircrafts are with the same types and with the same number of passengers. We note that these two hypotheses are to simplify the model presentation, and are not intended to reduce the general character of the developed decision support system. In addition, the quantity of consumed kerosene, $Q_k^{I_{l,f}\left[i\right]}$, also depends on the aircraft type and the weight of the aircraft (the empty mass plus the number of passengers); for example, the Airbus A318 can accommodate 136 passengers with a maximum mass of 68 tons against the A320 that can accommodate 180 passengers with a maximum mass of 78 tons.

$$C_g^f={\displaystyle {\displaystyle \sum }_{i=1}^{\left|{\mathfrak{T}}_f\right|}}\left(Q_k^{I_{l,f}\left[i\right]}·Y_{ft}^{I_{l,f}\left[i\right]}\right)·c_k$$

(3)

Generally, the amount of kerosene consumed throughout a given distance depends on the speed decided by the pilot. In fact, the aircraft is occupied with three types of index (mathematically noted by $Ind\left(·\right)$) in which each index corresponds to a predetermined speed mode. The choice between these three indices allows us to determine the quantity of consumed kerosene during a traveled air sector, $s_i$, measured by distance $\overline{I_{l,f}\left[i\right]}$. The kerosene quantity in sector i equals distance $\overline{I_{l,f}\left[i\right]}$ divided by the speed used in sector $i$ $SP\left\{I_{l,f}\left[i\right]\right\}$ multiplied by the index. The kerosene quantity is represented by:

$$Q_k^{I_{l,f}\left[i\right]}=\frac{\overline{I_{l,f}\left[i\right]}}{SP\left\{I_{l,f}\left[i\right]\right\}}·Ind\left(SP\left(I_{l,f}\left[i\right]\right)\right)$$

(4)

The real arrival time of flight $f$, $A_f^R$, is established by calculating the cumulative traveled time of different sectors plus the real departure time from the initial airport ${\tau }_{I_{l,f}\left[1\right]}^{IN}$. The real arrival time is given by:

$$A_f^R={\tau }_{I_f\left[\left|{\mathfrak{T}}_f\right|\right]}^{OT}={\displaystyle {\displaystyle \sum }_{j=1}^{\left|{\mathfrak{T}}_f\right|}}\frac{\overline{I_{l,f}\left[j\right]}}{SP\left(I_{l,f}\left[j\right]\right)}+{\tau }_{I_{l,f}\left[1\right]}^{IN}$$

(5)

Another cost is usually considered which is induced from the arrival delay. Indeed, to the flight delay before departure, the aircraft can arrive at the destination airport after the scheduled arrival even with the speed adjustment (higher speed mode) to recover the ground delay and\or choose a longer itinerary. This late arrival causes inconvenience for different stakeholders such as airlines, passengers, and air navigation traffic, which is paid in the form of penalty depending on the delay time. The delay cost represents the difference between the real arrival time and the scheduled arrival time multiplied by the unit cost per time slice of the arrival delay. Thus, the delay cost is represented by:

$$C_p^f=\left(A_f^R-A_f^P\right)·c_p$$

(6)

Usually, the burning of kerosene in aircraft engines produces carbon dioxide (CO₂) emissions in which its diffusion contributes to the greenhouse effect and global warming. In this way, the regulations governing the fuel consumption set targets aim to gradually reduce the environmental impact by imposing penalties on the carbon emissions. Since the ecological performance (emission, pollution, etc.) strongly depends on kerosene consumption and in the context of environment control the authorities decided to tax the airlines that paid for each emission unit. This emission quantity as formulated by Equation (7) depends on the distance traveled as well as on the index $Ind\left(·\right)$. In our model, the carbon emissions represent the quantity of carbon emitted from the flight operation and we do not consider other gases. Note that the speed mode is correlated to the index. Therefore, the carbon emissions quantity emitted for a given distance, equals the distance traveled multiplied by the carbon index emissions:

$$Q_{CO2}^{I_{l,f}\left[i\right]}=\overline{I_{l,f}\left[i\right]}·Ind\left(SP\left(I_{l,f}\left[i\right]\right)\right)$$

(7)

After defining the different costs, we present the objective function (Equation (8)) that is the sum of the cost of ground delay, the cost of consumption kerosene while cruising, the cost of late arrival, and the cost of carbon emissions. Detailing the expression of each cost as explained above, we obtain the following expression:

$$\begin{array}{cc}\hfill Min{\displaystyle {\displaystyle \sum }_{f\in ℱ}}[({\displaystyle {\displaystyle \sum }_{t=d_f}^{d_f+G_{tol}}}& \left(X_{ft}^{I_f\left[1\right]}·t\right)-d_f)c_g\hfill \\ & +{\displaystyle {\displaystyle \sum }_{i=1}^{\left|{\mathfrak{T}}_f\right|}}\left(\left(\frac{\overline{I_{l,f}\left[i\right]}}{SP\left\{I_{l,f}\left[i\right]\right\}}·In{d}_K\left(SP\left(I_{l,f}\left[i\right]\right)\right)\right)·Y_{ft}^{I_{l,f}\left[i\right]}\right)c_k\hfill \\ & +\left(\left({\displaystyle {\displaystyle \sum }_{j=1}^{\left|{\mathfrak{T}}_f\right|}}\frac{\overline{I_{l,f}\left[j\right]}}{SP\left(I_{l,f}\left[j\right]\right)}+{\tau }_{I_{l,f}\left[1\right]}^{IN}\right)-A_f^P\right)c_p]\hfill \end{array}$$

(8)

4.2. The Constraints

As explained above, the air traffic system is subject to bad weather conditions reducing the capacity of certain air elements (sectors and airports) during known time windows. Taking account of the new air capacity, Equation (8) ensures that the number of flights using an air sector $I_{l,f}\left[i\right]$ should not exceed its available capacity at time $t$, $CAP\left(I_f\left[i\right],t\right)$. In this paper, the air capacity elements under consideration are the air sectors where the airport capacity is considered infinite, which corresponds perfectly to the problem of air traffic management in Europe.

$${\displaystyle {\displaystyle \sum }_f}{Y}_{ft}^{I_{l,f}\left[i\right]}\le CAP\left(I_f\left[i\right],t\right)$$

(9)

An itinerary of flight can be observed as a set of successive segments sequence; each segment is defined as the sub-itinerary (sector) $I_{l,f}\left[i\right]$. The connection between segments sequence is respected by Equation (10) in which the passage of flight $f$ to sector $I_{l,f}\left[i+1\right]$ only occurs when the same flight has traveled to the previous sector $I_{l,f}\left[i+1\right]$, obviously respecting the necessary flight time.

$$Y_{f\left(t+\frac{\overline{I_{l,f}\left[i\right]}}{SP\left(I_{l,f}\left[i\right]\right)}\right)}^{I_{l,f}\left[i+1\right]}-Y_{ft}^{I_{l,f}\left[i\right]}\le 0$$

(10)

Constraints (11) and (12) ensure the 0–1 integrality to variable decision and the state variable.

$$X_{ft}^{I_{l,f}\left[i\right]}\in \left\{0,1\right\}$$

(11)

$$Y_{ft}^{I_{l,f}\left[i\right]}\in \left\{0,1\right\}$$

(12)

5. Resolution Approach Based on the Genetic Algorithm

To solve the air traffic management problem under emission and congestion constraints, we suggest the genetic algorithm as an optimization method to minimize the objective function. In the subsections below, the details of the resolution stages by the genetic algorithm are described in greater depth.

5.1. Encoding

The rescheduling options to recover the perturbation arisen over the planned flights are the ground delay ${\delta }_f$, changing the initial itinerary, and the speed adjustment. Once the itinerary is chosen, before the takeoff, the aircraft speed can be decided differently from one air sector to another. As explained above, the aircraft speed $SP\left(I_{l,f}\left[i\right]\right)$ is translated by a flight time expressed by Equation (13):

$${\mathcal{T}}_{I_{l,f}\left[i\right]}={\tau }_{I_{l,f}\left[i\right]}^{OT}-{\tau }_{I_{l,f}\left[i\right]}^{IN}=\frac{\overline{I_{l,f}\left[i\right]}}{SP\left\{I_{l,f}\left[i\right]\right\}}$$

(13)

Indeed, the suggested encoding of the genetic algorithm to present a solution of the rescheduling problem is the chromosome with integer values. The chromosome is arranged in this way: The first genes are reserved for the ground delay and the remainder are divided in the succession of the sector flight time for each aircraft. Thus, the solution size by chromosome encoding in $\left|\mathbb{F}\right|+{\displaystyle {\displaystyle \sum }_f}\left|I_{l,f}\right|$, $\left|I_{l,f}\right|$ is the number of air sectors in itinerary $l$.

Figure 1 illustrated an example of the encoding schema.

5.2. Fitness

In the evaluation stage, we use the objective function explained above (Section 3) as a fitness function that assesses the quality of the returned solution.

5.3. Selection by Elitism

In the selection stage, we adopted the elitism method among several selection tools of new candidates; the reader can refer to Eshelman (2014) [49] for a survey of the selection types.

The procedure of elitism selection ensures that the best candidates (chromosomes) from the previous generation will be included in the next generation. The percentage of the best candidates selected for the next generation is the parameter of elitism selection that is decided by the user. In this paper, the candidates are selected among $30\%$ of the generation.

5.4. Crossover

The idea is to use a crossover operator that ensures the feasibility of the new flights plan according to the constraints Equations (9)–(12), which is to conform to the uniform crossover. The uniform crossover uses a binary chromosome (named mask) randomly generated for each two parents. The bit value of mask ($0$ or $1$) determines which genes of the parents’ swap.

This uniform crossover operation generates two children of chromosomes that model two new rescheduled flights plan. For the bit value equal to $1$ that matches the ground delay, the time delay is inversed and, if not, the flight time spent in the sector is inversed, as illustrated in Figure 2.

5.5. Mutation

For the selected candidates, the mutation is implemented by selecting a random gene on the offspring’s chromosome length and then changing its value as follows: In the case where the gene matches the ground delay a random value of delay ${\delta }_f$ is chosen between $\left[0,G_{tol}\right]$. In the case where the gene matches the flight sector time, the cruise time in the chosen sector among $\mathsf{{\rm T}}=\left\{{\mathcal{T}}_{I_{l,f}\left[i\right]}{}^1,{\mathcal{T}}_{I_{l,f}\left[i\right]}{}^2,{\mathcal{T}}_{I_{l,f}\left[i\right]}{}^3\right\}$, where each one of $\mathsf{{\rm T}}$ corresponds to a given speed from the three modes.

For instance, two children are randomly generated according to the gene type as shown in Figure 3. The first child is the case when the ground delay of flight ‘2′ is randomly changed from two time slices to three time slices that does not exceed $G_{tol}=4$. The second child is generated in the case of the change of the speed mode. The gene of the parent corresponding to the first speed mode (${\mathcal{T}}_{I_{l_2,f_2}\left[1\right]}{}^1$) that is equivalent to six flight time slices. The mutation operator chooses randomly the second speed mode (${\mathcal{T}}_{I_{l_2,f_2}\left[1\right]}{}^2$) converted to the flight time that corresponds to eight time slices. Obviously, the feasibility of the generated solution is guaranteed whatever the changed gene.

5.6. Insertion

Among the several insertion methods proposed in the literature, the best individuals and parents’ replacement are adopted in this paper.

5.6.1. Best Individuals

The best individual’s method consists of keeping only the best children through all generations. Therefore, the least efficient children are automatically discarded out of the population.

5.6.2. Parents’ Replacement

The parents’ replacement consists of comparing the new children in relation to their parents. The new individuals are inserted in the population only in the case where the children are better than their parents. This operation is executed after the crossover or mutations operations and the solution evaluations stage.

6. Numerical Applications

This section presents the effectiveness of the new proposed encoding of the genetic algorithm for the possible resolution of a flight rescheduling problem with an emission consideration. For this purpose, we consider the following parameters:

6.1. The FRP Parameters

Unit costs are: $c_g=10USD/t.u$, $c_K=10USD,$ and $c_p=100USD/t.u$; where $USD/t.u$ is American dollars one time unit with $1t.u=20min$. $G_{tol}=10t.u$, we established several FRP instances in which the number of the flight is selected from $\left|\mathbb{F}\right|,$ where $\left|\mathbb{F}\right|=\left\{100,200,300\right\}$ and the number of itineraries for each flight is $\left|{\mathfrak{T}}_f\right|=15$. In addition, the air traffic system considered in this computational experiment is composed of $\raisebox{1ex}{$\left|\mathbb{F}\right|$}\!\left/ \!\raisebox{-1ex}{$50$}\right.$ airports. In other words, for $\left|\mathbb{F}\right|=200$ the air system consists of four airports with 50 flights per airports. Three types of the kerosene index consumed adopted are $Ind\left(SP\left(I_{l,f}\left[i\right]\right)\right)=\left\{3,4,5\right\}$.

We recall that the developed sustainable decision support system for the FRP can be exploited by the air stakeholders for a tactical decision; a decision applied only the day of the flight. For this, the rescheduling horizon adopted is $\left[5:00am;12:00am\right]$ which generally corresponds to the opening hours of an airport.

6.2. Computational Results of $FRP$

The conducted tests of the proposed genetic algorithm that are with the population contains 200 individuals. The generation number ($\mathrm{G}.\mathrm{N}$) is performed between $100$ and $2000$; $\mathrm{G}.\mathrm{N}=\left\{100,200,500,2000\right\}$. We choose two genetic algorithms: Elitism and best individuals denoted by GA₁, elitism and parents’ replacement called GA₂. The C is the computer language used to implement the proposed algorithm under Windows 7 with Core i7 2.60 GHz 8 Go of RAM.

Table 1. The total cost and the related CPU times (second) of GA₁ and GA₂ with different generations number.

$\mathit{N}°$	$\mathbf{G}.\mathbf{N}$	$\left|\mathbb{F}\right|$	$\mathit{C}1$	$\mathit{T}1$	$\mathit{C}2$	$\mathit{T}2$
$1$	$100$	$100$	$469,770$	$2.63$	$458,972$	$2.35$
$2$	$200$	$100$	$460,840$	$4.82$	$453,188$	$4.19$
$3$	$500$	$100$	$433,520$	$8.41$	$414,862$	$7.94$
$4$	$1000$	$100$	$397,870$	$16.34$	$357,148$	$15.69$
$5$	$2000$	$100$	$323,540$	$33.07$	$267,680$	$30.06$
$6$	$100$	$200$	$971,770$	$2.82$	$962,570$	$2.54$
$7$	$200$	$200$	$963,430$	$4.92$	$948,350$	$4.71$
$8$	$500$	$200$	$940,630$	$11.74$	$898,160$	$10.84$
$9$	$1000$	$200$	$878,460$	$22.88$	$827,790$	$21.24$
$10$	$2000$	$200$	$804,070$	$45.09$	$714,360$	$41.93$
$11$	$100$	$300$	$1,475,450$	$3.49$	$1,467,080$	$3.26$
$12$	$200$	$300$	$1,451,140$	$6.38$	$1,443,580$	$5.80$
$13$	$500$	$300$	$1,428,990$	$15.88$	$1,418,890$	$15.05$
$14$	$1000$	$300$	$1,382,520$	$29.34$	$1,330,760$	$27.14$
$15$	$2000$	$300$	$1,311,640$	$58.31$	$1,231,615$	$61.91$

presents the gathered results of the GA₁ and GA₂; $C1$ and $C2$ ($T1$ and $T2$) are respectively the cost (CPU times) of the sub-optimal solution of GA₁ and GA₂.

Figure 4 and Figure 5 illustrate respectively the comparison between the two genetic algorithms of the CPU times and solution cost with the $15$ instances presented in Table 1. We can deduce through Figure 3 that the AG₁ (elitism and best individuals) is more expensive in terms of time whatever the number of generation and the number of rescheduling flights (exception instance 15). Moreover, we can remark in Figure 5 that the AG₁ is the wrong algorithm in terms of the cost of the generated solution. Indeed, the AG₂ is the best algorithm due to insertion with the parents’ replacement, which deduces a quick sub-optimal solution with the lowest cost.

Before presenting the numerical results, we would like to investigate the robustness of our proposed model and the optimization algorithm AG₂ by presenting two tests. We vary some given parameters, for example, the unit cost of the ground delay c_g $\left\{10,50,100\right\}$ and the unit cost per time slice of the arrival delay c_p $\left\{100,500,1000\right\}$. For each parameter, we vary the number of flights from a small to high number such as, i.e., $\left\{100,500,1000,5000,10000\right\}$. The generation number is fixed to 1000 generations. We have provided the results in

Table 2. Robustness of the proposed model and algorithm AG₂ (test with c_g).

cg	$\mathit{N}°$	$\left|\mathbb{F}\right|$	$\mathit{C}1$
10	$1$	200	827,790
	$2$	500	2,358,433
	$3$	1000	4,855,570
	$4$	5000	24,987,800
	$5$	10,000	50,395,950
50	$6$	200	1,101,796
	$7$	500	3,059,332
	$8$	1000	6,385,954
	$9$	5000	32,843,830
	$10$	10,000	66,040,200
100	$11$	200	1,443,475
	$12$	500	3,972,232
	$13$	1000	8,269,567
	$14$	5000	42,574,320
	$15$	10,000	86,242,910

and

Table 3. Robustness of the proposed model and algorithm AG₂ (test with c_p).

cp	$\mathit{N}°$	$\left|\mathbb{F}\right|$	$\mathit{C}1$
100	$1$	200	827,790
	$2$	500	2,358,433
	$3$	1000	4,855,570
	$4$	5000	24,987,800
	$5$	10,000	50,395,950
500	$6$	200	3,452,358
	$7$	500	9,555,243
	$8$	1000	20,015,586
	$9$	5000	103,918,724
	$10$	10,000	208,570,420
1000	$11$	200	6,664,174
	$12$	500	18,530,980
	$13$	1000	38,783,570
	$14$	5000	202,577,090
	$15$	10,000	406,016,340

.

The results show that the model and the developed optimization method are robust, as the proposed algorithm converges to the optimal solution for whatever values of the unit cost of ground delay and the number of flights or unit cost per time slice of arrival delay. Furthermore, the results seem to be coherent and logic, as for example, when the unit cost of ground delay c_g increases the total cost increases. Or when the number of flights increases the total cost increases too.

6.3. Impact of the Carbon Tax on the Flights Carbon Emissions

In this subsection, we study the impact of the carbon tax on the total carbon emissions and the total flight costs. In this study, our target is to investigate the efficiency of carbon tax regulation for curbing the emission and its impact on the rescheduling decisions. Thus, we vary increasingly the carbon tax rate, and by using the proposed genetic algorithm, we determine the corresponding values of optimal total cost and total carbon emissions (see Figure 6). Indeed, the carbon tax is taken into account in the economic model (Equation (8)) through the consideration of the purchase kerosene price. As mentioned previously, the carbon tax is included in the purchase kerosene price by exercising a percentage on the kerosene price. In order to show the relationship between the purchase kerosene price with carbon emissions, it shall present the purchase kerosene price in the function of carbon tax. Thus, before presenting the carbon emissions in the function of carbon tax (Figure 7), we present in Figure 6 the values of the purchase kerosene price that corresponds to the considered carbon tax rate. In other words, Figure 6 allows making the connection between the carbon emissions, total cost, and purchase kerosene price, and then investigating the results given in Figure 7. The purchase kerosene price in the function of carbon tax is given by: k_c (% carbon tax) = % carbon tax * k_c(0), k_c(0) is the purchase kerosene price without tax. In Figure 6 k_c(0) = 10 USD/t.u.

For the rest of the data, we use the same as those that are used in the previous subsection. As can be observed in Figure 7, when the carbon tax increases, the carbon emitted by flights decreases and the total cost increases. This is explained by fact that when the carbon tax increases, the purchase kerosene price increases (see Figure 6), and then it shall reduce the kerosene consumption in order to minimize the total cost. Consequently, the carbon quantity emitted by flights decreases. Indeed, the rescheduling decision adopts the economic speed mode to reduce the kerosene consumption, but consequently arrival delay costs are scarified. In other words, in the case when the carbon tax is high, the rescheduling decision promotes the economic speed mode and ground delay on arrival delays, which explains also the increasing of the total cost of flights with the carbon tax. In this study, we show that the carbon tax regulation is efficient for curbing the carbon emissions emitted by the flights and also the proposed decision model is robust for rescheduling the perturbed flights plan according to the carbon regulations. This study can serve as a decision support to stakeholders of air traffic management under carbon tax regulation.

6.4. Impact of the Cost of Arrival Delay on the Carbon Emissions

In this subsection, we study the impact of the arrival delay cost on the total carbon emissions and the total flight costs. In practice, the arrival delay cost depends on the passengers’ requirement and company reputation that usually can be important and have an impact on the company benefic even environment. In this study, our target is to investigate the effect of the unit arrival delay cost on the rescheduling decision. Thus, we fix the carbon tax rate at 10% (i.e., $c_k=11USD$) and we vary increasingly the unit arrival delay cost, and by using the proposed genetic algorithm, we determine the corresponding values of the optimal total cost and total carbon emissions (see Figure 8). For the rest of the data, we use the same as those that are used in the previous subsection.

As can be observed in Figure 8, when the unit arrival delay cost increases, the carbon emitted by flights and the total cost increases. That is explained by the fact that when the arrival delay cost is high, the rescheduling decision chooses the high-speed mode (not economic speed) in order to limit the arrival delays. This decision negatively affects the environment by increasing the carbon emissions. In practice, companies invoke the environment aspect to decrease the delay cost by raising awareness of the passenger to accept a delay inconvenience for protecting the environment.

7. Conclusions

As the aircraft fleet increases with an exponential rate and the air sector contributes drastically to the global CO₂ emissions, air traffic delays and air pollution are more apparently observed. This study aims at developing a sustainable decision support system for assisting aerial stakeholders. Particularly, we have developed a generic mathematical model that will support rescheduling decisions for uncommitted flights by taking into account the quantity of CO₂ emissions. The air traffic system is characterized by the capacity floated over time and reduced before takeoff of scheduled flights so that the initial planning becomes unfeasible. The options adopted in the flight rescheduling are ground delay, itinerary changing, and cancellation decisions. Furthermore, the proposed generic model deployed the speed adjustment to catch up with the delay. This latter is decided among three speed modes in which the first mode is economical by considering the carbon emissions. This work presents a strong contribution by providing an optimal rescheduling flight plan that minimizes on hand the total flights delays and the global carbon quantity emitted by flights taking into account all rescheduling strategies.

As the resolution method, a genetic algorithm is introduced with new encoding in which a possible economical solution for $\mathrm{FRP}$ is generated. In addition, the aim of this study was to deal with the influence of the economic decision as well as the impact of the speed adjustment on the environment by establishing the correlation between the speed modes and the quantity of CO₂ emissions. The impacts of carbon tax and cost of arrival delay on the flights carbon emissions are studied. The established studies can serve as decisions support to stakeholders of air traffic management under environmental regulation. Furthermore, as usually, stakeholders are obliged to make a quick decision with more efficiency; the proposed genetic algorithm offers another benefit that is to find easily and quickly the optimal flight rescheduling.

A case study was presented to show, firstly, the effectiveness of the proposed genetic algorithm that displayed a sound agreement between the solutions quality and the computation times. Then, we used the case to study the impact of the carbon tax and the cost of arrival delay on the flights carbon emissions. The results revealed that when the carbon tax increases the carbon emitted by flights decreases and the total cost increases, and when the unit arrival delay cost increases the carbon emitted by flights and the total cost increases. This cases study can serve as a dashboard for a flight company, in order to find an optimal decision according to the carbon tax and the different costs related to the flight. Furthermore, as the proposed genetic algorithm allows finding quickly an efficient solution, it can be very helpful in taking rescheduling decisions in a short time with lower cost. This allows staying competitive in the flight domain.

The presented model can be extended to cover the rescheduling problem for the continuous flights (with stopover), considering the successive delay and the constraint of flights having common passengers; passengers going up and down at stopover points. This research is not exempt from limitations: First, this work considers that only the uncommitted flights with a rescheduling decision is static. Second, the emissions regulation is based only on the carbon tax. In our future research, we will address these limitations by considering the dynamic decision, e.g., real-time decision, when the aircraft is in cruising, by considering also the airborne delay option. In addition, using other optimization methods is necessary to further analyze the solutions quality obtained by genetic algorithms. Moreover, we will consider another emissions regulation, such as the mandatory carbon regulation.