1. Introduction

In the realm of Air Traffic Flow Management (ATFM) and operations planning, EUROCONTROL's Group Rerouting Tool (GRRT) [1] is instrumental in providing alternative routing options for users, particularly Aircraft Operators (AOs), to optimize flight planning and address inefficiencies. This study delves into assessing the efficacy of a 2D flight route matching algorithm for post-operational analysis within the GRRT framework, ensuring comparability with the established 4D algorithm. By enabling strategic and tactical analyses of GRRT proposals by AOs, this research contributes to the continuous refinement of GRRT within EUROCONTROL's Enhanced Tactical Flow Management System (ETFMS) [2].

The GRRT system currently utilizes a 4D trajectory-based algorithm for proposal matching, incorporating three spatial dimensions plus time. In contrast, a 2D trajectory is akin to a bird's eye view of the 4D trajectory, lacking information on flight level (FL) and speed. This poses challenges for flight efficiency and post-ops analysis, necessitating a solution to leverage flight route information for subsequent analysis.

Based on the expertise and past experience of EUROCONTROL experts who use the tool, it is observed that limitations arise in examining the current 4D matching algorithm from a flight efficiency strategic analysis standpoint. These limitations are attributed to its conservatism in matching, constrained by specific tolerances in flight level and geographic position. This conservatism restricts its suitability for post-operational analysis.

The subsequent research questions address the need for simplifying the flight reroute proposal matching process while maintaining or improving accuracy and efficiency, identifying limitations of the current 4D algorithm and proposing solutions, incorporating flight reroute proposal acceptance analysis into the matching process for AO insights, and assessing the potential knowledge enhancement from the new approach for flight reroute proposal matching.

The most important take-off from the conducted literature review is that the flight trajectories in 4D can be downscaled to 2D trajectories [3]. Moreover, as discussed in [4], rerouting trajectories necessitates incorporating new waypoints, establishing a criterion where two trajectories are deemed identical only if they traverse the same set of waypoints. This makes the matching waypoints in the flight plan similar to algorithms for alignment of strings used in bioinformatics [5,6,7]. A large-scale database is required for conducting the analysis, and to fulfill this need, the Basic Local Alignment Searching Tool (BLAST) [8] serves as a concept for storing and comparing flight plans. Leveraging the available data, flight plans are identified and compared to yield results for both tactical and operational analyses under the guidelines of [9].

2. Literature Review

In [10], the author delves into the application of 3D perspective views on flat screens for situational awareness tasks, shedding light on the nuances of human-machine interaction between 2D and 3D perspectives in aviation. While the paper provides an initial grasp of the disparities between the two, it emphasizes the preference for 2D perspective views due to their effectiveness in displaying key points outlined in the flight plan. Additionally, [3] defines a flight trajectory in 2D space as a function of waypoints (1).

(1)

By taking into account this formula, a 4D flight trajectory can be represented as an ordered set of waypoints by eliminating the altitude and time.

Optimizing flights in the European airspace remains a challenging endeavor. In [4], the researchers aim to develop a conflict-free 4D trajectory planning methodology, akin to the ETFMS, at a continental level with 30 thousand flights. The proposed algorithm, designed to address the challenges posed by various external factors, relaxes 4D trajectory constraints by generating alternative trajectories through different waypoints. The study highlights that two flight paths are considered different if they do not pass through the same waypoints. The scalability of transitioning between a 4D and 2D trajectory is noted as feasible, as discussed in [4,11], while maintaining reference to the same set of waypoints.

In the sphere of distance-based trajectories, the literature [12,13,14,15,16] primarily emphasizes 2D trajectory clustering due to limitations in datasets containing 3D or 4D flight trajectories Notably, [12] focuses on clustering aviation routes to gain insights into waypoint usage. However, as this research has direct access to flight plans containing waypoints, trajectory clustering is circumvented for initial post-operational analysis. Clustering methods discussed in [13,14,15] hold potential for adaptation in aviation, especially for matching flight paths given the similarity between road networks and airway systems. However, the accuracy depends on the precision of the devices that track the objects, GPS or radars in aviation.

