InGaN Bandgap, Affinity, Effective density of states, Permittivity

Keywords: AM 1.5G Solar Spectrum.  Absorption, SRH, Auger and direct recombination, Band discontinuity, Tunneling current, Polarization/Piezoelectric parameters

The development of new thin films solar cells is highly accelerated by using rigorous optimization approach. A large set of parameters is involved in

  the solar cell operation: active layer thickness, composition, bandgap, doping, contacts, etc. The study of the solar cell performances with respect to these linked parameters is necessary to better understand the underlying physics and to optimize the final device. We propose in this poster presentation (*) a new open-source solar cell optimizer: SLALOM for SoLAr ceLl multivariate OptiMizer. SLALOM implements, for the first time for solar cells, a rigorous multivariate approach while the standard optimization work used to use the one-by-one parameter procedure. SLALOM is implemented to be easily extended to any simulator, the core code itself does not depend on any particular engine. It can be adapted for any solar cell structure, runs locally or remotely on a calculation server, using the SSH protocol and includes a graphical user interface to real-time monitor the optimization. Two study cases, InGaN and CZTS solar cells, are presented to show the SLALOM ability to become a useful tool for the development of novel solar cells. (*) Article independently submitted to EPJ Photovoltaics InGaN and CZTS solar cells optimized using SLALOM. The used backend simulator engine is Silvaco® Atlas®.

  written in Python, It uses the SciPy and NumPy numerical packages, Tkinter for the user interface and Matplotlib for 2D curve plotting. Figures shows the SLALOM general architecture. SLALOM modules:  slalom.py: the SLALOM startup module: sets the parameters, the optimization method and controls the whole process  slalomCore.py: the SLALOM core class: implements the optimization using mathematical algorithms and controls the device simulation engine  slalomDevice.py is a class defining a set of devices (e.g. InGaN PN, CZTS NP...) for easier and more robust optimization work  slalomDeviceGui.py is a class providing an interface to create a new device type SLALOM is distributed under MIT license for free use, modification and redistribution. Its source code is freely available for download and use from:  https://github.com/sidihamady/SLALOM  http://www.hamady.org/photovoltaics/slalom_source.zip One-by-one parametric analysis steps (cf. figure):  defining a set of technological and physical parameters: composition, doping concentrations, layers thicknesses...  defining the set of samples to simulate  simulating these samples to extract the photovoltaic efficiency The sample for which the efficiency is optimal in then identified and the varying parameter set to the optimal value. The procedure then iterates for the next parameter, keeping all other parameters constant… Advantage:  simplicity Disadvantages:  mathematical uncertainty: at the end of the procedure, the highest obtained efficiency is not guaranteed to be the optimal one since the procedure ignores the interdependence between the solar cell parameters  huge number of evaluations of the efficiency SLALOM (SoLAr ceLl multivariate OptiMizer):  uses state-of-the-art mathematical optimization algorithms to find the parameter set that yields the optimal solar cell efficiency  takes the interdependence between the parameters into account  minimizes the computing time, if compared to the classical method Procedure steps:  defining a set of parameters pertaining to the solar cell operation (e.g. composition, doping concentrations, layers thicknesses...)  using a semiconductor simulation engine that allows the numerical evaluation of the solar cell efficiency from its parameters (cf. figure)  using a mathematical algorithm designed to find the parameter vector that maximizes the efficiency using a numerical iterative procedure Used mathematical optimization algorithms:  Sequential Least Squares Programming (SLSQP) method: starting from an initial guess, it uses Newton's method to find the optimum  Broyden-Fletcher-Goldfarb-Shanno (BFGS) iterative algorithm: it uses a quasi-Newton method to find the optimum using gradient evaluations and approaching the second derivatives [6] S Ould Hamady, A Adaine, and N Fressengeas. Numerical simulation of InGaN Schottky solar cell. Materials Science in Semiconductor Processing, 41:219-225, 2016. [7] A Adaine, S Ould Saad Hamady, and N Fressengeas. Simulation study of a new InGaN p-layer free Schottky based solar cell. Superlattices and Microstructures, 96:121-133, 2016. [8] Abdoulwahab Adaine, Sidi Ould Saad Hamady, and Nicolas Fressengeas. Effects of structural defects and polarization charges in InGaN-based double-junction solar cell. Superlattices and Microstructures, 107:267-277, 2017. Efficiency of the InGaN PN solar cell determined by SLALOM using the L-BFGS-B and SLSQP methods: both methods converge to the same set of optimal parameters in about two hours for L-BFGS-B and one hour for SLSQP on a Red Hat Linux server with two 8-core Xeon processors and 32 GB of RAM. The InGaN simulation files for Silvaco© Atlas® are included in the SLALOM distribution. The optimal set of parameters gives an optimal efficiency of about 18 %, a shortcircuit current of 26.8 mA/cm 2 , an open-circuit voltage of 0.85 V and a fill factor of 78 %, obtained for the following set of values: a P-layer thickness of 0.01 µm, an N-layer thickness of 1 µm, a P-layer doping of 10 19 cm -3 , an N-layer doping of 4×10 16 cm -3 and an Indium composition of 56 %. Current-voltage characteristic of the InGaN PN solar cell at the optimum: Copper Zinc Tin Selenide Cu 2 ZnSnSe 4 (CZTS): abundance of elements and high photovoltaic performances. The CZTS simulation files for Silvaco© Atlas® are included in the SLALOM distribution. The set of parameters choosen to be optimized are the CZTS absorber doping and thickness. The other data used in the simulation, such as the CZTS bandgap, mobilities and absorption coefficient and the CdS layer parameters, are fixed to their experimentally known values. Optimal efficiency found by SLALOM: 20.5 % for a CZTS thickness of 1.3 µm and a doping concentration of 1.4×10 15 cm -3 . Efficiency is higher than the InGaN solar cell efficiency, showing the potential of this alternative material for photovoltaics. The optimization duration was about three hours, more than ten times faster than rough parametric analysis. Current-voltage characteristic for the optimal efficiency: 35 th European Photovoltaic Solar Energy Conference and Exhibition 24 -28 September 2018 Brussels

