A framework for collaborative air traffic flow management minimizing costs for airspace users: Enabling trajectory options and flexible pre-tactical delay management

A Framework for Collaborative Air Traffic Flow Management Minimizing Costs for Airspace Users: Enabling Trajectory Options and Flexible Pre-tactical Delay Management Yan Xua,b, Ramon Dalmaub, Marc Melgosab, Adeline Montlaurb, Xavier Pratsb aCentre for Aeronautics, School of Aerospace, Transport and Manufacturing, Cranfield University, Cranfield, MK43 0AL, Bedford (UK) bDepartment of Physics - Aeronautics Division, Technical University of Catalonia, Castelldefels 08860, Barcelona (Spain) Abstract This paper proposes a collaborative air traffic flow management (ATFM) framework, in the scope of trajectory based operations, aiming to improve the costefficiency for airspace users (AUs) when facing ATFM regulations. The framework consists of four modules. The first one involves the AUs initially scheduling their preferred trajectories for all their flights. Based on this initial demand, the second module (assumed to be on the Network Manager -NMside) detects time-varying hotspots (i.e. overloaded sectors along the day). In the third module, hotspot information is shared back to the AUs who plan alternative trajectory options to avoid crossing these congested airspace volumes (in the lateral and vertical domain); as well as providing to the NM different pre-tactical delay management preferences (including ground holding, linear holding, air holding and pre-tactical delay recovery); based on their internal cost breakdown structures. Incorporating all these potential combined options, the last module computes the best trajectory selections and the optimal distribution of delay assignments, such that the cost deviation from the initial status (all the user-preferred trajectories) is minimized. This model is formulated as mixed integer linear programming (MILP) and validated by a real-world case study focused on 24 hours of traffic over the French airspace. Results using the proposed framework suggest a significant system delay reduction by nearly 97% over the existing method, whilst yielding an average of less than 100 kg extra fuel consumption and 50 Euro extra route charges for the 11% flights diverted to their alternative trajectories. Keywords: air traffic flow management, trajectory based operations, demand and capacity balancing, collaborative decision-making, trajectory options Preprint submitted to Transp. Res. Part B: Methodological February 26, 2020 1. Introduction The air transportation system currently faces a significant strain from the fast-growing flight demand. This has been evidenced in recent years by severe flight delays and more commonly-seen network congestion in many regions across the world. For example, in Europe, year 2016 saw an average departure delay per flight of 11.3 minutes (and 29.1 minutes, per delayed flight, for the average arrival delay), an increase of 9% in comparison to 2015. Further, over this time period flights delayed more than 30 minutes increased 9.8%, with an average of 1.9% for operational cancellation monthly (EUROCONTROL, 2017a). A series of reports, e.g., Cook and Tanner (2015), can be used as a reference for European delay costs incurred by airlines. In the United States, in turn, 17% of the flights were delayed by more than 15 minutes in 2016, with another 1.2% canceled (US Department of Transportation,2016). Ball et al. (2010) presented the economic impact of flight delay, where the cost of delay to airlines is estimated by modeling the relationship between the total cost and operational performance metrics. Given an average delay cost of $62.55/min anticipated for the U.S. passenger carriers (Airlines for America, 2016), the 60 million minutes of total delay in this year led to an estimated $3.8 billion direct aircraft operating costs. One of the primary causes for those delays and congestion is that the number of flights (demand) often exceeds the supply of the airspace accommodation (capacity). In addition, the sustained growth in traffic also shows some seasonal or exceptional peaks (holiday seasons, major sport events, etc.). Conversely, convective weather, airspace restrictions, overloaded airports and air traffic control (ATC) industrial actions, to name a few, can temporarily reduce this supply. The effort thereby to achieve demand and capacity balancing (DCB) is typically known as Air Traffic Flow Management (ATFM). Examples of ATFM systems include the Enhanced Tactical Flow Management System (ETFMS), implemented by Eurocontrol’s Network Manager Operations Centre (NMOC, previously Central Flow Management Unit), which compares traffic demand, regulated demand and load against capacity to assess possible imbalances in the European airspace and allows the implementation of measures to resolve these imbalances in the traffic, such as regulations or rerouteing. With the assistance of the Network Operations Plan (NOP) Portal, European ATFM stakeholders will have access to the upto-date information of the network situation which will allow them to more 2 dynamically plan and manage the demand and capacity (EUROCONTROL, 2017b). Similar initiatives exist in the United States, including Ground Delay Programs (GDPs) and Airspace Flow Programs (AFPs). GDPs control the arrival rate at an affected airport by assigning departure delays to flights at their origin airports (FAA,2009). An AFP identifies constraints in the enroute system, regulating flights filed into the Flow Constrained Area (FCA) (Libby et al.,2005). While a flight has no choice but to eventually end up at its destination airport, a capacity-constrained en-route sector can often be bypassed at limited cost by selecting an alternative route. To that aim, AFPs specify available reroutes that avoid the FCA. Flight operators may then choose to accept the delay for an affected flight, or to take the available reroute (Pourtaklo and Ball,2009). The overall objective of these ATFM initiatives is typically to reach a compromise solution across all stakeholders based on some fairness criteria (e.g., first scheduled, first served policy). In this context, specific preferences for the airspace users (AUs) were not typically taken into account in the early development of ATFM programs. With the paradigm shift for the future air traffic management (ATM) proposed by SESAR (Single European Sky ATM Research) in Europe and NextGen (Next Generation Air Transportation System) in the United States for instance, the AUs are expected to increasingly participate in ATM decisions, using, in particular, more collaborative decision making (CDM) mechanisms. CDM is more of a philosophy for better managing air traffic through information exchange, procedural improvements, tool development, and common situational awareness (Ball et al.,2000). It allows decisions to be taken by those best positioned to make them based on the most comprehensive, up-to-date accurate information and ensuring that all concerned stakeholders are given the opportunity to influence the decision (EUROCONTROL, 2017b). CDM was first implemented in GDPs in the late 1990s (Chang et al., 2001), and then incorporated tools such as flight substitution, cancellations, compression, and slot credit substitution (Ball et al.,2005). SESAR has been advancing this through development of the User Driven Prioritisation Process (UDPP) to achieve additional flexibility for AUs to adapt their operations in a more cost-efficient manner (SESAR,2015). Increased CDM is also found in the Collaborative Trajectory Options Program (CTOP) that has been deployed since early 2014 in the United States, and which is built upon concepts of GDPs and AFPs. AUs are allowed to submit, well in advance of the issuance of the program, a set of desired reroute options that 3 can be used to route around an FCA or constraint (FAA,2014). In general, under CDM, ATFM is expected to be conducted in a way that gives significant decision-making responsibilities to AUs (Vossen et al.,2012). To achieve the top-level aspiration of the ATM paradigm shift described above, one must overcome the amalgamation of the flight planning and execution phases, based on advanced flight trajectory management. Indeed, the flight trajectory is established as the fundamental element of such operating procedures, which is referred to as Trajectory Based Operations (TBO). Concretely, TBO represents an ATM method for strategically planning, managing and optimizing flights throughout the operation by using time-based management, information exchange, and the aircraft’s ability to fly precise paths in time and space (SESAR,2020;FAA,2018). It requires innovations to be introduced in all parts of the ATM system to realize the envisioned changes. Stakeholder involvement, better data sharing and usage with System Wide Information Management (SWIM), introduction of advanced decision support tools for human operators, both on ground and in the air, and improving management in all the facets of the air transportation, are just a few envisioned and needed changes. The TBO concept has nowadays became the main focus of validation conducted in International Civil Aviation Organization (ICAO) Global Air Navigation Plan (ICAO,2016), as well as in multiple regional programmes, including the SESAR (Europe) and NextGen (U.S.), and also CARATS (Japan), OneSKY (Australia) and Sirius (Brazil). Although there may exist slight differences for the TBO-associated definitions through the different programmes, the general principle is indeed of high degree of consistency. For the sake of clarity, this paper takes all terminology from the SESAR TBO concept (SESAR,2017). In the above context of TBO, a framework for Collaborative Air Traffic Flow Management (C-ATFM) is introduced in this paper. The main structure of the framework is presented in Fig. 1, which is composed of four modules, each representing the tasks that might be conducted by either the AUs or the NM. An outline of each module is given as follows: •Module I: Initial planning of user-preferred trajectories This module refers to the planning of trajectories by the AUs, taking into account forecast weather conditions and strategic ATM constraints, such as route availability restrictions or flight level allocation and orientation schemes (see Section 3.1). The trajectory optimization 4 Figure 1: An overview of proposed collaborative air traffic flow management framework. and planning methodology used in this module has been previously reported in (Dalmau et al.,2018). According to the SESAR concept of operations (ConOps), these trajectories would correspond to the Business Development Trajectories (BDT). •Module II: Detection of demand and capacity imbalance Based on the trajectories computed in the previous module (i.e. initial traffic demand), a primary detection of imbalances between traffic demand and airspace capacity is conducted in this module (see Section 3.2). Time-varying hotspot volumes are thereby identified. Combined with airspace geometric descriptions, the specific hotspot avoidance information is shared back to all AUs with one or more concerned flights, i.e., flights traversing at least one hotspot (see Section 3.3). •Module III: Submission of trajectory options and pre-tactical delay management preferences 5 With the hotspot avoidance information received, concerned AUs compute alternative trajectories for their captured flights to avoid entering these hotspot volumes, using the same trajectory optimization techniques implemented for initial trajectory planning (see Section 3.4). Different preferences are also allowed on how AUs wish to manage (at pre-tactical/dispatch level) the delay (see Section 3.5). According to the SESAR ConOps, these trajectories would correspond to the Shared Business Trajectories (SBT). •Module IV: System-wide optimization to balance demand and capacity This module is initiated by the NM to balance the demand and capacity, yielding eventually the best combinations of trajectory selections and delay assignments among all regulated flights (see Section 4). The objective considered in this paper minimizes the overall deviation with respect to the ideal status where all AUs could maintain their initial BDTs. Resulting trajectories would correspond to the Reference Business Trajectories (RBT). The modular design of this framework allows flexible adjustment of one or more modules for various purposes. In particular, this paper focuses on the benefits analysis with respect to an ideal deterministic setting for the framework over the current operations. Taking into account the uncertainty in the system, stochastic models could be adopted in Module IV to better address such issue in reality. Also, additional mechanisms (such as UDPP) for collaborative trajectory planning can be considered in Module III to give more priority to the equity concern. Then, a real-world case study is presented in Section 5, using realistic data of 24 hours traffic crossing the French airspace. Finally, Section 6summarizes the conclusions of this paper. The supplement materials are provided in Appendix from Athrough E. 2. Literature review Following the pioneering work done by Odoni (1987), researchers have focused on the development of models to minimize the congestion costs in response to airport capacity reduction. Delay assignment, such as ground holding, has been used as the most common short-term ATFM initiative (see (Terrab and Paulose,1992;Richetta and Odoni,1994) for instance). If 6 congestion at airspace sectors is also taken into account, the problem of controlling release times and speed adjustments as well as reroutings of aircraft while airborne for a network of airports (including sectors) was studied in (Bertsimas and Patterson,1998,2000;Lulli and Odoni,2007). With the added complication of the problem, dynamical rerouting proved highly effective in the case of weather affected approaches around the airport which itself can operate at full capacity (Mukherjee and Hansen,2009). Aiming at realistic applications, the computational challenges arising from previous models were largely reduced by means of a massively parallel Dantzig-Wolfe decomposition method applied to the Bertsimas Stock-Patterson model (Rios and Ross,2010;Tandale et al.,2013). Regarding CDM, researchers have explored different ways to incorporate mechanisms to previous models, aiming at further improving ATFM performance. Moreover, some potential metrics to achieve an acceptable fairness level, compensated by some loss of system efficiency, were proposed and discussed in (Barnhart et al.,2012;Bertsimas and Gupta,2015). An efficient dual network flow formulation for the static-stochastic GDP was presented in (Ball et al.,2003), showing how this formulation can be implemented under CDM with equity considerations. The integer programming formulation for the GDP was extended by Vossen and Ball (2006a), to approximate the CDM process where the slot compression step can be considered as a mediated bartering between AUs. The opportunities for slot trading in a single airport setting were studied under the condition that GDP offers are given to trade from various airlines (Vossen and Ball,2006b). Similarly, slot exchange mechanisms in an AFP scenario through a mediated bargaining of assigned slots was discussed in (Sherali et al.,2011), allowing AUs to improve costefficiency. The overall collaboration process was then simulated by Molina et al. (2014) using an agent-based modeling approach, where different ATM stakeholders were modeled in a CDM framework. For the current version of CTOP, an RBS (ration-by-schedule) scheme is adopted. Namely, flights are assigned the best available routes and slots available at the time flight operators submit their preference requests during the planning period, in a sequential manner (Miller and Hall,2015). Yet, the rules of allocation in that algorithm have some obvious drawbacks, such as airlines’ competitive responses. In this context, Kim and Hansen (2015) investigated a game theoretic treatment of airline preference submission behavior within the First Submitted First Assigned allocation process. Recently, an alternative flight scheduling approach for CTOP, based on lin7 ear optimization instead of pure RBS, has been studied using a Max-Min fairness rule to guarantee some equity (Rodionova et al.,2017). Furthermore, to enhance the involvement in the CDM paradigm, there has been also much research conducted from the AUs’ point of view. Early studies (Meyer and Oster,1981;Morrison and Winston,2010) explored the impacts of deregulation and the statistical relationships between airline operating cost variables and financial performance, with a focus on fuel and crew costs. Holloway (2008) provided an overview of the different types of schemes established to categorize costs in the airline operations. Flight cancellation decisions in GDP were studied in (Xiong and Hansen,2009), revealing the value of a flight cancellation and airline preference structure in their decision making process. With the forthcoming TBO concept, a transition in ATM from control by tactical clearance to management by reference to a trajectory is expected, which emphasizes the importance of an efficient trajectory planning (optimization) from AU side. The aircraft trajectory optimization problem can be modeled and solved using optimal control theory (Betts and Cramer,1995; Betts,2010). A recent study (Gardi et al.,2016) provided a comprehensive review of the different trajectory optimization techniques, with a special focus on the recent advances introduced in the ATM context. Using optimal control has the advantage that the dynamic equations of the aircraft are taken into account, producing very accurate and realistic trajectories while obtaining the guidance commands as result of the optimization process. Complete frameworks using this approach have been reported in (Soler et al.,2012; Dalmau et al.,2018). Using this technique, Xu et al. (2017); Xu and Prats (2017a) showed how to optimally handle ATFM and additional reactionary delays at dispatch (planning) level by means of linear holding and pre-tactical delay recovery strategies. 3. Collaborative Trajectory Design This section introduces the interactive trajectory design process, aligned with the CDM paradigm described before. Specific avoidance information is generated by the NM and is shared to concerned AUs for each affected flight. Precisely-designed alternative trajectories, along with preferences on delay management, are produced by AUs and eventually submitted back to the NM (Modules I, II and II in Fig. 1). 8 3.1. Initial schedule of user-preferred trajectory (Module-I) In the European ATFM system, AUs have been offered a high level of flexibility in regard to flight planning (Boli´c et al.,2017), which enables the scheduling of initial trajectory to well reflect their preferences. For dayto-day operations, these preferences are generally focused on the aircraft direct operating cost encompassing a weighted sum of fuel consumption, route charges and time-related costs (such as crew and maintenance fees). Aiming at minimizing the total operating cost per flight, in this paper both the lateral route and vertical profile are optimized to generate an optimal 4D trajectory in order to represent the user-preferred trajectory (i.e. the BDT). Nevertheless, the details of producing this initial traffic demand are out of the scope of the paper and the methodology was previously reported in (Dalmau and Prats,2017;Dalmau et al.,2018). Next, a brief summary of this methodology is given. (a) Lateral route affected by weather (b) Vertical profile with ATM restrictions Figure 2: Initial trajectory planning decoupled to lateral route and vertical profile. The trajectory optimization algorithm used here decouples the computation of the optimal lateral route and vertical profile. The available lateral route network is represented by a graph, in which the nodes represent waypoints or navigation fixes and the edges are the route segments. Based on this graph, the optimal lateral route minimizing the direct operating cost is computed by using the A* algorithm (Hart et al.,1968). The difference in national unit rates with regards to the route charges has been taken into account. Realistic weather conditions, especially wind fields that have a great impact on the trajectory, are also considered, using GRIdded Binary 9 if either the origin or destination airport is inside or close to any hotspot volume, the lateral avoidance trajectory may not be possible. (a) Initial optimal route (b) Alternative optimal trajectory avoiding hotspots in the lateral domain Figure 5: 4D trajectory optimization: optimal route planning over a conventional structured ATS network For the vertical-avoidance alternative trajectory, the lateral route is fixed to that initially scheduled and for each hotspot sector i, the segments of route traversing the hotspot are identified, together with lower and upper altitudes defining that sector, hi Land hi U, as shown by the red squares in Fig. 6a. Then, during the numerical integration of the climb phase, if the along-path distance is included into any of the climb segments, it is checked whether the aircraft would penetrate altitude hi Lfrom below at the next integration step. If so, a level off at constant altitude and CAS (or Mach if hi Lis above the cross-over altitude) would be performed until reaching the end of the segment. Then, the climb is resumed until reaching the Top of Climb (TOC) at the optimal cruise altitude (compare the TOC positions in Fig. 6a and in Fig. 6b). The same principle applies for the integration of the descent phase. When generating the cruise phase, from the TOC to the TOD (Top of Descent), the flight levels in the range [hi L, hi U] are removed from the candidate set of flight levels within the segments. At each integration step, the optimal cruise altitude (in terms of the direct operating cost) is computed to decide whether a step climb (see Fig. 6b) should be performed or not. The solving algorithm follows an iterative process similar to those implemented in state-of-the-art on-board Flight 16 −600 −400 −200 0 Distance to go [NM] 0 100 200 300 400 Speed [kt] / Altitude [FL] TAS CAS Altitude GS Mach 0.2 0.3 0.4 0.5 0.6 0.7 0.8 Mach [-] (a) Initial optimal altitude and speed profiles −600 −400 −200 0 Distance to go [NM] 0 100 200 300 400 Speed [kt] / Altitude [FL] TAS CAS Altitude GS Mach 0.2 0.3 0.4 0.5 0.6 0.7 0.8 Mach [-] (b) Alternative optimal trajectory avoiding hotspots in the vertical domain Figure 6: 4D trajectory optimization: optimal altitude and speed profiles under conventional flight level allocation and orientation constraints Management System (FMS), which systematically evaluates all potential sequences of decision parameters and selects the optimal one. It should be noted, however, that eventual ATC restrictions might restrict the number of climbs/descents in cruise to avoid hotspots (to avoid the so called “yoyo” effect). Although these restrictions could be easily incorporated in the proposed methodology, for the sake of generality this paper assumes that AUs will always submit their optimal trajectories, regardless of how many flight level changes resulted from the hotspot avoidance. 3.5. Pre-tactical delay management preferences (Module-III) In addition to alternative trajectory options, delays might still be required to solve the demand and capacity imbalance. Different types of initiatives may apply to absorb (or recover) the assigned delays in the pre-tactical phase (i.e. at flight dispatch level), and their costs, limitations and implementations are not necessarily the same. In this paper, four specific ways to handle delays at dispatch level are considered including ground holding, airborne holding, linear holding and delay recovery (Xu and Prats,2017b). These initiatives will change the Controlled Times Over (CTOs) at positions, which can be regarded as different ways to adjust the 4D trajectory’s timeline. Airborne holding would consume more fuel due to the extended flight track, whilst ground holding has no impact on fuel consumption. Due to 17 the increased extra fuel, the airborne holding time is fairly limited, taking into account that safety related issues may arise from a reduction of the on-board reserve fuel. Ground holding, however, can only be performed at the departure airport, prior to take-off. Airborne holding (including holding patterns or path stretching) can be done at any available airspace, in theory, but practically it is typically performed in designated locations. Linear holding and pre-tactical delay recovery are performed airborne too, but rather than extending the flight path, they are executed following the original trajectory by means of a cost-based speed control method (i.e. decreasing or increasing speed to absorb or recover delay, respectively). Generally, the amount of linear holding and delay recovery that can be achieved depends on factors such as the aircraft type, trip distance, payload, cruise flight level and etc., as well as the extra fuel allowance (if any) when applying these strategies. For more information, see (Xu et al.,2017;Xu and Prats, 2017a). In order to avoid confusion, it is worth emphasizing that in this paper delay recovery is considered at flight dispatch level (pre-tactical recovery), while obeying all the ATFM controlled times of arrival (CTAs) distributed along the trajectory. Obviously, recovery can only be performed if CTOs are given in one or several positions along the route, leaving some margin to recover delay with the flight segment going from the position of the last CTO to the destination airport. Consequently, delay recovery cannot be performed if a CTO is given at the destination airport. The delay recovery considered in this paper must be differentiated from the tactical delay recovery procedures typically performed in current operations, which is a consequence of enforcing only the Controlled Time of Departure (CTD) instead of CTO/CTA at the affected sector/airport (where the latter is actually effective). Although recovering delay could benefit the system in general, this pretactical delay recovery is allowed only if some delay will be imposed at the forepart of a trajectory (e.g., ground holding at the origin airport) during the delay assignment stage. The reason is as follows: this paper assumes that the BDTs/SBTs (submitted by the AUs) are their most preferred trajectories, which means that when they compute the speed profiles, the time-related costs (including the buffer time for ground operations) should have been considered already. In other words, increasing (or reducing) aircraft speed in order to recover (or absorb) delay airborne may incur some extra operating costs for particularly the AUs. Due to the lack of information in their preferences of delay recovery over the extra costs, this paper assumes, for 18 simplicity, that they are willing to pay more to fly faster only if their flights will be delayed. Otherwise, they would prefer to fly as initially scheduled. 4. Demand and Capacity Balancing In this section, a linear optimization model is presented. It incorporates all potential options, such as alternative trajectories and pre-tactical delay management preferences coming from the collaborative trajectory design process presented in Section 3, in such a way that traffic demand is balanced with available capacity (Module IV in Fig. 1). The mathematical formulation is based on the well-studied Bertsimas Stock-Patterson model as presented in (Bertsimas and Patterson,1998), which has shown excellent computational performance to handle this type of problems. In a more recent study, Bertsimas et al. (2011b) introduced some new constraints that force local routing conditions sufficient to perform the rerouting function efficiently. However, compared with the method proposed in this paper, the rerouting decision was made in a more centralized way, which means that the concerned AUs would have to divert their flights to any possible routes specified by the NM. As discussed previously, such requests may not be favored by the AUs. One reason could be that the diverted trajectory is of low efficiency in terms of operating costs, as the NM typically lacks some proprietary information from AUs that is critical in trajectory planning. Recent studies (see (Liu et al.,2018) for instance) have been also devoted to capturing AUs’ trajectory choices based on historical data, so that the ATFM solutions will be able to propose alternative routes that are most likely to be accepted by specific AUs. This paper, in light of the principle of the TBO, allows (and encourages) AUs to resubmit alternative trajectories on their own decisions, through a collaborative process as introduced in Sec. 3. In other words, the AUs always compute the trajectories, starting from the BDT (nominal flight plan), down to the RBT. The NM does not compute trajectories, but chooses the “best” option in a system-wide optimization. This distributed decision-making framework is regarded as the main advance with respect to the previous work done in (Bertsimas et al.,2011b). 4.1. Problem statement In this paper we assume conventional airspace management, where the different ANSPs might change the configuration of the airspace according to 19 a finite list of different possible sectorisations (i.e. different ways to define collapsed sectors from the elementary sector list). These sectorisation changes might be done at given time intervals along the day (typically at every 20 or 60 minutes), producing the so called sector opening scheme. Typically, ANSPs might choose the best sector opening scheme that better matches the forecast traffic demand along the day, trying to avoid as much as possible sector overloads. Yet, some other operational considerations are taken into account, such as ATC staff availability, for instance. It is out of the scope of this paper to consider advanced solutions, such as the dynamic airspace configuration (DAC) concept currently explored by SESAR (Zelinski and Lai, 2011); or integrated solutions such as those proposed in (Xu et al.,2018). The different trajectory options and pre-tactical delay management preferences resulting from the collaboration process described in the previous section are integrated into a single optimization model, selecting eventually the best distribution of trajectory options and delay assignments. This means that for each flight there are Nffeasible combinations to solve the demand and capacity imbalance, with: Nf=Nt(2Nd−1) (1) where Ntrepresents the number of trajectory options submitted for flight f, and Ndis the number of pre-tactical delay management preferences that the AU envisages for the same flight. Nt≥1 since the nominal trajectory initially scheduled is always an option and Nd≥1 since ground holding must always be applicable. Then, depending on the AU, more or less trajectory or delay preferences might be submitted. It is worth noting that the −1 in Eq. (1) is needed to discard the combination where only delay recovery is performed (and no ATFM delay is assigned). The model is formulated as mixed integer linear programming (MILP), and the corresponding decision variables are defined below. Note that detailed notations of the formulation can be found in Appendix A. •Decision variables for trajectory options: wf k=(1,if trajectory kis chosen for flight f 0,otherwise •Decision variables for delay management: 20 xj k,t =(1,if trajectory kdeparts from position jby time t 0,otherwise yj k,t =(1,if trajectory karrives at position jby time t 0,otherwise Fig. 7presents the trajectory timeline versus designed positions (i.e., intersections with elementary sectors, along with origin and destination airports), where the four delay preferences are implemented. Note that an alternative trajectory implies a new set of intermediate designed positions (e.g., P-1, P-2 and P-3 in Fig. 7). Figure 7: Schema of trajectory timeline versus designed positions. Concretely, ground holding is experienced only at the origin airport; airborne holding can only be performed “at” a given position (the difference between the “departure” and “arrival” time at that position equals to the holding time); and since linear holding and delay recovery are realized by speed control, the slope of the lines is increased or decreased compared with the initially planned schedule. Recall that the typical airborne holding is distinguished from linear holding in Sec. 3.5 by the fact that when performing the former, the actual flight distance will be extended (either by vectoring or using holding patterns). 21 This flight path “stretching”, however, does not contribute to the execution of a trajectory defined by contiguous points. Thus, the typical airborne holding, on some level, can be seen as a “circling” at a particular position. It is also worth noting that the positions referred here may not correspond to the actual geographical (navigation) waypoints existing in current airspace. In addition, the feasible time window Tj kshown in Fig. 7defines a solution, based on the initially scheduled times of a particular trajectory, which will largely reduce the number of variables needed for the optimization. Finally, note that the “by” time is used, rather than “at” for the time domain, which would enable a faster solution searching process according to (Bertsimas and Patterson,1998), while the “at” time can be derived by (xj k,t −xj k,t−1) and (yj k,t −yj k,t−1) respectively. To enforce that only one time slot will be assigned to one trajectory at each designed position, within a prescribed feasible window Tj k, it has to satisfy Pt∈T j k(xj k,t −xj k,t−1) = 1 and Pt∈T j k(yj k,t −yj k,t−1) = 1. However, when using the “by” time, this constraint can be rewritten and fixed prior to solving the model, by means of setting xk,Tj k= 1, yk,Tj k= 1, and xk,Tj k−1= 0, yk,Tj k−1= 0, where Tj kand Tj kare respectively the lower and upper bound of the solution search window Tj k. 4.2. Objective function In light with the discussions in Sec. 3.1, the initially scheduled trajectory should represent the most preferred trajectory for a specific flight from the AUs’ point of view (i.e. individual optimum). In this way, if every single initial trajectory were maintained as it is in the final execution of flights, a global optimum at system level would be achieved, which is equal to the combination of all individual flight optima. Nevertheless, some regulations on those trajectories might be enforced due to certain reasons (e.g., a demand and capacity problem), meaning that not all the individual optima can be attained. The objective function used in the model presented in this paper, therefore, aims to minimize such deviations2, namely the extra fuel consumption, 2It is worth noting that for the reason of respecting the fairness principle, the objective function could be reformulated to minimize the maximum deviation of each flight, namely the Max-Min rule, in which no single flight can increase its benefits without reducing the benefits of other flights (Bertsimas et al.,2011a). 22 extra route charges, and the extra time related costs, between the initial trajectory and that trajectory resulted from the DCB process: min(C∆F+C∆R+C∆T) (2) The summed three items correspond to those considered for the scheduling of initial trajectories (recall Sec. 3.1), which in turn are treated as the baseline for computing the extra costs. Accordingly, the extra fuel consumption C∆Fis denoted as in Eq. 3. C∆F=X f∈F X k∈Kf αk(Fk−Ff 0)wf k(3) where Fkand Ff 0are respectively the total fuel consumed with trajectory k and with the initial trajectory of flight f. Note that k∈ Kf, where kis one of the trajectory options Kfsubmitted by flight f. In this case, if the initial trajectory is eventually selected, then the extra cost incurred from the fuel consumption for flight fwould be equal to zero. Similarly, the extra route charges C∆Rare computed by Eq. 4, where Rkand Rf 0are the total ATS fees charged with trajectory kand with the initial trajectory of flight f.αk and βkare respectively the weighting cost of fuel and route charges, which in turn could be specified on a trajectory basis. C∆R=X f∈F X k∈Kf βk(Rk−Rf 0)wf k(4) It should be noted that, due to practical reasons, the route charges are nowadays paid based on the GCD between the entry and exit positions within the (different) charging zones based on the planned (initially scheduled) trajectory. They are not re-charged for the added and/or reduced distances caused from tactically altering the trajectories (Delgado,2015). However, this may not reflect well the real air traffic services that they use. Therefore, aiming at future TBO concept of precise operations, this paper calculates the route charges, for each flight, using the absolute distances along the flown trajectory inside the charging zones according to the corresponding national unit rates3. Moreover, this is the most generic formulation of the model 3From 1 January 2020, Eurocontrol is now using the actual route flown as recorded by the NM to establish the distance factor used for the calculation of route charges. 23 presented in this paper and C∆Rcould always be set to zero if applying the current charging policy. Eq. (5) defines the time-related costs discussed in Sec. 3.5, which are composed of those incurred from the different types of delay, including ground holding GHk, air holding AHk(i.e., standard airborne holding and linear holding), and delay recovery DRk. It can be noticed from Eq. (5) that the cost weights (i.e., γg k,γa kand γd k) of each delay preferences could be trajectoryspecific4. C∆T=X f∈F X k∈Kf [γg kGHk+γa kAHk−γd kDRk] (5) Since delay recovery DRk=GHk+AHk−ADk, where ADkdenotes the arrival delay at the destination airport, Eq. (5) can be organized as follows: C∆T=X f∈F X k∈Kf [(γg k−γd k)GHk+ (γa k−γd k)AHk+γd kADk] (6) Specifically, depending on the holding positions, GHk,AHk, and ADkare formulated by the respective decision variables as depicted by Eqs. (7)-(9): GHk=X t∈T j k,j=Jk(i):i=1 (t−rj k)(xj k,t −xj k,t−1) (7) AHk=X t∈T j kX j∈Jk(i):1<i<nk t(xj k,t −xj k,t−1−yj k,t +yj k,t−1) (8) ADk=X t∈T j k,j=Jk(i):i=nk (t−rj k)1+(yj k,t −yj k,t−1) (9) Taking into account the fairness factor of delay assignment, the total delay is multiplied by a coefficient (t−rk f)1+(with slightly greater than 0) in Eq. (9), in such a way that the delays would be assigned moderately across all the flights (Bertsimas and Patterson,1998), instead of unevenly to one particular flight. 4For example, one particular trajectory might be given higher priority through setting a greater γd kenabling more delays to be recovered. However, this may raise issues of eventual unfair competition, such as gaming. How to prevent these issues is still under research and it is out of the scope of this paper. 24 4.3. Constraints The constraints concerned with the model are categorized into four groups, including aircraft operations, user-specified limits, network capacities, and decision variables. 4.3.1. Aircraft operations X k∈Kf wf k= 1 ∀f∈ F (10) xj k,Tj k−1=yj k,Tj k−1= 0 ∀f∈ F,∀k∈ Kf,∀j∈ Jk(11) xj k,Tj k =yj k,Tj k =wf k∀f∈ F,∀k∈ Kf,∀j∈ Jk(12) xj k,t −xj k,t−1, yj k,t −yj k,t−1≥0∀f∈ F,∀k∈ Kf,∀j∈ Jk,∀t∈ Tj k(13) xj k,t −yj k,t ≤0∀f∈ F,∀k∈ Kf,∀j∈ Jk,∀t∈ Tj k(14) Constraint (10) enforces that only one trajectory of all submitted options (including the initial and alternatives) is eventually selected for each flight. Constraints (11)-(12) guarantee that each selected trajectory k, (i.e., under the condition of wf k= 1, otherwise if wf k= 0 then all decision variables associated with the unselected trajectory are equal to 0), is assigned with only one time slot for departing and arriving respectively at position jwithin the prescribed time window Tj k. Constraints (13) ensures the timeline’s continuity, namely if an aircraft arrived/departed at time t−1 then it must have arrived/departed at time t. Constraint (14) specifies that the departure time is not earlier than the arrival time for any aircraft at any position. 4.3.2. User-specified limits yj0 k,t+uj,j0 kzj,j0 k−xj k,t ≤0∀f∈ F,∀k∈ Kf,∀i∈[1, nk−1] : j=Jk(i), j0=Jk(i+ 1),∀t∈ Tj k∩[Tj0 k−uj,j0 kzj,j0 k,Tj0 k−uj,j0 kzj,j0 k] (15) 25 •Case-0: the original model using all default parameter values given in experimental setup (see Sec. 5.1); •Case-1: Case-0 + setting superlinear factor to 0.2, to further take into account the non-linearity of delay cost for each flight; •Case-2: Case-1 + restricting the maximal delay quota of 10 min for each alternative trajectory, but 45 min (as default) for the initial trajectory; •Case-3: Case-2 + allowing only ground holding to be used as pretactical delay management initiative for the initial trajectory; and •Case-4: Case-3 + imposing a weighted cost 1 + (∆F+∆R) (F+R)on the delay assigned to alternative trajectory based on its extra and initial cost. For each case, the problem dimensions and computational times are summarized in Table 3. The mathematical formulation is based on the Bertsimas Stock-Patterson Model. In numerical experiments, GAMS v.25.1 software has been used as the modeling tool and Gurobi v.8.1 MIP optimizer as the solver. Computations have been run on a 64 bit Intel i7-8700 @ 3.20 GHz six-core CPU computer with 32 GB of RAM and Linux OS. Table 3: Problem size and computational time. Summary Case-0 Case-1 Case-2 Case-3 Case-4 Variables 4,943,940 4,943,940 3,665,250 3,665,250 3,665,250 Equations 11,343,818 11,343,818 8,334,973 7,064,986 7,064,986 Non-zeros 27,925,736 27,925,736 20,577,424 15,107,278 15,107,278 Generation 2 min 2 min 2 min 1 min 1 min Solution 138 min 99 min 62 min 14 min 9 min Objective 412,848 412,848 423,893 610,545 611,441 Rel. gap 0.28% 0.50% 0.42% 0.00% 0.00% Experimental results can be found in Table 4, which include key indicators encompassing delay assignment, trajectory selection, extra costs and equity. Across all these cases, the most promising result would be that the total (arrival) delay is reduced to only 3,000 - 4,500 min. Remember that when using C-ATFM with GH mode, this number is greater than 200,000 min (see Table 2), which means that the delay reduction (by using the C-ATFM full version) is nearly 98%. In the meantime, the total delay cost is reduced by 95% (due to the cost variance of using different delay initiatives), and the 32 average delay cost (per delayed flight) also decreases from almost 10,000 Euro (see Table 2) to less than 600 Euro. Table 4: Main indicators of the results derived from each case of study. Indicators Case-0 Case-1 Case-2 Case-3 Case-4 Total delay (min) 3,083 3,106 3,137 4,413 4,411 Delayed flight (a/c) 621 626 633 937 935 Avg. delay cost (Euro) 567 565 560 402 402 Original trajectory (a/c) 5,455 5,439 5,460 5,406 5,404 Alternative trajectory (a/c) 800 816 795 849 851 Avg. delay for original (min) 4.8 4.9 5.2 4.9 4.9 Avg. delay for altern. (min) 5.8 5.9 2.8 3.5 3.4 Extra fuel consumption (kg) 73,777 73,779 74,886 79,454 78,781 Extra route charges (Euro) 23,936 23,908 23,873 25,359 24,985 Extra trajectory cost (Euro) 60,825 60,798 61,316 65,086 64,376 Avg. extra cost per altern. (Euro) 76 75 77 77 76 Departure reversal pairs (#) 235 225 231 248 251 Arrival reversal pairs (#) 190 178 174 257 255 Next, such notable delay (and its cost) reduction is accompanied by approximately 800 flights diverted to their alternative trajectories. The extra trajectory costs (including fuel consumption and route charges) range between 60,000 - 65,000 Euro (in which the fuel cost is slightly higher than the charges of additional route), making the average extra cost per selected alternative trajectory close to 75 Euro. In other words, by means of diverting 800 flights (i.e., 13% of the total) incurring 75 Euro extra trajectory cost for each (see Table 4), the system delay will decrease by more than 200,000 minutes, producing a net income (i.e., delay cost reduction minus trajectory cost increase) of 16 million Euro in a system wide view5. This trade-off seems impressive, which will be further demonstrated in Sec. 5.7. In terms of fairness indicators, the numbers of flight reversal pairs are lowered down to 200 - 300 for both departure and arrival across all the cases (which is due to the absolute delay reductions), if compared with more than 15,000 in the GH mode (recall Table 2). Further, when allowing the airborne linear holding and delay recovery, part of the reversed flights in departure can be recovered till the arrival through speed changes en route. 5Note that the reason of issuing such a large amount of delay (in C-ATFM GH mode) is because all capacity constraints through the network have been strictly enforced (for illustrative purpose), which is not the real case in current operations. 33 Then, for different cases of study, Case-1 poses some non-linearity in the cost of delay, which yields more flights to be delayed and diverted with an increased (average) extra trajectory cost. The consequence is, however, a decrease in flight reversals (i.e., improved equity) as shown in Table 4. From Case-1 to Case-2, each alternative trajectory is given a quota of delay, namely 10 min maximal, and hence the average delay for the alternatives is reduced from 5.9 min to 2.8 min, compared with an increased number (from 4.9 min to 5.2 min) for the originals. This feature could be interpreted as one strong incentive for AUs to submit accurate alternative trajectories, as they can be guaranteed with no more than a slight delay. From Case-2 to Case-3 and Case-4, even less penalty is given to the flights having more potential extra costs, but in the meantime it largely increases delay (i.e., 40% more than that for Case-2). This means that some additional efficiency is lost for achieving a higher level of equity (and incentive). In this sense, Case-2 might be relatively a balanced method, and therefore is chosen as the way for conducting all the following experiments in this study. Summing up, this section discusses the concerns for AUs’ incentive and equity. These two factors are indeed the key aspects of mechanism design, which deserve a thorough assessment in future work. The main focus of this paper is limited to quantify the benefit pool of the framework that might be attained with an ideal system operating (in a deterministic setting). This ideal system would include an incentive compatible mechanism for eliciting the required inputs from AUs, and not be constrained by equity concerns. 5.5. Overall demand and capacity situations Fig. 9a presents firstly the initial (i.e., pre-regulation) demand for each considered operating sector during each time period. The total number of operating sectors across the day (72 periods of time) is 3,285, each of which is formed in a period of 20 min by either an elementary sector (164 in total) or a collapsed sector (224 in total). The sequence of these operating sectors has been ordered in accordance with their activation time in that day (but is arbitrary within each 20 min period). It can be also noticed that there are more sectors opened from 6 AM to 6 PM than the reverse, which is also roughly in line with the distribution of traffic occurrence. Seeing from Fig. 9b, large numbers of capacity overloads (i.e., demand higher than capacity) can be found, while in some cases it could be as high as twice the capacity value that the sector can provide. 34 500 1000 1500 2000 2500 3000 0 5 1 0 1 5 2 0 2 5 3 0 3 5 P r e r e g u l a t i o n d e m a n d ( a c / 2 0 m i n ) O p e r a t i n g s e c t o r s 1 8 P M1 2 A M 6 A M (a) Initial demand in operating sector 500 1000 1500 2000 2500 3000 - 2 0 - 1 5 - 1 0 - 5 0 5 1 0 1 5 2 0 O ve rlo a d U n d e rlo a d D i f f e r e n c e o f c a p a c i t y a n d d e m a n d O p e r a t i n g s e c t o r s (b) Imbalance of demand and capacity Figure 9: Initial traffic demand and imbalances with capacity for each operating sector during each time period. 0 500 1000 1500 2000 2500 3000 3500 0 . 0 0 . 5 1 . 0 1 . 5 2 . 0 2 . 5 R a t i o o f d e m a n d a n d c a p a c i t y S o r t e d o p e r a t i n g s e c t o r s I n i t i a l P o s t - r e g Figure 10: Sorted ratios of demand and capacity for initial and post-regulation situations. To better understand the balance between demand and capacity, their ratios are sorted (based on the initial demand) and presented in Fig. 10. Obviously, the curves representing pre-regulation (i.e., initial) are steeper with some parts growing higher than 1 (i.e., demand higher than capacity). Conversely, the curves turn to be level and average with respect to the postregulation cases, which means that more airspace capacities are well utilized. Note that Fig. 10 contains only data for the day of operation in 24 hours, 35 without showing a number of regulated flights having their arrival times delayed to the next day. In other words, the regulated demand (represented by the blue line) would be slightly lower than the initial demand (red line), where the gap is 695 (i.e., 27,601 - 26,906) entry counts (2.5% of the total) in this particular case study. 5.6. Trajectory selections and delay assignments As mentioned previously, any of the options proposed in Sec. 3.4 and Sec. 3.5 can be integrated together and imposed on one flight. For this particular case of study Nt= 3 (nominal trajectory plus lateral and vertical alternatives) and Nd= 4 (ground holding, airborne holding, linear holding and pre-tactical delay recovery), leading to 45 possible combinations (recall Eq. 1). For example, an aircraft might be asked to experience some ground holding at the origin airport, fly its lateral alternative trajectory, undertake a small amount of airborne or linear holding en route, whilst being allowed to partially recover those delays along the remaining trajectory. Table 5: Summary of trajectory selections and delay assignments* in C-ATFM. Options Initial Lateral Vertical Total (5,460 a/c) (530 a/c) (265 a/c) (6,255 a/c) Flight (a/c) Time (min) Flight (a/c) Time (min) Flight (a/c) Time (min) Flight (a/c) Time (min) GH 819 3,890 63 174 36 103 918 4,167 AH 24 161 2 3 1 3 27 167 LH 42 87 3 5 1 3 46 95 DR 619 -1,150 54 -100 25 -42 698 -1,292 AD 579 2,988 29 82 25 67 633 3,137 * GH-ground holding; AH-airborne holding; LH-linear holding; DR-delay recovery; AD-arrival delay In the previous case study, there are 795 flights selecting their alternatives, which contain 530 lateral hotspot-avoidance trajectories and another 265 vertical ones, as shown in Table 5. According to the cost results presented in Figs. 8c and 8d, the vertical alternatives generally incur less extra cost than the lateral, due to lower extra fuel consumption and no additional route charges. However, it turns out that more laterals than the verticals are eventually selected. This suggests that the lateral alternative trajectories should perform better in terms of redistributing the traffic flow across different operating sectors (with unoccupied capacities), even though they may require some more extra costs. 36 There also exists much less delay assigned with the alternatives than the initials, which is resulted from the quota setting (for incentive concern) as discussed in Sec. 5.4. Then, among the different delay preferences, ground holding is obviously the most-commonly used, absorbing almost all the required system delays, but it appears that a small amount of airborne holding (27 min) and linear holding (46 min) could contribute to minimizing the total cost even if their unit cost of 90 Euro/min is higher than the cost of ground holding (81 Euro/min). In terms of delay recovery, besides reducing the system cost explicitly, it also has some similar effects to air holding. For example, some available capacity (or free slot), which results from delaying a specific flight, might be taken over by another flight that is capable of advancing its arrival time at that place (through performing delay recovery), which is similar to an intermediate slot swapping process. 5.7. Trade-off of delay cost with extra fuel consumption and route charges Benefiting from the accurate avoidance information for individual flights (see Sec. 3.3), the alternative trajectory that is precisely re-designed by AUs may incur as little extra costs as possible (compared to the initially scheduled). The distributions of extra fuel consumption and extra route charges for all the submitted lateral (i.e., 1,305) and vertical (i.e., 1,379) alternative trajectories are presented in Figs. 8c and 8d. On the other side, Fig. 11 shows the case for the selected trajectories, in which the trade-off of such extra trajectory cost with respect to the delay cost reduction (with respect to the GH mode) is given for each flight. Among the set of submitted trajectories, there are some cases where a large amount of extra fuel consumption and/or route charges are needed (due to certain flights having multiple sectors to avoid for instance). Yet, it does not mean that these costly trajectories will be selected by the NM (based on the DCB model), as shown in Fig. 11 (in which only three flights are observed to incur an extra cost of higher than 1,000 Euro). Most costs, however, lie within an area of less than 300 Euro. Compared with this small amount of extra trajectory cost, the benefits gained from delay cost reduction is significant. Such advantage would be an explicit incentive that motivates AUs to use the proposed framework. Nevertheless, it can be noticed that a few flights somehow have negative (little though) net benefits (see Fig. 11), which also raises the necessity of taking into account more fairness concerns in future work. 37 0 300 600 900 1200 Extra fuel and route cost (Eur) 0 10000 20000 30000 40000 Delay cost reduction (Eur) 0 5000 10000 15000 20000 25000 30000 35000 Net benefit (Eur) Figure 11: Trade-off between delay cost reduction with respect to C-ATFM (GH mode) and cost incurred from extra fuel consumption and route charges for selecting alternative trajectories. 6. Conclusions This paper presented an innovative collaborative air traffic flow management framework in the scope of the future trajectory based operations. The main contribution of this paper is the integration of trajectory planning and air traffic flow management, as well as their interactive processes (i.e., collaborative trajectory design including hotspot detection and avoidance), into a single framework, and also the application to a real-world scale problem. The key finding of the paper is to quantify the benefit pool that might be attained with such framework operating in a deterministic setting. The interactive trajectory design process (between airspace users and the Network Manager) was regarded as the key enabler of the framework for a series of downstream performance enhancements. Specifically, the accurate provision of the identified time-varying hotspot airspaces contributed to assisting airspace users to schedule alternative trajectories with as few extra costs as possible. Combining different options, resulted from the collaborative process, to manage the imbalances of demand and capacity could improve the cost-efficiency of air traffic flow management. The linear optimization model, taking fully advantage of the trajectory design solutions, incorporated potential traffic management initiatives (i.e., 38 multiple trajectory options mixed with different pre-tactical delay management preferences) to balance the traffic demand with airspace capacity, trying to minimize the deviation to the initial set of user-preferred trajectories. Results showed that, by implementing the proposed framework, a significant delay reduction was achieved with only a relatively small amount of extra costs (including fuel consumption and route charges) incurred. Nevertheless, the achieved results represent an upper bound of the potential gains that the framework can provide, which will largely depend on the level of uncertainty in the system. A follow-up work will be conducted to further assess such impacts by adapting to the stochastic models proposed in the appendix. In addition to the analysis of the equity metrics, a more mature mechanism should be addressed to better balance the efficiency and equity. The computational performance will be also under future research towards an operational decision-support tool. Acknowledgment The work presented in this paper was partially funded by grants from the Funds of China Scholarship Council (No. 201506830050) and by the SESAR Joint Undertaking under grant agreement No. 699338, as part of the European Unions Horizon 2020 research and innovation programme: APACHE project (Assessment of Performance in current ATM operations and of new Concepts of operations for its Holistic Enhancement - http:// apache-sesar.barcelonatech-upc.eu/en). The opinions expressed herein reflect the authors view only. Under no circumstances shall the SESAR Joint Undertaking be responsible for any use that may be made of the information contained herein. The authors would like to thank Dr. Christina Barado at UPC for generating the experimental results with the CASA algorithm. The authors appreciate the reviewers and the editor for all their valuable comments and suggestions. 39 Appendix A Notations Acronym: AD Arrival Delay AH Airborne Holding ATC Air Traffic Control ATFM Air Traffic Flow Management ATM Air Traffic Management ATS Air Traffic Service AUs Airspace Users CASA Computer Assisted Slot Allocation C-ATFM Collaborative Air Traffic Flow Management CDM Collaborative Decision-Making CTA Controlled Time of Arrival CTD Controlled Time of Departure CTO Controlled Time Over DCB Demand and Capacity Balancing DDR2 Demand Data Repository v2 DR Delay Recovery ETA Estimated Time of Arrival ETD Estimated Time of Departure ETO Estimated Time Over GCD Great Circle Distance GH Ground Holding LH Linear Holding NM Network Manager O/D Origin and Destination RBS Ration-by-Schedule SR Structured Route TBO Trajectory Based Operations Nomenclature: f∈ F set of flights k∈ K set of trajectories j∈ J set of control points t∈ T set of time moments l∈ L set of operating sectors 40 τ∈Tset of time periods ξ∈Ξ set of scenarios s∈ S set of stages Kfsubset of trajectory options of flight f Tj ksubset of feasible time window for trajectory kat position j Lτsubset of operating sectors that are open in time period τ Jasubset of airports Jτ lsubset of elementary sectors collapsing to operating sector l during time period τ Jksubset of control points that trajectory ktraverses Jk(i)     departure airport, if i= 1 arrival airport, if i=nk intermediate designed positions, if 1 < i < nk T(τ) subset of time moments subject to time period τ Tssubset of time moments subject to stage s Sξsubset of stages subject to scenario ξ Fssubset of flights initially scheduled to depart within stage s Ntnumber of trajectory options submitted for flight f Ndnumber of pre-tactical delay preferences submitted for flight f Nfnumber of possible alternatives for flgiht fto solve the DCB problem rj kinitially scheduled time of trajectory kat position j Tj klower bound of the feasible time window Tj k Tj kupper bound of the feasible time window Tj k Fkfuel consumption of trajectory k Ff 0initially scheduled fuel consumption for flight f Rkroute charges of trajectory k Rf 0initially scheduled route charges for flight f ξn snth scenario ξthat may occur at the end of stage s zj,j0 kscheduled segment flight time of two contiguous positions jand j0 uj,j0 ktime bound of delay recovery within flight segment (j, j0) vj,j0 ktime bound of linear holding within flight segment (j, j0) S(k, l, τ) the first entered elementary sector for trajectory kamong those collapsed into operating sector lduring time period τ CD j(τ) airport departure capacity during time period τ CA j(τ) airport arrival capacity during time period τ Cl(τ) capacity of operating sector lduring time period τ αkweighting cost of extra fuel consumption for trajectory k βkweighting cost of extra route charges for trajectory k 41 Ball, M. O., Hoffman, R., Odoni, A. R., Rifkin, R., 2003. A stochastic integer program with dual network structure and its application to the groundholding problem. Operations research 51 (1), 167–171. Ball, M. O., Hoffman, R. L., Knorr, D., 2000. Assessing the benefits of collaborative decision making in air traffic management. In: Proceedings of the 3rd USA/Europe ATM R&D Seminar. Napoli, Italy. Barnhart, C., Bertsimas, D., Caramanis, C., Fearing, D., 2012. Equitable and efficient coordination in traffic flow management. Transportation science 46 (2), 262–280. Bertsimas, D., Farias, V. F., Trichakis, N., 2011a. The price of fairness. Operations research 59 (1), 17–31. Bertsimas, D., Gupta, S., 2015. Fairness and collaboration in network air traffic flow management: an optimization approach. Transportation Science 50 (1), 57–76. Bertsimas, D., Lulli, G., Odoni, A., 2011b. An integer optimization approach to large-scale air traffic flow management. Operations research 59 (1), 211– 227. Bertsimas, D., Patterson, S. S., 1998. The air traffic flow management problem with enroute capacities. Operations research 46 (3), 406–422. Bertsimas, D., Patterson, S. S., 2000. The traffic flow management rerouting problem in air traffic control: A dynamic network flow approach. Transportation Science 34 (3), 239–255. Betts, J., 2010. Practical Methods for Optimal Control and Estimation Using Nonlinear Programming, 2nd Edition. Society for Industrial and Applied Mathematics. URL https://epubs.siam.org/doi/abs/10.1137/1.9780898718577 Betts, J. T., Cramer, E. J., 1995. Application of direct transcription to commercial aircraft trajectory optimization. Journal of Guidance, Control, and Dynamics 18 (1), 151–159. Boli´c, T., Castelli, L., Corolli, L., Rigonat, D., 2017. Reducing atfm delays through strategic flight planning. Transportation Research Part E: Logistics and Transportation Review 98, 42–59. 48 Chang, K., Howard, K., Oiesen, R., Shisler, L., Tanino, M., Wambsganss, M. C., 2001. Enhancements to the FAA ground-delay program under collaborative decision making. Interfaces 31 (1), 57–76. Cook, A., 2007. European air traffic management: principles, practice, and research. Ashgate Publishing, Ltd. Cook, A. J., Tanner, G., 2015. European airline delay cost reference values: Updated and extended values. Tech. rep. Dalmau, R., Melgosa, M., Vilardaga, S., Prats, X., 2018. A fast and flexible aircraft trajectory predictor and optimiser for atm research applications. In: Proceedings of the 8th International Conference for Research in Air Transportation (ICRAT). Castelldefels, Spain. Dalmau, R., Prats, X., 2017. Assessing the impact of relaxing cruise operations with a reduction of the minimum rate of climb and/or step climb heights. Aerospace Science and Technology 70, 461–470. Delgado, L., 2015. European route choice determinants. In: Proceedings of the 11th USA/Europe ATM R&D Seminar. Lisbon, Portugal. EUROCONTROL, 2017a. All-causes delay and cancellations to air transport in Europe. Tech. Rep. CODA Digest 2016, CDA-2017-005, Network Manager. EUROCONTROL, 2017b. ATFCM operations manual - network operations handbook. Tech. Rep. Ed. 21.0. EUROCONTROL, 2018. DDR2 reference manual for general users. Tech. Rep. Version 2.9.5. FAA, 2009. Traffic Flow Management in the National Airspace System. Tech. Rep. FAA-2009-AJN-251, Federal Aviation Administration. FAA, 2014. Collaborative Trajectory Options Program (CTOP): Document Information. Tech. Rep. AC 90-115, Federal Aviation Administration. FAA, 2018. Nextgen implementation plan. Tech. Rep. 2018-2019 Edition. 49 Gardi, A., Sabatini, R., Ramasamy, S., 2016. Multi-objective optimisation of aircraft flight trajectories in the ATM and avionics context. Progress in Aerospace Sciences 83, 1–36. Hart, P. E., Nilsson, N. J., Raphael, B., 1968. A formal basis for the heuristic determination of minimum cost paths. IEEE transactions on Systems Science and Cybernetics 4 (2), 100–107. Holloway, S., 2008. Straight and level: Practical airline economics. Ashgate Publishing, Ltd. ICAO, 2016. Global air navigation plan (2016-2030), Doc 9750-an/963, fifth edition. Tech. rep. Kim, A., Hansen, M., 2015. Some insights into a sequential resource allocation mechanism for en route air traffic management. Transportation Research Part B: Methodological 79, 1–15. Libby, M., Buckner, J., Brennan, M., 2005. Operational concept for Airspace Flow Programs (AFP). Tech. rep., FAA Air Traffic Organization, Systems Operations Services. Liu, Y., Hansen, M., Lovell, D., Ball, M., 2018. Predicting aircraft trajectory choice - a nominal route approach. In: Proceedings of the 8th International Conference for Research in Air Transportation (ICRAT). Castelldefels, Spain. Lulli, G., Odoni, A., 2007. The European air traffic flow management problem. Transportation Science 41 (4), 431–443. Meyer, J. R., Oster, C. V., 1981. Airline deregulation: the early experience. Auburn House. Miller, M. E., Hall, W. D., 2015. Collaborative trajectory option program demonstration. In: Proceedings of the 34th IEEE/AIAA Digital Avionics Systems Conference (DASC). IEEE, Prague, Czech Republic, pp. 1C1–8. Molina, M., Carrasco, S., Martin, J., 2014. Agent-based modeling and simulation for the design of the future european air traffic management system: the experience of cassiopeia. In: International Conference on Practical Applications of Agents and Multi-Agent Systems. Springer, pp. 22–33. 50 Morrison, S., Winston, C., 2010. The economic effects of airline deregulation. Brookings Institution Press. Mukherjee, A., Hansen, M., 2009. A dynamic rerouting model for air traffic flow management. Transportation Research Part B: Methodological 43 (1), 159–171. Nuic, A., Mouillet, V., 2014. User Manual for the Base of Aircraft Data (BADA) Family 4, EEC Technical/Scientific Report. Eurocontrol Experimental Centre, Bretigny-sur-Orge, France. Odoni, A. R., 1987. The flow management problem in air traffic control. In: Flow control of congested networks. Springer, Berlin, Heidelberg, pp. 269–288. Pourtaklo, N. V., Ball, M., 2009. Equitable allocation of enroute airspace resources. In: Proceedings of the 8th USA/Europe ATM R&D Seminar. Napa, CA, US. Richetta, O., Odoni, A. R., 1994. Dynamic solution to the ground-holding problem in air traffic control. Transportation research part A: Policy and practice 28 (3), 167–185. Rios, J., Ross, K., 2010. Massively parallel Dantzig-Wolfe decomposition applied to traffic flow scheduling. Journal of Aerospace Computing, Information, and Communication 7 (1), 32–45. Rodionova, O., Arneson, H., Sridhar, B., Evans, A., Sept 2017. Efficient trajectory options allocation for the ollaborative trajectory options program. In: Proceedings of the 36th IEEE/AIAA Digital Avionics Systems Conference (DASC). St. Petersburg, FL, US, pp. 1–10. SESAR, 2015. Step 1 v3 UDPP validation report, optimised airspace user operations. Tech. Rep. PJ07.06.02, SESAR JU. SESAR, 2017. SESAR 2020 concept of operations edition 2017. Tech. Rep. PJ.19-02. SESAR, 2020. European ATM master plan. Tech. Rep. 2020 Edition. 51 Sherali, H. D., Hill, J. M., McCrea, M. V., Trani, A. A., 2011. Integrating slot exchange, safety, capacity, and equity mechanisms within an airspace flow program. Transportation science 45 (2), 271–284. Soler, M., Olivares, A., Staffetti, E., Zapata, D., 2012. Framework for aircraft trajectory planning toward an efficient air traffic management. Journal of Aircraft 49 (1), 341–348. Tandale, M. D., Wiraatmadja, S., Vaddi, V. V., Rios, J. L., 2013. Massively parallel optimal solution to the nationwide traffic flow management problem. In: 2013 Aviation Technology, Integration, and Operations Conference. Los Angeles, CA, US, p. 4349. Terrab, M., Paulose, S., 1992. Dynamic strategic and tactical air traffic flow control. In: IEEE International Conference on Systems, Man and Cybernetics. IEEE, Chicago, US, pp. 243–248. US Department of Transportation, 2016. Airline on-time statistics. Tech. rep. URL https://www.transtats.bts.gov/ Vossen, T., Ball, M., 2006a. Optimization and mediated bartering models for ground delay programs. Naval Research Logistics (NRL) 53 (1), 75–90. Vossen, T. W., Ball, M. O., 2006b. Slot trading opportunities in collaborative ground delay programs. Transportation Science 40 (1), 29–43. Vossen, T. W. M., Hoffman, R., Mukherjee, A., 2012. Air Traffic Flow Management. Springer US, Boston, MA, pp. 385–453. World Meteorological Organization, 1994. A guide to the code form fm 92-ix ext. GRIB. Edition 1. Xiong, J., Hansen, M., 2009. Value of flight cancellation and cancellation decision modeling: ground delay program postoperation study. Transportation Research Record: Journal of the Transportation Research Board (2106), 83–89. Xu, Y., Dalmau, R., Prats, X., 2017. Maximizing airborne delay at no extra fuel cost by means of linear holding. Transportation Research Part C: Emerging Technologies 81, 137–152. 52 Xu, Y., Prats, X., 2017a. Effects of linear holding for reducing additional flight delays without extra fuel consumption. Transportation Research Part D: Transport and Environment 53, 388–397. Xu, Y., Prats, X., 2017b. Including linear holding in air traffic flow management for flexible delay handling. Journal of Air Transportation 25, 123–137. Xu, Y., Prats, X., Delahaye, D., 2018. Synchronization of traffic flow and sector opening for collaborative demand and capacity balancing. In: 37th IEEE/AIAA Digital Avionics Systems Conference (DASC). IEEE, London, UK. Yang, Y., 2017. Practical method for 4-dimentional strategic air traffic management problem with convective weather uncertainty. IEEE Transactions on Intelligent Transportation Systems 19 (6), 1697–1708. Zelinski, S., Lai, C. F., 2011. Comparing methods for dynamic airspace configuration. In: Proceedings of the 30th IEEE/AIAA Digital Avionics Systems Conference (DASC). IEEE, Seattle, WA, US, pp. 3A1–1. 53