Instead of using turning points to identify waypoints, the study [17] utilizes the intersection of trajectories to define waypoints and construct the route network. Similarly, in the domain of ship navigation, as indicated in [18], major waypoints are determined through clustering, and subsequently, the route network is established.

To match trajectories with published procedures, a 2D algorithm proves more suitable [4,11], considering flight plans are based on predefined waypoints. The review of trajectory clustering papers [12,13,14,15,16,17,18] highlights the challenge of comparing planned routes with actual trajectories deviating from the flight plan. Ignoring the vertical dimension in shared flight routes allows for the application of methods with better accuracy when comparing two flight plans, enabling the identification of routes passing through an ordered set of points. While the clustering algorithms strive to identify the exact waypoints and generate the initial flight plan, the data used in this research is fortunate to already include the initial flight plans.

Considering the content in field 15 of a flight plan, the task involves seeking similarities between strings, a concept extensively used in DNA alignment in biology [5]. Drawing inspiration from biological data, the approach is adapted to align waypoints in flight plans, mirroring the alignment of DNA codons. The ability to quantify matches, mismatches, and gaps aids in comparing two flight plans. Employing a scoring matrix [6], one can penalize or reward routes with missing points, and. Additionally, taking inspiration from [7], they can calculate the distance between different flight plans. However, equidistance requirements limit the latter method's applicability, necessitating waypoint encoding for algorithmic comprehension which augments the complexity.

Inspired by BLAST [8] in bioinformatics, a proposal is made to build a comprehensive flight plan database. This entails capturing waypoint sequence relevance and developing an algorithm for identifying matches and similarities. Challenges include unique characteristics of flight plan data and the need for adaptations due to differences in data structure and semantics compared to biological sequences.

Various Longest Common Subsequence (LCS) algorithms [19,20] differ in behaviors and applications. Given the expected few differences in flight routes on the same city-pair, faster algorithms are preferred [21]. This paper employs the edit graph logic from [5,6], resulting in an O(ND) time LCS algorithm with small D, making it suitable for flight matching. While LCS yields identity percentages, its applicability is challenged by the need for a strict and complete exact match in the research.

The LCS, commonly used in differential file comparison [22], inspires its application in flight plan matching. Adapting this logic helps identify changes, differences, and similarities between different versions of flight plans, particularly in analyzing segments proposed in flight reroute proposals against initial flight plans.

In [9], a comprehensive exploration of techniques and challenges in analyzing large-scale movement datasets is presented. It is of outmost importance to create a foundation for the post-ops analysis of the flight plan datasets. The cited paper explains the importance of exploring patterns within the set of extracted trajectories and events. This will be done through the data analysis for both strategic and tactical analysis of the proposals. On the other hand, it explains the importance on identifying trajectories which are needed in order to do effective analysis for large-scale datasets.

The study's immediate focus remains on straightforward string-to-string comparison, with potential implications for uncovering routing patterns, detecting deviations, and optimizing route planning-a foundation for future tasks.

3. Flight Plan and Reroute Opportunities

The primary goal of optimizing route network utilization is to minimize delays, improve flight paths, and efficiently use available airspace, benefiting both airlines and aviation authorities. The GRRT, integrated into the ETFMS, plays a crucial role in achieving these objectives. By recalculating flight routes based on predetermined criteria, the GRRT aims to convert diverse cost factors into a standardized unit, generating a total cost for each route. The ETFMS provides default weights for criteria like delay, flying time, route length, suspension, overload, fuel cost, etc., allowing for flexible adjustments. This systematic approach enhances overall air transportation efficiency, promoting cost-effectiveness and operational smoothness for the benefit of passengers and industry stakeholders.

The data is taken from the EUROCONTROL’s data warehouse. It contains operations log messages as well as environment data such as routes, segments and waypoints.