Parameters [1] InN GaN CZTS Bandgap (eV) Affinity (eV) Carrier lifetime (ns) Permittivity N C (cm -3 ) N V (cm -3 ) 0.7 5.6 1 15.3 9.1×10 17 5.3×10 19 3.42 4.1 1 8.9 2.3×10 18 4.6×10 17 1.5 4.5 1000 10 2.2×10 18 1.8×10 19 Absorption Mobility Refractive Index Extracted from experimental data [3] Caughey-Thomas Model [4] Adachi Model [5]


Gabriel Hondet

Luis Delgado

Gerald Gurtner

Airline disruption management with aircraft swapping and reinforcement learning

Managing fleet disruption is essential for an airline to control delay costs. Delays emerging from these disruptions can be manipulated through fleet operations like aircraft swapping. This paper applies machine learning techniques to the disruption problem. While airlines might do this process manually or using basic predefined rules, the complexity of the problem makes it well suited for a computed approach. The paper describes the principles of reinforced learning and the model used for testing them. Two representations of decision states are considered and applied to a set of historical schedules for an airline. The performance obtained by swapping aircraft using the reinforced learning is finally compared to the idle option, i.e., do not swap any flight. The comparison evinces that while the algorithm is far from being optimal, the agent takes relevant decisions as it performs better than the idle behaviour in heavily disrupted simulations.

Introduction

The design of a schedule is strategic as it happens months in advance of its implementation. Since schedules try to maximise profit, they are subject to an efficiency-resilience trade off. A schedule is here said to be resilient if it is not too sensitive to unexpected events, i.e., the probability that the carried out operations deviate in time from what was scheduled is low. The lower the buffer between operations, the higher the cost efficiency but the lower the resilience. In contrast, a schedule allowing more time between operations is resilient but not efficient. To make profit, airlines will therefore try to minimise delays between operations, and thus expose themselves to disruption problems [START_REF] Cook | European airline delay cost reference values[END_REF][START_REF] Milind | Can time buffers lead to delays? the role of operational flexibility[END_REF].

Costs of disruption problems often rise due to the reactionary delays triggered. To lower these costs, airlines can modify the schedule in real time. However, the number of re-configurations makes the problem highly combinatorial and thus better suited for computed solutions than human found ones. Airlines could modify the trajectory of flights, e.g., selecting a different route or modifying their operating cost index [START_REF] Cook | Dynamic cost indexing -managing airline delay costs[END_REF]; actively wait for passengers so that they don't miss their connections [START_REF] Delgado | Hub operations delay recovery based on cost optimisation -dynamic cost indexing and waiting for passengers[END_REF]; swap aircraft [START_REF] Hans-Wieger | Aircraft schedule recovery problem -a dynamic modeling framework for daily operations[END_REF]; cancel flights and in some cases ferry aircraft [START_REF] Cao | The value of runway time slots for airlines[END_REF]. Commercial tools can be used to create and adjust the required flight plans such as Lufthansa Lido or airline recovery management tools by Sabre.

In this paper, the reconfiguration problem that arises from disruptions in the schedule is solved via reinforcement learning. Once a schedule has been built, it is given to a simulator and an agent. The agent will try to lower a cost function by swapping aircraft to cope with disruptions created by the simulator.

The goal of this paper is to present how reinforcement learning techniques could be used in the disruption management problem. The agent will be trained by a basic reinforcement learning algorithm, the Q learning algorithm.

The article is organised as follows. Section 2 presents a literature review on models of disrupted management. It also presents an overview of the reinforcement learning paradigm. Section 3 describes the model used in this paper including a description of the learning mechanism. Section 4 explains in detail the experimental setup used to test the model. Section 5 shows the results obtained with the model on the experimental setup. Finally, Section 6 draws some conclusions and looks at future work.

2 Literature review 2.1 Disruption management [START_REF] Hans-Wieger | Aircraft schedule recovery problem -a dynamic modeling framework for daily operations[END_REF] and [START_REF] Kohl | Airline disruption management-perspectives, experiences and outlook[END_REF] provide a survey of different actions that might be considered by airlines to manage disruptions. They include among others: swap aircraft, cancel flight, delay flights, use stand-by aircraft. Studies to minimise the impact of disruptions often only handle a subset of all possible actions. Most articles use aircraft swapping, flight cancelling, flight re-timing and ferrying. Some works do not consider ferrying, as [START_REF] Hu | Optimization of multi-fleet aircraft routing considering passenger transiting under airline disruption[END_REF], stating that ferrying is very seldom used. Some models would also allow to use stand by aircraft such as in [START_REF] Løve | Using heuristics to solve the dedicated aircraft recovery problem[END_REF].