To facilitate the analysis of flight plans and rerouting opportunities, the implementation of an Extract, Transform, Load (ETL) pipeline is imperative for retrieving messages generated by the ETFMS. These messages, crucial for comprehensive analysis, include different event types, each containing essential information found in field 15. Initial flight plans are submitted in the form of Filed Flight Plan (FPL) messages, with the flexibility for modification through Change or Modification (CHG) messages. Of paramount significance is the “REROUTE” message, encapsulating all identified routes deemed as potential candidates. Each “REROUTE” message is categorized as either “INTERESTING” or “UNINTERESTING”, with the former proposing a more optimal route based on specified parameters. The analysis focuses solely on “REROUTE” messages marked as “INTERESTING”. Additionally, the system generates “REROUTE MATCHING” messages whenever it identifies that a flight plan from an AO was proposed by the system for a given flight. These messages furnish statistical information on both the latest and proposed flight plans, alongside details about the corresponding route identifier, enriching the analytical scope.

4. Post-Operational Analysis

In the context of Air Traffic Flow Management, EUROCONTROL has observed that AOs often rely on internal, historic city-pair-based routes stored in their catalogues, rather than actively seeking optimized routes. This practice can lead to missed opportunities for more efficient routes dynamically available in the network after filing the flight plan. The GRRT addresses this challenge by providing timely information on new route proposals. Both tactical and strategic analyses are conducted to understand the effectiveness of these proposed routes for concurrent and future applications. The GRRT proves valuable in enhancing airline flexibility for optimal route selection in response to evolving traffic patterns and the availability of more efficient routes. This research explores the extent to which AOs adopt newly suggested routes for future flights, emphasizing the significance of the GRRT in supporting airlines' operational needs.

5. Field 15 Parser

The development of a Python script and SQL query are crucial for accurately parsing field 15 in the flight plan, enabling the extraction of essential information and generating a list of waypoints to determine the intended sequence of points for the aircraft's flight. It employs a parsing mechanism for field 15, involving the segmentation of the string into a list, subsequent application of predefined regex rules to each element, and the enumeration of types based on established patterns. To ensure accuracy and reliability, regex patterns were designed and utilized for labelling types within the field 15 string. It is of outmost importance the usage of quality aviation environment data in order to have the best accuracy when parsing and transforming the field 15.

After identifying elements in the flight plan, non-2D trajectory characteristics such as initial speed, cruise altitude, and SID/STAR are removed. Manual constraints are applied to handle differences in naming points and routes, especially for flights from North America. A careful check ensures that the first value after removing non-point or route types is indeed a point. Routes are expanded to include points within them, considering the order of segments. The resulting ordered list of points provides the planned route with the lowest granularity. The process ensures accuracy in extracting hidden points under route elements, yielding a precise representation of the flight plan's route.

The parsing can be visualized using different colours to showcase the steps noted in the previous paragraph:

1. Identifying the types of each element in field 15:

2. Removing the non-2D trajectory characteristics:

3. Expanding the routes to get the intermediate waypoints, in this example it’s the NANCY and JARNY waypoints:

4. Obtaining the final parsed field 15:

In Figure 1, an illustrative example is provided for visual comparison, showcasing the heightened granularity achieved in the final route through a comparison between the initial field 15 and the parsed route output.

Figure 1. Granularity comparison of initial field 15 (left) and parsed field 15 (right) of a flight

6. Matching Methodology

The current ETFMS features functionality to analyse updates in flight plan messages (“FPL”, “CHG”) following the proposal of a route opportunity message (“REROUTE”). After generating route proposals, the REROUTE message is dispatched. The AO can either store these proposals locally or modify the flight plan by filing the field 15 with the proposed GRRT route. The GRRT triggers a “REROUTE MATCHING” message when it detects that a new flight plan modification (“FPL”/ “CHG”) exactly matches one of the reroute proposals (“REROUTE”) sent by GRRT.

6.1. GRRT Approach

The matching algorithm uses the 4D trajectory of the flight. It compares the flights in FPL and CHG with the REROUTE messages. An approximate match means that two 4D trajectories of flights have the same trajectory within a certain deviation in flight level, time tolerance and geographic positioning.

While the 4D algorithm is designed to support various ETFMS mechanisms, including slot reservation post-reroute proposal, its conservative nature limits its suitability for GRRT and post-ops analysis. This arises from the potential for AOs to refile flight plans with altered time, speed, and levels after receiving a proposal from GRRT while maintaining the newly communicated routing option. Such variations can impede trajectory matches, given the algorithm's reliance on geographic and flight level tolerances. For instance, a proposed route on FL320 may face restrictions due to pre-tactical changes, prompting the AO to refile with FL380, resulting in a non-match. Daily operational adjustments by AOs in flight levels can further challenge 4D matches, especially if the deviation from the proposed route is significant. Additionally, the 4D algorithm is not continuously employed for route visualization but is selectively applied at the tactical stage.

6.2. Matching Algorithm

In the literature review, the preference for a two-dimensional algorithm in processing flight plans is identified, emphasizing its reliance on predefined geographic waypoints. This approach facilitates the identification of routes, laying the groundwork for strategic and tactical analyses of proposals. The dataset containing the field 15 and the type of oplog message was created using the ETL. The data was ingested in a database so that it can be efficiently queried. The subsequent parsing of field 15 messages, yields a version containing only the planned waypoints for each flight. Simplifying the storage process, a hash is generated for each parsed route, ensuring unique identification through a consistent MD5 hash value. Python’s “hashlib” library is employed for creating the MD5 hash, encoded using UTF-8 and converted to a hexadecimal string. This hashed value serves as a stable and unchanging route ID, offering a straightforward and effective means for subsequent analysis.

6.2.1. Tactical Analysis

To determine matches, the algorithm compares the route ID in each “REROUTE” message with the one in the preceding “CHG” message. If any match occurs, the flight is considered "matched." The algorithm processes all flights in the dataset, enabling a comprehensive view of proposed routes and their efficiency. Even if the order of “CHG” messages is altered, a match persists if the route ID aligns with any preceding “REROUTE” message. This flexibility accommodates instances where operational changes may affect flight plans. An example is observed in Table 1, demonstrating a match with the “REROUTE” message 2 and “CHG” message.

Table 1. Sequence of oplog messages in one flight

Applying this algorithm to the entire dataset reveals the number of matches detected by the 2D approach. Additionally, a comparison with the count of “REROUTE MATCHING” messages provides insights into matches facilitated by the GRRT system.

6.2.2. Route Catalogue

For the analysis of reroute proposal adoption, the hash values of parsed routes, referred to as route IDs, are utilized. The rule for determining the uptake of routes is defined as follows: a route is considered used only when encountered in a “REROUTE” message before its appearance in an “FPL” or “CHG” message. This process is swift as it utilizes a dictionary, taking O(1) to check if the “ROUTE_ID” is present for a specific city-pair. Once this catalogue is established, containing the initial occurrences of routes per city-pair and message type, adopted flights can be identified by traversing the data catalogue and comparing the timing of “REROUTE” and “FPL”/ “CHG” messages. With a runtime of less than 1 second for a full AIRAC and one AO, this algorithm proves efficient for creating the necessary structure.

6.2.3. Segment Catalogue

For a comprehensive analysis of the adoption of proposed segments by AOs, it is imperative to identify the new segments introduced in each “REROUTE” message. AOs might not use the entire route but only specific segments, leading to an incremental approach in testing and implementing routes for improved efficiency. To address this, an algorithm needs to be created for identifying these new segments. Using the algorithm proposed in [6], which identifies differences between the two strings, an example of a set of waypoints from a flight plan is demonstrated. The example waypoints are derived from flight plans:

- NEPIX, RUBSI, AXUTI, BODRI, GURLI, TUSKA, LEGPI, CORIS, NIRDU, JUIST, TEMLU, EEL

- NEPIX, RUBSI, EKMIK, ROGED, NIROD, KUGAL, EEL

Once the algorithm is applied, the unique additions from the target string are marked with " + ", segments that are removed from the source string are marked with "−", and those appearing in both strings are left blank. From this string, the segments starting with " + " are filtered to obtain the desired segments.