It is well understood that cost of delay is not linear in function of delay [START_REF] Cook | European airline delay cost reference values[END_REF][START_REF]Coda digest 2017, all-causes delay and cancellations to air transport in europe[END_REF]. The immediate consequence is that cost can be lowered by dividing delay among more flights rather than having it concentrated, i.e., in average it is less costly two flights delayed 20 minutes than one flight delayed 40 minutes.

To analyse the different techniques that try to minimise disruption, an air traffic model is required. This is relevant as knock-on effects, i.e., reactionary delay, needs to be considered. Several graph representations have been proposed. For a exhaustive review see [START_REF] Clausen | Disruption management in the airline industry -concepts, models and methods[END_REF]:

• Connection network, in which each node is a flight leg and two nodes 𝑢, 𝑣 are connected if leg 𝑣 can be flown directly after leg 𝑢 with the same aircraft.

• Time line network, where nodes are events, i.e., arrivals or departures specified by a time and an airport. An edge represents an activity performed by the aircraft.

• Time band network, where each node is either a set of activities performed by an aircraft within a time interval (or time band) or the end of a recovery period, at a certain time and in a specific airport. In this case the flights are modelled as edges.

Passengers can be more extensively considered, as in [START_REF] Delgado | Hub operations delay recovery based on cost optimisation -dynamic cost indexing and waiting for passengers[END_REF][START_REF] Hu | Optimization of multi-fleet aircraft routing considering passenger transiting under airline disruption[END_REF]. Passengers of cancelled flights are often reassigned to a new flight, where possible, or returned to their destination according to the rules of Regulation 261.

In most of the works presented in the review, solutions are found via graph algorithms, such as maximising the flow in [START_REF] Jarrah | A decision support framework for airline flight cancellations and delays[END_REF] or integer programming as in [START_REF] Andersson | The flight perturbation problem[END_REF]. It has nevertheless also been stated as a repartitioning problem in [START_REF] Rosenberger | Rerouting aircraft for airline recovery[END_REF]. [START_REF] Løve | Using heuristics to solve the dedicated aircraft recovery problem[END_REF], uses a heuristic on a graph. In this model, a node is either an aircraft or a departure. A departure is connected to an aircraft in an other airport which may be itself connected to a departure. The network is then used here with a local search meta heuristic, the steepest ascent local search. Another heuristic, the "grasp" heuristic, is used in [START_REF] Michael | Models and Methods for Managing Airline Irregular Operations[END_REF].

In [START_REF] Hu | Optimization of multi-fleet aircraft routing considering passenger transiting under airline disruption[END_REF], the problem is then modelled with a time band network and solved with Cplex using the financial cost as objective function. In addition to the time band network, a "passenger transition relationship" is introduced. This relationship enables the passengers to be transferred on other flights when a flight is cancelled.

When optimising the tactical network operations, several objective functions might be considered. The review [START_REF] Clausen | Disruption management in the airline industry -concepts, models and methods[END_REF] mentions counting the total delay, counting the number of operations carried out (e.g., swaps, reassignments, ferryings) and evaluating the real cost. The latter is the most used, however costs are complicated to model and thus several levels of refinements can be seen. For example, two sub-costs are considered in [START_REF] Løve | Using heuristics to solve the dedicated aircraft recovery problem[END_REF]. One is associated with delays and the other with cancellations. Costs associated with passengers might also be included [START_REF] Cook | Measuring the cost of resilience[END_REF][START_REF] Hu | Integrated recovery of aircraft and passengers after airline operation disruption based on a grasp algorithm[END_REF][START_REF] Hu | Optimization of multi-fleet aircraft routing considering passenger transiting under airline disruption[END_REF]. Further analysis of costs can be found in [START_REF] Cook | Dynamic cost indexing -managing airline delay costs[END_REF], [START_REF] Cook | The hidden cost of airline unpunctuality[END_REF] and [START_REF] Cook | Evaluating the true cost to airlines of one minute of airborne or ground delay[END_REF].

The test setups presented in [START_REF] Clausen | Disruption management in the airline industry -concepts, models and methods[END_REF] span from 3 aircraft and 8 flights to 332 aircraft and 2921 flights, solved in 24 minutes using Cplex. In [START_REF] Løve | Using heuristics to solve the dedicated aircraft recovery problem[END_REF], the method using heuristics has been tested on an instance of 80 aircraft, 44 airports and 340 flights. The time needed to solve such an instance is below 10 seconds.

Reinforcement learning

Reinforcement learning is a method of machine learning based on the interaction between an agent and its environment. It has been extensively used in games where the agent embodies the player and the environment is the world the player evolves in. It has been proven successful in small games such as Tetris, outperforming the human player with the most basic algorithm known as Q learning using lookup tables [23]. Many more sophisticated learning methods have been developed since, such as Deep Q Networks (DQN), developed by Google using convolutional deep neural networks [START_REF] Mnih | Playing atari with deep reinforcement learning[END_REF].

The disruption problem in a fleet can be easily compared to a game making reinforcement learning suitable to solve it. The player would be the airline Environment Agent Action New state Reward Figure 1: Reinforcement learning principle operator who can swap aircraft and the environment is the real world and more specifically the fleet being disrupted. Simple problems may be solved using simple Q learning algorithms using matrices. Real world problems however generally involve a large amount of states or of actions, making Q matrices unusable. To overcome this limitation, multi layer perceptrons can replace the Q matrix as described in [START_REF] Rummery | On-line q-learning using connectionist systems[END_REF]. Multi layer perceptrons are able to handle continuous inputs. If the problem involves many actions, restricted Boltzmann machines can be used as presented in [START_REF] Sallans | Reinforcement learning with factored states and actions[END_REF].

As the problem involves a fleet of aircraft, it might be seen as a multi agent behaviour. While research has been lead on multi agent reinforcement learning, it is stated in [START_REF] Buşoniu | Multi-agent reinforcement learning: An overview[END_REF] that it is even more subject to the curse of dimensionality than single agent reinforcement learning and thus less prone to manage an important amount of actions or states.

Model

Reinforcement learning model

The idea is to make an agent interact with an environment in order to learn the best possible behaviour. This behaviour is modelled by a policy which maps states of the environment to actions the agent should perform. To learn how to behave, each action the agent carries out is rewarded, and each action modifies the environment. The agent will thus adapt its behaviour in function of the rewards it receives (see Figure 1). Every time the agent performs an action, the environment is modified and shifts into a new state. The following notations will be used:

• 𝒮 the set of states,

• 𝒜 the set of actions,

• (𝑠, 𝑠 ′ ) ∈ 𝒮 2 states of the environment,

• 𝑎 ∈ 𝒜 an action,

• 𝛾 ∈ [0, 1) the vision of the agent or the discount factor,

• 𝑇 𝑓 ∈ ℕ the end of the lifetime of the agent, being, in our case, a day of operation.

Mathematically, the best behaviour is the behaviour maximising a criterion. This criterion is usually the expectation of the cumulative sum of rewards, i.e., the total reward the agent can expect during its lifetime, with 𝑟 𝑡 the reward at time step 𝑡, 𝛾 ∈ [0, 1) the discount factor, 𝔼 (

𝑇 𝑓 ∑ 𝑡=0 𝛾 𝑡 𝑟 𝑡 ) (1)
In our case, the reward is the cost savings obtained by performing a given action Valuation functions are used to discriminate policies. Given a policy 𝜋 ∶ 𝒮 → 𝒜, the associate valuation function will be 𝑉 𝜋 ∶ 𝒮 → ℝ. Finding the best policy falls back to computing 𝑎𝑟𝑔 𝑚𝑎𝑥 𝜋 𝑉 𝜋 .

Given an initial state 𝑠 0 ∈ 𝒮, the valuation function can be defined as, with 𝔼 𝜋 the expectation following policy 𝜋, ∀𝑠 ∈ 𝒮,

𝑉 𝜋 𝛾 (𝑠) = 𝔼 𝜋 [ 𝑇 𝑓 ∑ 𝑡=0 𝛾 𝑡 𝑟 𝑡 |𝑠 0 = 𝑠] (2)
The optimal valuation function 𝑉 * satisfies the Bellman equation, which can be written as, with 𝑠 ∈ 𝒮,

𝑉 * (𝑠) = 𝑚𝑎𝑥 𝑎∈𝒜 {𝑟(𝑠, 𝑎) + 𝛾 ∑ 𝑠 ′ ∈𝒮 𝑝(𝑠 ′ |𝑠, 𝑎)𝑉 * (𝑠 ′ )} . (3)
Once found, 𝑉 * gives the optimal policy 𝜋 * such that 𝑉 * = 𝑉 𝜋 * .

The Q learning model

Principle

Q learning is based on the use of a function 𝑄 ∶ 𝒮 × 𝒜 → ℝ as an equivalent of the valuation function, with (𝑠, 𝑎) ∈ 𝒮 × 𝒜,

𝑄 𝜋 (𝑠, 𝑎) = 𝑟(𝑠, 𝑎) + 𝛾 ∑ 𝑠 ′ ∈𝒮 𝑝(𝑠 ′ |𝑠, 𝑎)𝑉 𝜋 (𝑠 ′ ) (4)
The Bellman equation is then with 𝑄, ∀(𝑠, 𝑎) ∈ 𝒮 × 𝒜,

𝑄 * (𝑠, 𝑎) = 𝑟(𝑠, 𝑎) + 𝛾 ∑ 𝑠 ′ ∈𝒮 𝑝(𝑠 ′ |𝑠, 𝑎) 𝑚𝑎𝑥 𝑏 𝑄 * (𝑠 ′ , 𝑏) (5)
The idea is then to update incrementally the values of 𝑄 for each transition (𝑠 𝑡 , 𝑎 𝑡 , 𝑟 𝑡 , 𝑠 𝑡+1 ), with 𝑠 𝑡 , 𝑎 𝑡 being the state of the environment and the selected action at time step 𝑡, 𝑟 𝑡 the reward associated to 𝑠 𝑡 and 𝑎 𝑡 , and 𝑠 𝑡+1 the state Require: 𝑄, 𝛾 ∈ [0, 1], 𝛼 initialise state 𝑠 repeat 𝑎 ← choose action from an action set play 𝑎, observe reward 𝑟 and new state 𝑠 ′ 𝑄(𝑠, 𝑎) ← 𝑄(𝑠, 𝑎) + 𝛼(𝑟 + 𝛾 𝑚𝑎𝑥 𝑎 ′ 𝑄(𝑠 ′ , 𝑎 ′ ) -𝑄(𝑠, 𝑎)) 𝑠 ← 𝑠 ′ until training finished Figure 2: General Q learning algorithm [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF] resulting from the application of 𝑎 𝑡 on 𝑠 𝑡 . The update is done using the following formula, which comes from equation 5, with 𝛼(𝑠 𝑡 , 𝑎 𝑡 ) ∈ [0, 1) the learning rate;