[' NEPIX-RUBSI', '+ RUBSI-EKMIK', '+EKMIK-ROGED', '+ ROGED-NIROD', '+ NIROD-KUGAL', '+ KUGAL-EEL', '- RUBSI-AXUTI', '- AXUTI-BODRI', '- BODRI-GURLI', '- GURLI-TUSKA', '- TUSKA-LEGPI', '- LEGPI-CORIS', '- CORIS-NIRDU', '- NIRDU-JUIST', '- JUIST-TEMLU', '- TEMLU-EEL']

Only the entries containing " + " are selected in the process:

[('RUBSI', 'EKMIK'), ('EKMIK', 'ROGED'), ('ROGED', 'NIROD'), ('NIROD', 'KUGAL'), ('KUGAL', 'EEL')]

Once the segments are generated, each row is traversed, and segment by segment, a catalogue of first occurrences of those segments per city-pair and message type is created. Similar to the routes, the data catalogue is then traversed to compare if the segments from the REROUTE message were introduced before the FPL/CHG message.

7. Results and Findings

For this work, the outcomes were tested using AIRAC 501, 502, and 503 cycles (around 3 continuous months of data) from two distinct AOs, which will be anonymized. The results are presented in Table 2. The three AIRACs were since they were actual during the time this thesis was written. AO1 was chosen randomly, while AO2 has been handpicked because the aviation experts from AO2 are aware of GRRT and occasionally use it for their operations. Therefore, an anticipation of more matches from AO2 can be made.

Table 2. Comparison of flight matching results for different AIRACs and AOs

From Table 2, both AOs have a similar number of flights, but AO1 is receiving almost double the amount of REROUTE messages and has a slightly higher number of 'unique flights with reroute proposals.' As mentioned in the introduction, AO1 has a 'match-to-message ratio' of around 2%, while AO2 has around 20%, confirming the hypothesis that AO2 is matching more flights proposed by the GRRT. It is also observed that, for AO2 in AIRAC 503, there is a substantial number of exclusive matches identified by the algorithm. The direct cause is unknown. One possible reason could be that the system passed to another version during AIRAC 503.

Table 3. Comparison of different ratios

From Table 3, it is observed that the algorithm successfully covers almost 100% of the flights. Despite adapting the algorithm for both tactical and strategic analysis, the achieved results are nearly identical to the 4D matching by GRRT. Of particular interest are the "outliers" exclusively matched by each algorithm. These outliers are mostly due to different naming of waypoints outside of the NM area and encoding of some flight plans that use the North Atlantic Tracks.

8. Future Work

The biggest bottleneck when performing the analysis is the speed by which the data is being queried from the main data warehouse. To fully complete the ETL pipeline, the data can be loaded to an OLAP database which will be incrementally filled by scheduled SQL queries. This way aviation experts can have their analysis ready in seconds.

Further improvement can be made on the data quality. Correct aviation environment data is needed in order for the field 15 parser to work and the subpoints in the field 15 to be extracted.

Limiting the analysis to a specific region, such as the airspace managed by EUROCONTROL, helps in avoiding many outliers caused by poor data quality and encoding issues.

9. Conclusions

This research introduces a novel flight plan matching ralgorithm aimed at improving the analysis of flight reroute proposals by the Group Rerouting Tool (GRRT). The proposed algorithm successfully achieves comparable results to the existing GRRT matching algorithm while also uncovering additional flight plans exclusively matched by the new approach. By simplifying the matching process and focusing on 2D representations of flight routes, the algorithm provides a more accurate and efficient means of identifying identical routes for subsequent tactical and strategic post-ops analysis.

This study contributes to the field by addressing the limitations of current 4D trajectory matching algorithms, offering a 2D approach inspired by string pattern matching techniques. The developed data structures and cataloguing methods facilitate the comparison of routes and segments, allowing for a deeper understanding of flight reroute proposal uptake. Notably, the proposed method overcomes the conservative nature of the 4D algorithm, showcasing its effectiveness in identifying matches with larger variations in flight levels.

In summary, the 2D flight plan matching algorithm proves to be a robust and efficient solution, not only matching more flights than the current GRRT approach but also enabling detailed tactical and strategic post-ops analyses. This enhanced capability provides a valuable tool for aviation experts to make informed decisions and optimize flight operations effectively.