𝑄 𝑡+1 (𝑠 𝑡 , 𝑎 𝑡 ) = 𝑄 𝑡 (𝑠 𝑡 , 𝑎 𝑡 ) + 𝛼 𝑡 (𝑠 𝑡 , 𝑎 𝑡 ) (𝑟 𝑡 + 𝛾 𝑚𝑎𝑥 𝑏 𝑄 𝑡 (𝑠 𝑡+1 , 𝑏) -𝑄 𝑡 (𝑠 𝑡 , 𝑎 𝑡 )) (6)

Parameters

Looking at equation 6, one can denote two parameters, 𝛼 and 𝛾 The discount factor 𝛾 can be interpreted as the sight length of the agent. Seeing equation 2, the higher 𝛾 is, the more delayed reward are taken into account. On the opposite, a 𝛾 of zero creates a myopic agent which considers only immediate rewards.

If transitions between states are stochastic, the learning parameter 𝛼 must be a sequence verifying the properties (see [START_REF] Christopher | Q-learning, machine learning[END_REF])

∑ ∞ 𝑘=0 𝛼 𝑘 = ∞ and ∑ ∞ 𝑘=0 𝛼 2 𝑘 ∈ ℝ.

General algorithm

The training algorithm is given in Figure 2. The training is finished when the state becomes terminal. Whether a state is terminal is decided by the underlying environment. Typically, the training algorithm will be run many times to have a Q function close enough to the optimal one.

Action selection Choosing actions consists in solving an exploitation-exploration trade-off. The exploration behaviour consists in exploring the state space, taking decisions that are not necessarily considered the best ones. The exploration is required to avoid local minima. Indeed, while the exploitation behaviour relies on the data accumulated to make the best decisions, it might carry out actions that are wrongly considered best because other ones have not been tried yet.

The exploration carries out actions to see whether, by chance, they would be better than the ones known so far. Different methods can be used to deal with this exploitation exploration trade off while selecting actions, see [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF] for a detailed review. In this paper, we use bandit methods. Bandits methods come from an analogy with slot machines, where a bandit with 𝑘 arms is able to activate 𝑘 slot machines sequentially. The goal of the bandit is to select each time the machine yielding the highest reward, maximising profit and minimising the regret of not activating the best machine. The UCB method (for upper confidence bound, see [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF]) bandit algorithm can be implemented by using action 𝑎 defined by, with 𝑡 the time step, 𝑁 𝑡 (𝑠, 𝑎) the number of times action 𝑎 has been performed in state 𝑠, 𝑐 ∈ ℝ + a constant controlling exploration,

𝑎 = 𝑎𝑟𝑔 𝑚𝑎𝑥 𝑎 ′ ∈𝒜 (𝑄 𝑡 (𝑠, 𝑎 ′ ) + 𝑐√ 𝑙𝑛 𝑡 𝑁 𝑡 (𝑠, 𝑎 ′ )
) .

The first term motivates exploitation. The second one, being higher as the number of visits is low, motivates exploration.

Implementation

In this paper, a simple implementation approach has been selected for computational reasons. In this form, the agent is a lookup table mapping stateaction tuples to their reward expectation. This way, the operation 𝑄(𝑠, 𝑎) ← 𝑄(𝑠, 𝑎) + 𝛼(𝑟 + 𝛾 𝑚𝑎𝑥 𝑎 ′ 𝑄(𝑠 ′ , 𝑎 ′ ) -𝑄(𝑠, 𝑎)) is straightforward and consists in the replacement of the old value by a new one. While this method has several advantages among which its simplicity, it cannot be scaled to high dimensional states or continuous states. More advanced methods can be used, like neural networks, see [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF].

Disruption management problem description

This paper focuses on the ability to swap aircraft when airlines are faced with disrupted operations. Swapping aircraft consists in exchanging aircraft between two flights. Intuitively, swapping can be cost effective for at least two reasons. The first is illustrated in Figure 3 where the amount of delay that is expected to be propagated by a given flight (𝑟𝑑 2 ) is divided between two flights producing 𝑑 1 and 𝑑 2 with 𝑑 1 + 𝑑 2 ≤ 𝑟𝑑 2 . In this examples, two flights are delayed instead of one but part of the buffer for flight 1 is used to recover delay from flight 2, so not only the delay is divided between more flights, but also reduced. This is cost effective because the cost of delay is non-linear and the cost of the two lower delays is lower than the cost of a single higher one. Note that aircraft swapping then helps to manage reactionary delay which account for 44% of all the delay experienced [START_REF]Coda digest 2017, all-causes delay and cancellations to air transport in europe[END_REF]. Another reason to perform aircraft swaps is that, in some cases, an aircraft with delay might have more legs in its schedule than another flight the airline can swap the flight with. By doing this swap, the number of legs where delay can be propagated can be reduced.

Finally, swapping are also often used in practice to save costs in other ways that are out of the scope of this paper. For instance the airline can concentrate all delay into one flight and then cancel it; modelling this would require More parameters such as additional passenger information (e.g. type of passengers, and their connections) can be used by airlines to better estimate the cost of the different options.

Some constraints need to be considered when performing the swaps. An aircraft can be swapped with another only if the flight of one ends where the flight of the other starts and the aircraft type is the same. Or in other words, two aircraft can be swapped if they have an airport in common in their flights itineraries. On real operations, further constrains need to be considered such as crew availability, number of seats per specific aircraft, etc.

An aircraft becomes available for a flight after the turnaround operations are preformed. For example, in Figure 3b, the first aircraft can be used for the next rotation of the second flight after its turnaround. These ground operations are modelled as a function of the type of aircraft and airport.

Scope of model

The main objective of the air traffic model is to capture the propagation of delay through the network, as this will allow us to capture situations as the ones described in Figure 3. The simulator focuses on the fleet of an airline and on one day of operations. The simulator is driven by the landings of aircraft. When an aircraft lands, it can either follow its scheduled flight plan sequence or swap the remaining flights of the day with another aircraft of the same type. As mentioned, other disruption management strategies (e.g., ferrying, flight cancellation or trajectory modification) are not considered. There are no standby aircraft available to swap with and crew management is not considered.

A total cost is computed at the end of the day based on flight delay and on the ending position of the aircraft.

Delays and uncertainty

Delays have been capped to five hours. Above this threshold, it is generally more cost effective to cancel the flight which is out of scope of this paper.

Sources of delay

There are four sources of delay and uncertainty in the system:

• reactionary delay,

• taxiing in and out of the runway,

• air traffic flow management delay,

• any other sources of delay (e.g., ground operations)

The distributions used to generate the delays have been calibrated and validated in previous projects [START_REF]ComplexityCost project. D4.5[END_REF][START_REF]Vista project. D5.2 -final assessment report[END_REF].

Taxiing The taxiing in and out time distributions are Gaussians. The mean and the standard deviation depend on the airport and type of operation [START_REF]ComplexityCost project. D4.5[END_REF].

Reactionary Reactionary delays, i.e., delays caused by delays on previous flights, are explicitly modelled and thus not generated from a distribution.

Air traffic flow management (ATFM)

A probability and distribution of ATFM delay is built on historical data analysing the Demand Data Repository (DDR2) [START_REF]DDR2 reference manual for generic users[END_REF].

Miscellaneous Encompasses all other sources of primary delay not explicitly modelled (e.g., late arrival of passengers, mechanical failure, &c.). The distribution of miscellaneous delays is an exponential one with parameter 15 capped at 90 minutes [START_REF]ComplexityCost project. D4.5[END_REF].

Exceptional delays

To stress the environment, exceptional delays are randomly created. Each simulation is started with a probability of encountering an exceptional delay. Each departing flight might have an exceptional delay, based on this probability. A delay is said to be exceptional if it is superior to three hours as airline must compensate clients from three hours of delay [17].

Calibration and validation

The behaviour of the simulator has been checked against the values given in [START_REF]Coda digest 2017, all-causes delay and cancellations to air transport in europe[END_REF]. Particularly, have been checked

• the average departing delay,

• the average reactionary delay,

• the proportion of reactionary delay among all delays.

As an overview, 21.21% of the flights were delayed and some additional data has been gathered in table 1.

Costs

Costs depend on the aircraft model and the delay. The cost function is increasing non linearly with the delay: the more a flight is delayed, the higher the ratio cost/delay is (i.e., the second derivative of the cost w.r.t the delay is positive). These costs are modelled from [START_REF] Cook | European airline delay cost reference values[END_REF]. Additionally, if an aircraft ends in an airport which is not the final airport indicated on the initial schedule, a cost is added to reflect the rerouting of crews or aircraft. This cost has been set to the maximum cost of delay.

Simulator as reinforcement learning environment

The successive steps of the simulator fit the succession of states needed in reinforcement learning.

Feeding the agent with all the data computed in the simulator would be inefficient. As an example, states used by the algorithm need to be visited as much as possible along an episode, which requires them to be, ideally, time independent. It would therefore be counter productive to embed the time of the simulation in the state.

To ease the work of the algorithm, states are converted to observations. An observation is the reduction of a state, gathering the essential information to allow the agent to take the appropriate action and estimate the cost associated to the action.

Choosing which information to include in the observation is a difficult problem. They need to be precise enough, to improve final performance; but not too detailed to avoid the explosion of the number of states, leading to a slower convergence. Fields that can be considered to be included in the observations are: delay, number of extra flights in the day remaining for a given aircraft or type of airport.

Actions

In each state, the agent performs an action on the environment. Here, an action is either swapping the landed aircraft with another one or doing nothing. Swapping two aircraft means that the aircraft exchange the remaining of their respective flight paths. We thus consider swapping aircraft equivalent to swapping flights or, to be more precise, flight paths.

One must then decide which flights can be swapped with. The first way would be to allow to swap with any not flown flight departing from the current airport. However, this have two drawbacks. First, too many actions would be made available, slowing the convergence. Secondly, actions wouldn't be clearly recognisable by the agent. The agent needs to associate an expectation of the cost following an action on a state. But swappable flights might be very different from one state to another which could increase the variance of the final reward given the current state.

Reward

In reinforcement learning, the reward allows the agent to decide which action is the most suited to the state the environment is in. Furthermore, by the estimation of reward expectations, the agent is also able to determine the best action for not only the current state but also the probable sequence of all future states.

In our model, the reward is the final cost of delays. Since the algorithm maximises the expectation of reward, if the value on which the reward is based should be minimised, the reward will be the opposite of this value. We will therefore use the opposite of the cost as reward. The algorithm uses one day of operation of one airline. It has been tested on a subset of the traffic of Vueling on October 12, 2014. The initial schedule has a fleet of 90 aircraft. In order to speed up experiments, only 6 aircraft have been kept. The aircraft has been chosen such that there is a fair amount of swapping possibilities, i.e., each aircraft has at least one swapping possibility along its flight path. Flight data has been obtained from [START_REF]DDR2 reference manual for generic users[END_REF].

The cost of reallocation at the end of the day has not been taken into account. As reallocation costs only happen at the end of an episode, they are the most delayed reward possible and are thus hard to learn. Given that this paper is a proof of concept and not a real life application, applicability is reduced in favour of results.

Observations and actions

Observation

Two type of observations have been tried. The first one is based on flight paths and contains:

• a mapping from aircraft to flight paths,

• a mapping from aircraft to their delay,

• the identifier of the landed aircraft,

• the delay of the landed aircraft,

• a mapping from aircraft to whether, if there is a swappable flight on its flight path, the SOBT (scheduled off block time) of this swappable flight is before the ready time of the landed aircraft,

• a mapping from aircraft to whether it has more remaining flight in its flight path than the landed aircraft. The second observation type does not contain the flight path nor the delay. The fields considered are:

• a mapping from aircraft to whether the SOBT of its next swappable flight is before the ready time of the landed aircraft,

• a mapping from aircraft to whether it is currently flying toward the current airport,

• a mapping from aircraft to whether it has more remaining flights than the landed one,

• a mapping from aircraft to whether it is on its original flight path (if reallocation costs are considered),

• the identifier of the landed aircraft.

• the accumulated delay on the fleet Table 3 contains an example of the fields considered in the second type of observation. To avoid the explosion of the number of states, delay amounts are further discretised from the set of integers to a finite number of variables (e.g. {low, medium, high}). With 𝑑 the number of values used to describe delay and 𝑛 the cardinal of the fleet, there are 𝑛𝑑 ⋅ 𝑛! 2 2𝑛 𝑑 𝑛 observations for the first model and 𝑑𝑛2 4𝑛 for the second (with generally 𝑑 ≥ 𝑛).

Action

A flight is considered swappable if:

• the origin airport is the same as the current one,

• it is the first flight (according to SOBT) in the flight path of the aircraft to match the above requirement,

• the previous flight has not landed yet. In short, for an aircraft, a flight is swappable if it is the first one to depart from the current airport and the aircraft is not on the ground going ready to do it. Figure 4 shows an example of two flights that can be swapped: aircraft 1 is supposed to fly the plain legs while aircraft 2 flies the dotted legs. Aircraft 1 is arriving at airport C and aircraft 2 just departed from B, at landing of aircraft 1, it can swap the remaining of its flights taking the C to D leg. Aircraft 2 will therefore operate the C to E leg.

Results

Parameters

All the parameters tuned in the model are:

• 𝛾 the discount factor, see 3.2.2.

• 𝑐 the exploration control parameter when using UCB bandits, see Equation 7.

• 𝑝 𝑑 the probability of introducing a severe delay on each flight, a severe delay is 3h.

• 𝑞 𝑖 the initial value of the 𝑄 matrix.

For the experiments, the parameters (𝛾, 𝑐, 𝑝 𝑑 , 𝑞 𝑖 ) = (0.95, 10, 0.06, -9 ⋅ 10 4 ) have been used.

Learning process

To verify that the agent learns and performs better, a metric from [START_REF] Mnih | Playing atari with deep reinforcement learning[END_REF] will be used. At the beginning, random states are taken by following a random policy along an episode. Then during the training, at each time step, with 𝑆 the set of selected states and 𝒜 the set of available actions, is computed This metric thus gives an indication of the evolution of the discounted reward expectation through training. Figure 5 shows this metric used with both observations. The second observation type seems to perform better since it reaches the -8 ⋅ 10 4 of expected discounted reward in approximately 1,000 trainings whereas the first observation type does not even reach the -8 ⋅ 10 -4 in 5,000 trainings. The overall increase asserts that the agent learns how to perform better, since its expectations of rewards are getting higher. The sudden falls may be interpreted as the agent realising that delays might happen.

1 𝑐𝑎𝑟𝑑 𝑆 ∑ 𝑠∈𝑆 𝑚𝑎𝑥 𝑎 ′ ∈𝒜 𝑄(𝑠, 𝑎 ′ ). (8

Comparing with the idle behaviour

The usability of the algorithm is determined by asserting whether it performs better than doing nothing. Figure 6 shows the boxplots of the distribution of rewards (i.e., negative cost of delay at the end of the day) for the agents and the idle behaviour. The assumption that the agent with observation type 2 is better than the other is verified, since all displayed quantiles are higher for the former. Comparing with the idle agent, our trained agent seem to perform worse in general. However, the agent 2 (with observation type 2) has a shorter left whisker than the idle, showing that the agent is able to recover perturbed episodes.

The fact that the agent does not perform as well as the idle might be explained by local maxima, i.e., the agent believes that, given a certain observation, swapping is the best idea although it is not. Indeed, even after 20,000 episodes, it can be seen, inspecting the details of the simulations, that some observations have been visited only a dozen times. This problem might be solved by training more the agent or providing other options rather than just swapping aircraft. The average number of swaps per simulated day of operations, computed on 1,000 episodes ran with trained agents, are 8.7 for agent 1 and 7.3 for agent 2. The performance observed can also be explained due to the limited options given to the agents (swapping or not), in some cases swapping can be a risky operation as downstream effects can be generated. The limited set of options explains the relatively high number of swaps performed but further validation is also needed. The next section discusses some future work that can be done to improve the overall final performance of the algorithm.

Conclusion

This paper presents a method based on machine learning to deal with air traffic disruptions by doing aircraft swapping. The model used for the algorithm is able to manage a whole fleet of aircraft and is primarily modelling the delay propagated through flights, as well as defining the actions that can be performed on the fleet. The step by step dynamic of the simulator, coupled with the cost associated with an action is well suited for reinforcement learning.

A basic reinforcement learning algorithm, the tabular Q learning, is presented here, along with a non trivial method concerning action selection. The results evince some interesting features, namely the ability to recover from heavily disrupted traffic and future potential lines of research.

Further work

Concerning the algorithm, several options are possible. The tabular method might be improved by choosing more adequately the states. Indeed, it has been seen in Figure 5 and Figure 6 that the design of the observation impacts the performances of the agent. These features might be chosen either on expert knowledge, or based on analysis of the relations between the variables of the simulator and the resulting cost. This analysis might be done using supervised learning and decision trees, where the tree should predict the cost based on the variables.

More advanced reinforcement learning algorithms can be used, such as replacing the look-up table by a neural network such as in [START_REF] Rummery | On-line q-learning using connectionist systems[END_REF], more advanced recurrent neural networks as in [START_REF] Bakker | Reinforcement learning with long short-term memory[END_REF] or using the latest A3C (Advantage Actor Critic) algorithm by Deepmind presented in [START_REF] Mnih | Asynchronous methods for deep reinforcement learning[END_REF].

The model can also be extended, by e.g., adding the possibility to cancel or ferry flights. Passengers can also be included in the model, giving the opportunity to choose to wait for an arriving flight having delay if there are passengers from this flight who connect with the departing flight. Aircraft performance could also be modelled, giving the ability to choose whether to speed up the next flight, as could the opportunity to choose between different routes. However, adding all these possibilities will increase the number of possible actions, making the above methods inefficient. To deal with large action space, a restricted Boltzmann machine could be used as a substitute for the look-up table, as explained in [START_REF] Sallans | Reinforcement learning with factored states and actions[END_REF] where an agent has been proved able to manage 2 40 actions.

More complex cost estimations could be used, for example by incorporating explicit passenger costs.

Finally, further validation of the algorithm outcome should be needed. However, information on aircraft swap can be hard to obtain since available data set do not have information about if flights were swapped or not.

  No swapping: Flight 1 on time, Flight 2 expected to propagate reactionary delay (𝑟𝑑 2 ) Swapping: Flight 2 experiencing 𝑑 2 delay and Flight 1 expecting 𝑑 1 delay. 𝑑 1 + 𝑑 2 ≤ 𝑟𝑑 2

Figure 3 :

 3 Figure 3: Example of benefit of swapping

Figure 4 :

 4 Figure 4: Swappability example: airports and flight for two aircraft

Figure 5 :

 5 Figure 5: Average maximum Q values over 5000 episodes with 𝑝 𝑑 = 0.06, 𝑐 = 10, 𝛾 = 0.95, 𝑞 𝑖 = -90, 000.

Figure 6 :

 6 Figure 6: Comparing the idle behaviour with the agent. Agent 1 uses the first observation type while agent 2 uses the second. Both agent have been trained over 20,000 episodes.

Table 1 :

 1 Statistics of the simulator calibration (average among all flights and quantiles among delayed flights, in minutes).

	Variable Avg.	Q10 Q50 Q70 Q90
	Reactionary delay 3.97	0	5	20	46
	Departure delay 11.04 18	32	45	70

Table 2 :

 2 First observation type example.

	Field description	Example instance
	aircraft → flight path	{(𝑎 1 , 𝑓 2 ), (𝑎 2 , 𝑓 1 ), … }
	aircraft → delay	{(𝑎 1 , low), (𝑎 2 , high), … }
	aircraft → sobt before ready time	{(𝑎 1 , 𝑡), (𝑎 2 , 𝑓), … }
	aircraft → more remaining	{(𝑎 1 , 𝑓), (𝑎 2 , 𝑓), … }
	landed aircraft id	2
	landed aircraft delay	low
	4 Experimental setup
	4.1 Schedules

Table 3 :

 3 Second observation type example.

	Field description	Example instance
	aircraft → sobt before ready time {(𝑎 1 , 𝑡), (𝑎 2 , 𝑓), … }
	aircraft → toward stn.	{(𝑎 1 , 𝑓), (𝑎 2 , 𝑡), … }
	aircraft → more remaining	{(𝑎 1 , 𝑡), (𝑎 2 , 𝑓), … }
	aircraft → on orig. flight path	{(𝑎 1 , 𝑓), (𝑎 2 , 𝑡), … }
	landed id.	4
	total delay	high
	Table 2 presents an example of the fields included in this observation de-
	scription.